順時針排序點列表

我遇到了問題，不知道如何解決。順時針排序點列表

我想排序點的列表，以便所有的點都是爲了形成一個路徑。到目前爲止，我所做的是計算列表中所有點的中心點，然後使用基於排序完成的代碼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()解決方案，但結果相同。任何幫助將非常感激。

來源

2016-03-31 niks

我認爲這將是有趣的添加到您的照片計算的中心點的位置 – pm100

您的主要任務是什麼？ – gabba

我有一個點的列表，並希望通過這些點繪製路徑。不幸的是他們沒有排序並給出不正確的結果。所以我試圖自己分類。 @gabba – niks

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

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

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

來源

2016-03-31 15:04:31 gabba

所以你說，如果我有凹多邊形，這是不可能的分點繪製正確的路徑？ – niks

@niks：第一個多邊形也是凹的。當中心點位於內核中時，該算法適用於[星形多邊形]（https://en.wikipedia.org/wiki/Star-shaped_polygon）。凸多邊形是星形的，它們的內核是整個多邊形，所以順時針排序是爲它們工作的。如果您找到一種方法將中心移動到T的橫條部分，您也可以對第二個多邊形使用順時針排序。 –

@Meehm，沒有辦法使算法適用於所有情況。 – gabba

順時針排序點列表

回答

相關問題