Ordering points in concave hull - algorithm

Question

I implemented an algorithm to find the alpha shape of a set of points. The alpha shape is a concave hull for a set of points, whose shape depends on a parameter alpha deciding which points make up the hull.

I have resolved the set of points in concave hull. These points make up a concave polygon. I would like to order these points in a clockwise manner.

Ordering points clockwise is straightforward when it is a convex shape. How to do this with a concave thing ? What algorithm is behind? I looked at 'non crossing shortest path' algorithms, 'shortest non crossing Hamiltonian path' algorithms. Is it the right approach ?

enter image description here

If you already have a polygon, does this mean that you have already an order, and need to determine only whether it is clockwise or counterclockwise? Or do you only have a set of points in no particular order, and want them to order so that they will form a polygon? — Petr
See stackoverflow.com/questions/6989100/… and cstheory.stackexchange.com/questions/8609/…. Some of used algorithms in this case can be see in en.wikipedia.org/wiki/Convex_hull_algorithms. — Mihai8
I've never done this before, but I imagine you could compute the centroid of the shape, then obtain the angular displacement of a vector leading from the centroid to each point (using arctan). If you have some code I could take a crack at adding this. — Asad Saeeduddin
Actually, ignore my atan suggestion above. Use the excellent approach from the accepted answer linked by @user1929959. Once you have the centroid, compare points based on whether the cross product of the vectors from the centroid to each point is positive (ccw rotation) or negative (cw rotation). The cross product when the third dimension is 0 is just the 2D determinant. — Asad Saeeduddin

kiriloff kiriloff · Accepted Answer · 2015-05-07T16:53:13

This answer is very valuable https://gamedev.stackexchange.com/questions/13229/sorting-array-of-points-in-clockwise-order as it is the same to order points in a concave hull, and any set of points, with the reference for ordering be the barycenter of the points (or any point inside the hull !)

Your question is not precise enough. An array of points is only « clockwise » or « anti-clockwise » relative to a reference point. Otherwise, any array of three points can always be either CW or CCW. See the following picture: on the left, the points are ordered clockwise; on the right, the exact same points are ordered anticlockwise.

clockwise or anticlockwise

In your case, I believe using the barycenter of the points as a reference point is reasonable.

A good method for an unknown number of points could be the following one:

let P[0], P[1], ... P[n-1] be the list of points to sort let M be the barycenter of all points

compute a[0], a[1], ... a[n-1] such that a[i] = atan2(P[i].y - M.y, P[i].x - M.x);

sort points relative to their a value, using qsort for instance.

Ordering points in concave hull - algorithm

1 Answers