Convex Hull of a n-polygon – The “Graham Scan” Algorithm

Andrew’s monotone chain convex hull algorithm constructs the convex hull of a set of 2-dimensional points in O(n \log n) time.

It does so by first sorting the points lexicographically (first by x-coordinate, and in case of a tie, by y-coordinate), and then constructing upper and lower hulls of the points in O(n) time.

An upper hull is the part of the convex hull, which is visible from the above. It runs from its rightmost point to the leftmost point in counterclockwise order. Lower hull is the remaining part of the convex hull.

public static Point[] ConvexHull(final Point[] x) {
    final boolean[] visited = new boolean[x.length];
    final ArrayList<Point> result = new ArrayList();

    // find the leftmost point of the hull
    int p = 0;
    for (int i = 0; i < x.length; i++) {
        if (x[i].x < x[p].x) {
            p = i;
        }
    }

    final int start = p;
    visited[start] = true;
    result.add(x[p]);

    do {
        int n = -1;

        for (int i = 0; i < x.length; i++) {
            if (visited[i]) {
                continue;
            }
            if (n == -1) {
                n = i;
            }

            // (X-P) x (N-P)
            final double cross = (x[i].x - x[p].x) * (x[n].y - x[p].y) - (x[i].y - x[p].y) * (x[n].x - x[p].x);

            if (cross < 0) {
                n = i;
            }
        }

        p = n;
        visited[p] = true;
        result.add(x[p]);

    } while (start != p);

    return result.toArray(new Point[result.size()]);
}

Leave a Reply

Your email address will not be published. Required fields are marked *