在快樂循環順序中生成點的凸殼算法？

Question

我改編了Anderson的單調鏈算法來尋找一個凸包，但是這樣做之後我發現結果點是按x順序的，而不是按照旋轉木馬的順序。是否有一個凸包算法可以按照旋轉木馬的順序生成點，這意味着圍繞船體的外圍排列？

這是我的單調鏈實現不滿足我的問題：

// monotone chain 
public static ComparablePoint[] convex_hull(ComparablePoint[] points){ 
    if(points.length > 1){ 
     int ctPoints = points.length; 
     int k = 0; 
     ComparablePoint[] hull = new ComparablePoint[ 2 * ctPoints ]; 
     java.util.Arrays.sort(points); 

     // Build lower hull 
     for (int i = 0; i < ctPoints; ++i) { 
      while (k >= 2 && crossProduct(hull[k - 2], hull[k - 1], points[i]) <= 0) 
       k--; 
      hull[k++] = points[i]; 
     } 

     // Build upper hull 
     for (int i = ctPoints - 2, t = k + 1; i >= 0; i--) { 
      while (k >= t && crossProduct(hull[k - 2], hull[k - 1], points[i]) <= 0) 
       k--; 
      hull[k++] = points[i]; 
     } 
     if (k > 1) { 
      hull = java.util.Arrays.copyOfRange(hull, 0, k - 1); // remove non-hull vertices after k; remove k - 1 which is a duplicate 
     } 
     return hull; 
    } else if(points.length <= 1){ 
     return points; 
    } else{ 
     return null; 
    } 
} 

要弄清楚我的意思是旋轉木馬輪順序：上凸包的點是在一個周長是一個凸多邊形。當你繞過多邊形的邊界時，我需要這些點。

上面顯示的單調鏈算法不會這樣做，它會按照它們的x座標順序返回點。具有最低x座標的點是第一個，然後是具有第二個最低x的點，依此類推。

Answer 1

以下算法按照您所描述的順序對船體上的點進行排序。它類似於@AyushMishra提供的答案，但另外解決了兩點具有相同X（或Y）值的情況。

/** 
* Sorts the given array according to "merry-go-round" order. The array is 
* sorted in-place. The ordering is clockwise ending with the bottom-most 
* point. 
* 
* @param points 
*   An array of points on a convex hull. 
*/ 
public static void sortPoints(Point[] points) { 

    // Ensure the input array is sorted by x-value 
    Arrays.sort(points, (o1, o2) -> Double.compare(o1.getX(), o2.getX())); 

    // get the index of the point with the smallest Y-value 
    int bottomMost = 0; 
    for (int i = 0; i < points.length; i++) { 
     if (points[i].getY() < points[bottomMost].getY()) 
      bottomMost = i; 
    } 

    final Comparator<Point> hullComp = new Comparator<Point>() { 

     @Override 
     public int compare(Point o1, Point o2) { 
      // handle case when Y's are the same. 
      if (o1.getY() == o2.getY()) 
       return Double.compare(o1.getX(), o2.getX()); 

      // otherwise, just compare Y values 
      return Double.compare(o1.getY(), o2.getY()); 
     } 
    }; 

    // Sort the left side of the hull from smallest Y to largest Y 
    Arrays.sort(points, 0, bottomMost, hullComp); 

    // Sort the right side of the hull from largest Y to smallest Y 
    Arrays.sort(points, bottomMost, points.length, 
      (o1, o2) -> hullComp.compare(o2, o1)); 

} 

我將此算法應用於this question中的2D船體。以下是結果圖。 （注：我抵消點，使得軸不會弄亂圖片）跟蹤線顯示了在不同的點在執行順序：

或者，你可以使用產生船體的算法按（順時針）順序自動排序。例如，Gift wrapping algorithm在O（nh）時刻產生旋轉木馬訂單中的點，其中h是船體上的頂點數。該算法的僞代碼（從維基百科借用）是：

jarvis(S) 
    pointOnHull = leftmost point in S 
    i = 0 
    repeat 
     P[i] = pointOnHull 
     endpoint = S[0]   // initial endpoint for a candidate edge on the hull 
     for j from 1 to |S| 
     if (endpoint == pointOnHull) or (S[j] is on left of line from P[i] to endpoint) 
      endpoint = S[j] // found greater left turn, update endpoint 
     i = i+1 
     pointOnHull = endpoint 
    until endpoint == P[0]  // wrapped around to first hull point 

Answer 2

只需將以下算法添加到您的算法中，該算法以增加的X順序輸出點。

我們將根據算法的輸出生成凸包的上半部分和下半部分。

讓我們看看凸包上的極端點。將它們命名爲L和R. [L是具有最小X座標的點，R是具有最大X座標的點]。

現在對於所有其他要點，我們將檢查該點是位於上半部還是下半部。這可以通過檢查點K是否位於連接L和R的直線上方或位於連接L和R的直線下面來輕鬆完成。

因此，我們可以將所有點分類在lower_half或upper_half中。

最後答案是：點L [左極點，即最小X] +點在upper_part增加X順序，點R [右極點，即最大X] +點在lower_part以X順序遞減。

注意：上述算法的複雜度爲O（n），所以它不會影響算法的運行時間複雜度，並且在添加它之後，解決方案的複雜性仍然是O（n log n）。