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]

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.