← all categories

Convex Hull d413dc5f

Convex hull via monotone chain. Returns hull vertices in counterclockwise order, no three consecutive collinear points (strictly convex turns only). Mutates a copy of the input (sorts it); pass by value or copy first if you need the original order.

Time: O(n \log n). tested

content/geometry/convex-hull.h

vector<Point> convexHull(vector<Point> pts) {
    int n = (int)pts.size();
    if (n <= 2) return pts;
    sort(pts.begin(), pts.end(), [](Point a, Point b) { return tie(a.x, a.y) < tie(b.x, b.y); });
    pts.erase(unique(pts.begin(), pts.end()), pts.end());
    n = (int)pts.size();
    if (n <= 2) return pts;

    vector<Point> hull(2 * n);
    int k = 0;
    for (int i = 0; i < n; i++) {
        while (k >= 2 && hull[k-2].cross(hull[k-1], pts[i]) <= 0) k--;
        hull[k++] = pts[i];
    }
    int lower = k + 1;
    for (int i = n - 2; i >= 0; i--) {
        while (k >= lower && hull[k-2].cross(hull[k-1], pts[i]) <= 0) k--;
        hull[k++] = pts[i];
    }
    hull.resize(k - 1);
    return hull;
}