順時針排序點列表

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

在這兩個示例中按順時針順序排列的點。但是對於第二個例子，這種方法不適合。順時針算法只適用於凸數字。

下面是不支持的圖的示例，沒有可用的中心點。

所以，如果你有一些點的集合，不知道如何把它們聯繫起來，不知道任何有關數字將無法恢復原來的身材。