0

我实现了在下一页找到的快速外壳代码：

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)

谁能帮帮我吗

4

1 回答 1

1

如果无法修改算法以正确顺序返回它们，您可以计算返回点的质心（将它们全部相加并除以计数，凸包的质心将始终位于外壳内） ，然后计算从质心到每个点的角度，如下所示：

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);

爪哇是：

    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
于 2015-05-04T23:14:41.927 回答