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;
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
|