以旋转木马顺序生成点的凸包算法？

Question

我采用安德森的单调链算法来寻找凸包，但在这样做之后我发现结果点是按 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;
    }
}

要清楚我所说的旋转木马顺序是什么意思：凸包上的点位于凸多边形的周长内。当您绕着多边形的周边走动时，我需要这些点是有序的。

上面显示的单调链算法不会这样做，它 returns 按 x 坐标的顺序排列点。 x 坐标最小的点在前，然后是 x 坐标第二低的点，依此类推。

Answer 1

只需将以下算法添加到您的算法中，该算法将按递增的 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)。

Answer 2

以下算法按照您的描述对船体上的点进行排序。它类似于@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

以旋转木马顺序生成点的凸包算法？

Convex hull algorithm that generates points in merry go round order?

algorithm

convex-hull