algorithm - 凹包中的排序点 - 算法

Question

我实现了一种算法来查找一组点的 alpha 形状。 alpha 形状是一组点的凹包，其形状取决于参数 alpha，它决定由哪些点组成包。

我已经解决了凹包中的点集。这些点组成了一个凹多边形。我想按顺时针顺序排列这些点。

当它是凸形时，顺时针排序点很简单。如何用凹面做这个？背后是什么算法？我研究了“非交叉最短路径”算法、“最短非交叉哈密顿路径”算法。这是正确的方法吗？

Answer 1

这个回答很有值(value)https://gamedev.stackexchange.com/questions/13229/sorting-array-of-points-in-clockwise-order因为在凹壳和任何一组点中对点进行排序是相同的，排序引用是点的重心(或壳内的任何点!)

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 orderedclockwise; on the right, the exact same points are orderedanticlockwise.

clockwise or anticlockwise

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

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

let P[0], P[1], ... P[n-1] be the list of points to sort let M be thebarycenter 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.