in reply to Re: Better maps with Math::Geometry::Voronoi, and a Challenge for Math Monks
in thread Better maps with Math::Geometry::Voronoi, and a Challenge for Math Monks

Huh, sounds promising. A few questions:

Re #5: Can you explain how I might implement this? My math skills are failing me here. Code would help.

Re #10: Hah! If that's the case then I guess it's game over for me. Just solving the easy part isn't going to help me much. It seems to me that without this step I'm highly likely to produce invalid polygons that won't render.

Re #11: How do you do that? I think if I could solve this one then my original approach might have worked.

-sam

  • Comment on Re^2: Better maps with Math::Geometry::Voronoi, and a Challenge for Math Monks

Replies are listed 'Best First'.
Re^3: Better maps with Math::Geometry::Voronoi, and a Challenge for Math Monks
by salva (Canon) on Jul 02, 2008 at 21:29 UTC
    Re #5: Can you explain how I might implement this? My math skills are failing me here. Code would help.
    You can compute the angle as ... 
    use Math::Trig qw(pi);
$angle = atan2($v2->{y}, $v2->{x}) - atan2($v1->{y}, $v1->{x});
# and normalize the angle to be in the range [-pi, pi]
my $rounds = floor(($angle + pi) / (2 * pi));
$angle -= 2 * pi * $rounds;

    [download]
    Re #10: Hah! If that's the case then I guess it's game over for me. Just solving the easy part isn't going to help me much. It seems to me that without this step I'm highly likely to produce invalid polygons that won't render.
    It's easy (at least conceptually!):

    At this point, @polygon contains a set of edges forming a closed polygon, all you have to do is to select all the edges inside from @edges and form (negative) polygons with them again. You will have to recursively call the procedure from 4.1 and take into account that this time you get polygons representing holes (that can contain holes, that are holes in holes and so "positive" polygons and so on).

    To find the set of edges inside @polygon from @edges, the easiest way is probably to recursively select all the edges connected to the edges/points in @polygon but that are not in @polygon.

    Re #11: How do you do that? I think if I could solve this one then my original approach might have worked.
    That's trivial (maybe some point on my previous post was confusing): @polygon contains a subset of @edges forming a closed polygon, you only have to ... 
    
my %polygon = map { $_ => 1 } @polygon, @polygon_holes;
@edges = grep { !$polygon{$_} } @edges

    [download]
[reply]
[d/l]
[select]
      To find the set of edges inside @polygon from @edges, the easiest way is probably to recursively select all the edges connected to the edges/points in @polygon but that are not in @polygon.
      opps, that's not enough, you also have to select all the edges (from @edges) connected to any vertex (from @vertices) that is inside the polygon (I am sure Google can show you several ways to find if a point is inside a polygon).
[reply]

In Section Meditations