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.

Lukelukens

The question doesn't make sense. The shape of the polygon depends on the order of the vertices. If you change their order, you'll draw a different shape... But if you want to choose an arbitrary center, you could sort by angle from that center point. atan2(y - centerY,x - centerX) I think you mean "convex" or "non concave" by the way. A circle is convex. – Reaganreagen

Did you check the example from the link I provided? That should be able to confirm whether I mean non-convex or not. I can guarantee an origin about which the points will be drawn. I will edit appropriately. – Lukelukens

Aren't you actually getting a list of lines from Conrec? That's different from a list of vertices. You can discover which lines are connected by checking for those which share a vertex point. – Pluto

Yes, sorry, you are technically correct. I get a two-point line segment from Conrec. But my end result is a List of lines where lines are a list of Points (it's a multi-dimensional array). That is because a contour line is not guaranteed to close with itself on a finitely bounded map. It may enter and leave the map multiple times, thus the multidimensional array of lines. These lines will not actually share any vertex. Please note, I am not arguing that this is the best way to do things. It's just the only way I could think of. – Lukelukens

Yes, but if the lines only become discontinuous when they leave the map you have a much easier problem to solve. Eg on the top border of the map, find the left most such point, and draw an edge to the next left-most such point, then skip to the next one and draw an edge to the one after that, and so on. Repeat for each edge of the map/viewport. – Pluto

Answer 1

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.

Pluto

Thank you. I hope with a few of the other guaranteed conditions in my problem that I might get a work-around a little easier than what you suggest (easier as in CPU cycles). But I may try this as well. – Lukelukens

Answer 2

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.

Sen

This sounds close to what I have to do. Thank you. For any given line segment, first I will have to determine which of the other lines has an end-point closest to the current line's terminus and then I will have to draw along that next line starting from that closest end-point (which may be the reverse order). – Lukelukens

Answer 3

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.

Ey

Indeed. But at least it will give me a forcible argument for more time. "Mathematically Impossible" has a nice ring to it. Unfortunately the previous programmer told us he had accomplished this functionality and then quit. So now I have to tell the project leader... :-) – Lukelukens

Answer 4

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.

Idaline