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

Question

I adapted Anderson's monotone chain algorithm for finding a convex hull but after doing so I discovered the resulting points are in x-order, not in merry-go-round order. Is there a convex hull algorithm that generates the points in merry-go-round order, meaning in order around the perimeter of the hull?

This is my monotone chain implementation which does not satisfy my problem:

// 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;
    }
}

To be clear what I mean by merry-go-round order: the points on a convex hull are in a perimeter which is a convex polygon. I need those points to be in order as you go around the perimeter of the polygon.

The monotone chain algorithm shown above does not do this, it returns the points in order of their x-coordinate. The point with the lowest x-coordinate is first, then the point with the second-lowest x, and so on.

Answer 1

Just add the following algorithm to your algorithm which outputs point in increasing X order.

We will generate the upper half and lower half of the convex hull from your algorithm's output.

Let's take the extreme points on the convex hull. Name them L and R. [L is the point having minimum X coordinate, R is the point having maximum X coordinate].

Now for all other points we will check if that point lie in the upper half or lower half. This could be easily done by checking if some point K, lies above the line joining L and R, or lies below the line joining L and R.

So, we can classify all points either in lower_half or upper_half.

Finally the answer would be : Point L [left extreme i.e minimum X] + points in upper_part in increasing X order, Point R[right extreme i.e maximum X] + points in lower_part in decreasing X order.

Note: The complexity of above algorithm is O(n), so it won't affect your algorithm's run time complexity and your solution's complexity would still be O(n log n) after adding it.

Answer 2

The following algorithm sorts points on a hull as you describe. It is similar to the answer provided by @AyushMishra, but additionally addresses the cases where two points have the same X (or Y) value.

/**
 * 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));

}

I applied this algorithm to the 2D hull found in this question. Here's a diagram of the results. (Note: I offset the points so that the axes wouldn't clutter the picture) The trace lines show the ordering at different points in execution:

Alternatively, you can use an algorithm that produces a hull that is automatically sorted in (counter)clockwise order. For example, the Gift wrapping algorithm produces points in merry-go-round order in O(nh) time where h is the number of vertices on hull. The pseudocode for this algorithm (borrowed from Wikipedia) is:

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