the first. the analogy of elastic around pegs is perfect. actually, more perfect is the analogy of shrink-wrapping around pegs -- concave polys are ok, just no boundary crossing.
i managed to get the following algorithm to work for the most part:
Code:
find the highest (lowest y coord) vertex
calc the angle from highest vertex to all other vertices
sort vertices numerically by that angle
connect vertices in order
and that avoids overlaps nicely. however, sometimes it generates strange shapes. here's an example of the algorithm at work, with a strange shape:
http://transmote.com/lab/simplePoly/
with this arrangement of vertices, it seems more 'natural' to draw the perimeter as 0-2-1-3-0, but that violates the "sort by angle to highest vertex" algorithm.
for a solution, i'm thinking about sorting by that algorithm, then looping through all vertices again and comparing the angle created by reversing the order of the second two vertices in each triplet, and going with the larger of the two. (i.e. with A012, also measure A021, and compare.) this could result in a complex polygon again, so if this loop does reverse the order in which it connects vertices, it would have to check the second segment in the triplet against all other segments in the polygon for an intersection.
since i'll rarely have more than, say, 10 vertices at a time, it shouldn't be too much of an issue for performance. of course, i don't even know yet if that will work, but i'll come back here to post my results when i get that far...which, due to scheduling, won't be for a while, unfortunately
Pages: 1
avoid complex polygons (Read 516 times)