Convex Hull (Bao lồi)

Wiki › Thuật toán › Hình học tính toán

huunguyen · Last updated 8, Tháng 4, 2026, 15:31

Bao lồi (Convex Hull) của tập điểm $P$ là đa giác lồi nhỏ nhất chứa tất cả các điểm trong $P$ .

Ứng dụng: Tìm diện tích bao lồi, Convex Hull Trick trong DP, bài toán tàu và bờ biển.

Thuật toán Andrew's Monotone Chain — $O (N \log N)$

Xây bao lồi bằng cách quét từ trái sang phải, duy trì phần dưới và phần trên riêng biệt.

struct Point {
    long long x, y;
    bool operator<(const Point& p) const {
        return x < p.x || (x == p.x && y < p.y);
    }
};

long long cross(Point O, Point A, Point B) {
    return (A.x-O.x)*(long long)(B.y-O.y) - (A.y-O.y)*(long long)(B.x-O.x);
}

// Trả về bao lồi theo chiều ngược kim đồng hồ
// Nếu muốn giữ điểm thẳng hàng trên cạnh: đổi <= thành <
vector<Point> convex_hull(vector<Point> pts) {
    int n = pts.size();
    if (n < 2) return pts;
    sort(pts.begin(), pts.end());
    pts.erase(unique(pts.begin(), pts.end(), [](const Point& a, const Point& b) {
        return a.x == b.x && a.y == b.y;
    }), pts.end());
    n = pts.size();
    if (n < 2) return pts;

    vector<Point> hull;

    // Phần dưới (lower hull)
    for (int i = 0; i < n; i++) {
        while (hull.size() >= 2 && cross(hull[hull.size()-2], hull.back(), pts[i]) <= 0)
            hull.pop_back();
        hull.push_back(pts[i]);
    }

    // Phần trên (upper hull)
    int lower_size = hull.size() + 1;
    for (int i = n-2; i >= 0; i--) {
        while ((int)hull.size() >= lower_size && cross(hull[hull.size()-2], hull.back(), pts[i]) <= 0)
            hull.pop_back();
        hull.push_back(pts[i]);
    }

    hull.pop_back();
    return hull;
}

Thuật toán Graham Scan — $O (N \log N)$

Quét từ điểm cực dưới-trái, sắp xếp theo góc cực:

vector<Point> graham_scan(vector<Point> pts) {
    int n = pts.size();
    // Tìm điểm cực dưới-trái
    int pivot = 0;
    for (int i = 1; i < n; i++)
        if (pts[i].y < pts[pivot].y || (pts[i].y == pts[pivot].y && pts[i].x < pts[pivot].x))
            pivot = i;
    swap(pts[0], pts[pivot]);
    Point p0 = pts[0];

    sort(pts.begin()+1, pts.end(), [&](const Point& a, const Point& b) {
        long long c = cross(p0, a, b);
        if (c != 0) return c > 0;
        return dist2(p0, a) < dist2(p0, b);
    });

    vector<Point> hull = {pts[0], pts[1]};
    for (int i = 2; i < n; i++) {
        while (hull.size() >= 2 && cross(hull[hull.size()-2], hull.back(), pts[i]) <= 0)
            hull.pop_back();
        hull.push_back(pts[i]);
    }
    return hull;
}

Diện tích bao lồi

double hull_area(vector<Point>& hull) {
    long long area2 = 0;
    int n = hull.size();
    for (int i = 0; i < n; i++) {
        int j = (i+1) % n;
        area2 += hull[i].x * hull[j].y - hull[j].x * hull[i].y;
    }
    return abs(area2) / 2.0;
}

Rotating Calipers — Đường kính bao lồi

Tìm cặp điểm xa nhất trong bao lồi trong $O (N)$ sau khi đã xây:

long long diameter2(vector<Point>& hull) {
    int n = hull.size();
    if (n == 1) return 0;
    if (n == 2) return dist2(hull[0], hull[1]);

    long long ans = 0;
    int j = 1;
    for (int i = 0; i < n; i++) {
        int ni = (i+1) % n;
        while (cross(hull[ni]-hull[i], hull[(j+1)%n]-hull[j], {0,0}) < 0)   // hướng lên
            j = (j+1) % n;
        ans = max({ans, dist2(hull[i], hull[j]), dist2(hull[ni], hull[j])});
    }
    return ans;
}

Khi nào dùng Convex Hull?

Tìm đa giác lồi bao quanh tập điểm.
Tìm cặp điểm xa nhất (rotating calipers).
CHT trong DP (tập đường thẳng tạo thành bao lồi).
Bài toán tầm nhìn, bao bì, v.v.

Bình luận

Không có bình luận tại thời điểm này.