c# - Quickhull 点未按正确顺序返回

Question

我实现了下一页上的快速船体代码:

http://www.ahristov.com/tutorial/geometry-games/convex-hull.html

该算法返回凸包的正确点，但未按正确的三角顺序返回它们。由于这些点的顺序没有意义，我不能用它们来画线，因此不能画船体本身。

例如，当我用以下几点运行算法时

 (2,5) (9,2) (1,8) (0,5) (3,3)

我希望它们返回的正确顺序是:

 (0,5) (1,8) (9,2) (3,3)

相反，快速船体算法会像这样返回它们:

 (1,8) (0,5) (3,3) (9,2)

谁能帮帮我

Answer 1

如果无法修改算法以按正确顺序返回它们，您可以计算 centroid返回的点(将它们全部加起来并除以计数，凸包的质心将始终位于包内)，然后计算从质心到每个点的角度，如下所示:

point.angle = atan2(point.y - centroid.y, point.x - centroid.x);

然后根据角度对点列表进行排序。

此外，您的这部分 C# 代码与 Java 不匹配:

    // Recursively proceed with new sets
    HullSplit(minPt, farthestPt, leftSetMinPt, ref hull);
    HullSplit(maxPt, farthestPt, leftSetMaxPt, ref hull);
    // should be:
    // HullSplit(farthestPt, maxPt, leftSetMaxPt, ref hull);

Java 是:

    hullSet(A,P,leftSetAP,hull);
    hullSet(P,B,leftSetPB,hull);

此外，与 Java 相比，您有效地颠倒了点到线测试的标志:

public int pointLocation(Point A, Point B, Point P) {
   int cp1 = (B.x-A.x)*(P.y-A.y) - (B.y-A.y)*(P.x-A.x);
   return (cp1>0)?1:-1;
}

if (pointLocation(A,B,p) == -1)  // tests for negative
if (pointLocation(A,P,M)==1) { // tests for positive
if (pointLocation(P,B,M)==1) { // tests for positive

C#:

private static bool IsAboveLine(Point a, Point b, Point pt)
{
    var result = ((b.X - a.X) * (pt.Y - a.Y))
                -((b.Y - a.Y) * (pt.X - a.X));

    return (result > 0) ? true : false;
}

if (IsAboveLine(minPt, maxPt, pt))  // tests for positive
if (!IsAboveLine(minPt, farthestPt, set.ElementAt(i)))  // tests for negative
if (!IsAboveLine(farthestPt, maxPt, set.ElementAt(i)))  // tests for negative