c# - 顺时针排序点列表

Question

我遇到了问题，不知道如何解决。

我正在尝试对点列表进行排序，以便所有点都形成一条路径。到目前为止，我所做的是计算列表中所有点的中心点，然后使用来自 this post 的代码。基于哪个进行排序。这是借用的代码片段:

public int Compare(Point3D pointA, Point3D pointB)
{
    if (pointA.X - CenterPoint.X >= 0 && pointB.X - CenterPoint.X < 0)
        return 1;
    if (pointA.X - CenterPoint.X < 0 && pointB.X - CenterPoint.X >= 0)
        return -1;

    if (pointA.X - CenterPoint.X == 0 && pointB.X - CenterPoint.X == 0)
    {
        if (pointA.Y - CenterPoint.Y >= 0 || pointB.Y - CenterPoint.Y >= 0)
           if (pointA.Y > pointB.Y)
               return 1;
            else return -1;
        if (pointB.Y > pointA.Y)
            return 1;
        else return -1;
    }

    // compute the cross product of vectors (CenterPoint -> a) x (CenterPoint -> b)
    double det = (pointA.X - CenterPoint.X)*(pointB.Y - CenterPoint.Y) -
                     (pointB.X - CenterPoint.X)*(pointA.Y - CenterPoint.Y);
    if (det < 0)
        return 1;
    if (det > 0)
        return -1;

    // points a and b are on the same line from the CenterPoint
    // check which point is closer to the CenterPoint
    double d1 = (pointA.X - CenterPoint.X)*(pointA.X - CenterPoint.X) +
                    (pointA.Y - CenterPoint.Y)*(pointA.Y - CenterPoint.Y);
    double d2 = (pointB.X - CenterPoint.X)*(pointB.X - CenterPoint.X) +
                    (pointB.Y - CenterPoint.Y)*(pointB.Y - CenterPoint.Y);
    if (d1 > d2)
        return 1;
    else return -1;
}

在某些情况下它工作正常但有时它会产生奇迹，请看附图，黑点是计算中心点:

在图 A 中一切正常，但是如果我决定向上移动形成两条水平线的点，我会遇到这个:

绿线是它应该的样子，黑线是它的真实样子，我不明白为什么我会这样。我还尝试了 atan() 解决方案，但结果相同。非常感谢任何帮助。

Answer 1

在您的两个示例中，点都按顺时针方向排序。但是对于第二个例子，它的方法不合适。顺时针算法仅适用于凸图形。

这里是不支持图形的示例，没有可用的中心点。

因此，如果您有一些点集，​​但不知道如何链接它们，并且对图形一无所知，您就无法恢复原始图形。