Order concave polygon vertices counterclockwise

3
votes

I have a set of points that are on the boundary of a concave polygon. I would like to find one non crossing polygon that have these points as vertices. In other words, I would like to order in a ccw (or cw) manner vertices of a concave polygon.

I had a look at methods to evaluate whether a polygon is ordered in ccw or cw manner (compute and sum cross products). It is not exactly my problem: I have the vertices in random sequence, and I want to order them so as to have them cw or ccw on the crust of the polygon.

I thought of taking the initial sequence of vertices, and successively identify crossings. If initial points sequence is [x1,y1 ; x2, y2 ; x3, y3 ; ...] and 2nd and 3rd points are crossing, we continue with sequence [x1,y1 ; x2, y3 ; x3, y2 ; ...]

What algorithm can you think of? what are notions behind? Do you have hints at some references?

alpha shape

Regds

2
algorithmgraphgeometrypolygoncounterclockwise
It's not clear what you mean by crossing points. Do you mean crossing lines ? In your example you seem to be changing the points - from (x2,y2) and (x3, y3) to (x2, y3) and (x3, y2) ? – krjampani

2 Answers

4
votes

If I understood the problem correctly, you want to order the input set of points so that they appear in clockwise order of some possibly concave polygon. This can be solved as follows.

enter image description here

Let p1 and p2 be the left-most and right-most points. Find a lower convex hull S of the points. S contains p1, p2 and all the convex hull points that are below the line p1p2. Now sort the remaining points (those not in S) by their x-coordinate. This sorted order together with the order of S (generated by the lower convex hull algorithm) will give you a desired clockwise order of all the vertices.

0
votes

There is information at the time the polygon is constructed that must be used unless the polygon is better defined than a set of points that could be a concave polygon I think.

For example, if the vertices are taken from a shape or image then the filled pixels in the shape can be helpful. For one project I need to order points on the perimeter of blobs, so I get the border pixels of the blob (can be done in many ways), then I use a DFS style traversal through those to put them in sequence. I then wrote algorithms to merge edges and make decisions at junctions.