geometry - how to order vertices in a simple, non-convex polygon

Question

I have a problem where I have a series of points for a simple, non-convex polygon (I hope I have the terminology correct). But the points are not necessarily in order (ie, clockwise or counterclockwise). For Flash's drawing API to correctly draw a fill area, I need to have these points progress in order around the edge (to finally connect with the starting point).

Is there some way I can sort my list of Cartesian coordinates in either clockwise or counterclockwise direction so I can draw my shape from point to point without "lifting the pen"?

I saw one post for sorting 4-points of a polygon, but I think it was a special case only for 4 points. My shapes have at minimum 6 points. In the list, each entry is guaranteed to be adjacent (in either clockwise or counterclockwise order) to at least one of its neighbors (either the previous point or the following). For example: A, B, D, C... or B, A, D, C... but not A, C, B, D... (I need to sort so I get either A, B, C, D or D, C, B, A). I found this post, but it appears to be unanswered: Sort point list into polygon

CPU performance is an issue. But even a "slow" solution, if it is easy to implement and understand (for the next programmer) might be ok if I can come up with an effective cache mechanism.

I would like to attach a picture to show an example of what I need to do but do not yet have 10 reputation points. Anyway, if I had a means for sorting the vertices of the 3rd example in this list of polygons, that would be perfect: http://upload.wikimedia.org/wikipedia/commons/1/1f/Assorted_polygons.svg

I really appreciate any and all help, thank you!

EDIT: I can indeed guarantee a center point for the coordinate system--it will be the center of the screen. All points will be between 0 and Screen Width/Height (origin is obviously Width/Height / 2). I cannot guarantee that the polygon will contain the origin point in its interior. It is a rare case exception, but I need to account for it.

By the way, the reason my segments are not necessarily in order is because they are generated using Conrec: http://paulbourke.net/papers/conrec/ (they are contour lines). I order the contour line segments generated by Conrec using the following: How to assemble an array(s) of continuous points for a contour line using Conrec The problem case now is for the outer contour lines on a map. Those will intersect with the edge of the map (ie, not form a closed polygon). In this case, I have draw around the edge of the map bounds until either I re-connect with where the line started (on the edge of the map) or a sibling line enters the map (repeating until I eventually get back to my starting point). Then I can draw an area and get the fill API to work. Hope this information helps. I assumed the best thing to do would be to generate an ordered list of polygon vertices, but perhaps another approach is called for.

Answer 1

I'm thinking of an O(n^2) algorithm:
Since you have the points in order that they are drawn (hopefully), you know the endpoints of each edge.
Choose a point to start on, then continue until you intersect another edge.
Then you mark that spot, continue on the new edge until you reach yet another edge or an endpoint. Whenever you reach a point where you change edges, list it. Once you reach the start point, you are done.