how to order vertices in a simple, non-convex polygon_问答_开发者

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 p开发者_JAVA百科icture 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.

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.

Perhaps you mean that the polygon is convex (i.e. it's non-concave). Otherwise I don't think what you're doing is actually possible (there could be multiple ways to "join the dots" and form a polygon).

One technique I can think of in that case: First, the first two items in the list must form an edge, by the rules you give. Then try adding vertices as they appear in list order; in each case, if the result could only be concave, remove the previous element from the result list and ignore it for now. Once you have gone through the source list, if you still vertices that you skipped over, continue for those skipped vertices.

Edit: Ok, just looked at your example from wikipedia, and you do mean non-convex. I don't think it's possible unfortunately.

Well, you're not going to like it, but it's not possible. If you think about removing all the lines in your demonstration polygon, you could connect them in a different way and still have a valid non-convex polygon, so how's a sort supposed to know which way to go? That's what sucks about non-convex polygons.

A simple example showing that the problem is not uniquely soluble is the points a=(0,0), b=(2,0), c=(1,1), d=(1,2); each of the orders (a,b,c,d,a), (a,b,d,c,a) (a,c,b,d,a) are simple polygons.