Sweep Line (Quét đường thẳng)

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

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

Sweep Line là kỹ thuật di chuyển một đường thẳng qua mặt phẳng để xử lý các sự kiện theo thứ tự tọa độ, giải nhiều bài toán hình học trong $O (N \log N)$ .

Ý tưởng

Xác định các sự kiện (events) — thường là điểm đầu/cuối của đoạn thẳng.
Sắp xếp sự kiện theo tọa độ quét (thường là $x$ ).
Duy trì trạng thái hiện tại (active set) khi di chuyển đường quét.
Xử lý từng sự kiện để cập nhật trạng thái và tính kết quả.

Ứng dụng 1: Diện tích hợp của hình chữ nhật

Tính diện tích hợp (union) của $N$ hình chữ nhật:

#include <bits/stdc++.h>
using namespace std;

// Mỗi hình chữ nhật: [x1,x2] x [y1,y2]
// Event: (x, type, y1, y2) với type: +1 = thêm, -1 = xóa

struct Event {
    int x, type, y1, y2;
    bool operator<(const Event& e) const { return x < e.x; }
};

// Segment tree đếm số lần phủ và tổng chiều dài được phủ
struct SegTree {
    vector<int> cnt;
    vector<long long> len;
    vector<int> ys;   // tọa độ y đã nén

    SegTree(vector<int>& ys) : ys(ys), cnt(4*ys.size(), 0), len(4*ys.size(), 0) {}

    void update(int node, int l, int r, int ql, int qr, int val) {
        if (qr <= l || r <= ql) return;
        if (ql <= l && r <= qr) { cnt[node] += val; }
        else {
            int mid = (l+r)/2;
            update(2*node, l, mid, ql, qr, val);
            update(2*node+1, mid, r, ql, qr, val);
        }
        if (cnt[node] > 0) len[node] = ys[r] - ys[l];
        else if (l+1 == r) len[node] = 0;
        else len[node] = len[2*node] + len[2*node+1];
    }
};

long long union_area(vector<tuple<int,int,int,int>>& rects) {
    vector<Event> events;
    vector<int> ys;

    for (auto [x1, y1, x2, y2] : rects) {
        events.push_back({x1, +1, y1, y2});
        events.push_back({x2, -1, y1, y2});
        ys.push_back(y1);
        ys.push_back(y2);
    }

    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    sort(events.begin(), events.end());

    SegTree seg(ys);
    int m = ys.size();
    long long area = 0;
    int prev_x = events[0].x;

    for (auto& e : events) {
        area += seg.len[1] * (e.x - prev_x);
        prev_x = e.x;

        int ql = lower_bound(ys.begin(), ys.end(), e.y1) - ys.begin();
        int qr = lower_bound(ys.begin(), ys.end(), e.y2) - ys.begin();
        seg.update(1, 0, m-1, ql, qr, e.type);
    }
    return area;
}

Ứng dụng 2: Đếm giao điểm đoạn thẳng (Bentley-Ottmann idea)

Kiểm tra xem có hai đoạn thẳng nào trong tập $N$ đoạn giao nhau không — $O (N \log N)$ :

// Sắp xếp các đầu mút theo x, dùng ordered set theo y để kiểm tra giao điểm
// Khi thêm đoạn: kiểm tra với đoạn trên và dưới trong active set
// Khi xóa đoạn: kiểm tra đoạn trên và dưới với nhau

Ứng dụng 3: Bao phủ đoạn thẳng

Tính tổng chiều dài của hợp $N$ đoạn thẳng trên trục số:

long long union_length(vector<pair<int,int>>& segs) {
    vector<pair<int,int>> events;
    for (auto [l, r] : segs) {
        events.push_back({l, 1});
        events.push_back({r, -1});
    }
    sort(events.begin(), events.end());

    long long total = 0;
    int cnt = 0, prev = 0;
    for (auto [x, type] : events) {
        if (cnt > 0) total += x - prev;
        cnt += type;
        prev = x;
    }
    return total;
}

Khi nào dùng Sweep Line?

Tính diện tích/chu vi hợp của các hình.
Đếm/tìm giao điểm đoạn thẳng.
Bài toán "khoảng cách gần nhất" theo một chiều.
Bài toán skyline (đường chân trời).

Bình luận

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