Convex hull: Monotone Chain Method

August 22, 2017

There is a method named “Monotone Chain Method” for finding convex hull of some points. It it quite easy to understand how and why it works.

We basically sort all points based on x axis. Then we find the left most points. Then we try to go clockwise as long as we can, we’ll reach the right most point. These points will form upper hull. Then from the right most point, we again try to go CW and reach left most point.

Visualization:

Pseudocode:

# Given: P = list of points on a place. length(P) >= 3. 
# Notation: 
# L[-1] := last element of list L
# L[-2] := second last element of list L. 
sort points in P by x-coordinate, break ties by y-coordinate
U, L = [], [] # empty-lists. for upper, lower hulls. 
for i = 1, 2, ..., n:
    while length(U) >= 2 and (U[-2], U[-1], P[i]) != clockwise turn:
        remove the last point from U
    append P[i] to U
for i = n, n-1, ..., 1:
    while length(L) >= 2 and (L[-2], L[-1], P[i]) != clockwise turn:
        remove the last point from L
    append P[i] to L
Remove the last point of each list (it's the same as the first point of the other list).
Concatenate U and L to obtain the convex hull of P.
Points in the result will be listed in clockwise order.

Here is a sample code in C++:

ll cross (point a, point b, point c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
vector<point> ConvexHull(vector<point>&p, int n) {
    int sz = 0;
    vector<point> hull(n + n);
    sort(p.begin(), p.end());
    for(int i = 0; i < n; ++i) {
        while (sz > 1 and cross(hull[sz - 2], hull[sz - 1], p[i]) <= 0) --sz;
            hull[sz++] = p[i];
    }
    for(int i = n - 2, j = sz + 1; i >= 0; --i) {
        while (sz >= j and cross(hull[sz - 2], hull[sz - 1], p[i]) <= 0) --sz;
            hull[sz++] = p[i];
    <sup>}</sup> hull.resize(sz - 1);
    return hull;
}

For more details, you can read this: Convex hull-Monotone chain