Wiki › Thuật toán › Hình học tính toán › Sweep Line (Quét đường thẳng)

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

huunguyen Updated Tháng sáu 2, 2026

Sweep Line (quét đường thẳng) là kỹ thuật tưởng tượng một đường thẳng quét ngang qua mặt phẳng (hoặc một con trỏ chạy dọc trục số), dừng lại tại các điểm "đáng chú ý" gọi là sự kiện (event) để cập nhật trạng thái. Nhờ đó nhiều bài toán hình học/khoảng vốn cần $O (N^{2})$ khi so từng cặp được giải trong $O (N \log N)$ , vì ta chỉ xử lý $O (N)$ sự kiện đã sắp xếp và mỗi sự kiện tốn $O (\log N)$ .

Các bài toán điển hình: tính diện tích/chu vi hợp của hình chữ nhật, độ dài hợp của các đoạn thẳng, đếm cặp đoạn thẳng cắt nhau, đếm số hình chồng lên một điểm, bài toán skyline (đường chân trời), cặp điểm gần nhất.

Ý tưởng / Trực giác

Cốt lõi của sweep line dựa trên một quan sát: trạng thái của bài toán chỉ thay đổi tại một số hữu hạn vị trí, không thay đổi liên tục.

Hãy nghĩ về bài tính độ dài hợp của các đoạn thẳng trên trục số. Nếu một điểm $x$ nằm "trong" một số đoạn, thì khi $x$ tăng dần, số đoạn phủ nó chỉ thay đổi đúng tại các đầu mút của đoạn: tại điểm mở (left) số đoạn $+ 1$ , tại điểm đóng (right) số đoạn $- 1$ . Giữa hai mút liên tiếp, số đoạn phủ là hằng số. Vậy thay vì quét từng đơn vị (vô số), ta chỉ cần xét $2 N$ mút.

Tổng quát, thuật toán gồm 4 phần:

Tạo sự kiện: với mỗi đối tượng, sinh ra các mốc làm trạng thái thay đổi (đầu/cuối đoạn, cạnh trái/phải hình chữ nhật...).
Sắp xếp sự kiện theo tọa độ quét (thường là $x$ ). Đây là chìa khóa: xử lý theo thứ tự khiến mỗi sự kiện chỉ cần cập nhật cục bộ.
Duy trì trạng thái hiện tại (active set) — tập các đối tượng mà đường quét đang "cắt" qua. Cấu trúc lưu trạng thái tùy bài: một biến đếm, một multiset, hay một cây phân đoạn (segment tree).
Cộng dồn kết quả: giữa hai sự kiện liên tiếp ở $x_{p r e v}$ và $x_{c u r}$ , trạng thái không đổi, nên đóng góp vào kết quả là (giá_trị_trạng_thái) * (x_cur - x_prev). Cộng phần này trước khi áp dụng sự kiện tại $x_{c u r}$ .

Vì sao đúng? Vì ta đã chia trục quét thành các "dải" giữa các sự kiện liên tiếp, trong mỗi dải trạng thái là bất biến, và ta tính chính xác đóng góp của từng dải. Tổng các dải bao trùm toàn bộ miền, không bỏ sót, không tính trùng.

Ví dụ chạy tay: độ dài hợp của các đoạn

Cho 3 đoạn trên trục số: $[1, 5]$ , $[3, 7]$ , $[10, 12]$ . Cần tổng độ dài vùng được phủ bởi ít nhất một đoạn.

Sinh sự kiện (vị trí, loại): mở +1, đóng -1. Sắp theo vị trí:

vị trí:   1    3    5    7    10   12
loại:    +1   +1   -1   -1   +1   -1

Quét từ trái sang, cnt = số đoạn đang phủ, total = kết quả. Trước mỗi sự kiện, nếu cnt > 0 ta cộng (x - prev) vào total:

x=1:  prev=1, cnt=0  -> dải [.. ,1] không phủ, cộng 0;   rồi +1 => cnt=1
                                                          ^ đường quét tới đây
x=3:  dải [1,3] có cnt=1>0 -> total += 3-1 = 2;          rồi +1 => cnt=2
       phủ:  1###3
x=5:  dải [3,5] có cnt=2>0 -> total += 5-3 = 2 (=4);     rồi -1 => cnt=1
       phủ:  1#######5     (chồng 2 lớp nhưng vẫn tính 1 lần)
x=7:  dải [5,7] có cnt=1>0 -> total += 7-5 = 2 (=6);     rồi -1 => cnt=0
x=10: dải [7,10] có cnt=0 -> cộng 0;                     rồi +1 => cnt=1
x=12: dải [10,12] có cnt=1>0 -> total += 12-10 = 2 (=8); rồi -1 => cnt=0

Kết quả total = 8. Kiểm tra tay: $[1, 7]$ dài 6 (hai đoạn đầu nối nhau) cộng $[10, 12]$ dài 2, tổng 8. Đúng.

Lưu ý cách cnt lên 2 ở dải $[3, 5]$ rồi xuống 1: ta chỉ cần biết cnt > 0 hay không, nên phần chồng nhau không bị cộng hai lần — đây chính là cái khéo của sweep.

Cài đặt

Độ dài hợp của các đoạn (1 chiều)

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

long long union_length(vector<pair<int,int>>& segs) {
    // Mỗi đoạn [l, r] sinh 2 sự kiện: mở (+1) tại l, đóng (-1) tại r.
    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()); // sắp theo tọa độ x

    long long total = 0;
    int cnt = 0, prev = 0;
    bool started = false;
    for (auto [x, type] : events) {
        // Cộng đóng góp của dải [prev, x] TRƯỚC khi đổi trạng thái.
        if (started && cnt > 0) total += (long long)(x - prev);
        cnt += type;          // áp dụng sự kiện
        prev = x;
        started = true;
    }
    return total;
}

Diện tích hợp của hình chữ nhật (sweep + segment tree)

Quét theo $x$ . Mỗi hình chữ nhật $[x_{1}, x_{2}] \times [y_{1}, y_{2}]$ tạo hai cạnh dọc: tại $x_{1}$ "bật" khoảng $y \in [y_{1}, y_{2}]$ (+1), tại $x_{2}$ "tắt" khoảng đó (-1). Cây phân đoạn trên trục $y$ (đã nén tọa độ) trả lời nhanh: "tổng độ dài phần trục $y$ đang được phủ ít nhất 1 lần". Giữa hai cạnh dọc liên tiếp, diện tích thêm vào = (độ dài phủ theo $y$ ) × (khoảng cách $x$ ).

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

struct Event {
    int x, type, y1, y2;             // cạnh dọc tại x, bật/tắt khoảng [y1,y2]
    bool operator<(const Event& e) const { return x < e.x; }
};

struct SegTree {
    vector<int>  cnt;                // số lần khoảng nút này được phủ trọn
    vector<long long> len;           // độ dài phần trục y được phủ trong nút
    vector<int>& ys;                 // mảng tọa độ y đã nén

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

    // Bật/tắt (val = +1 / -1) khoảng tọa độ thực [ys[ql], ys[qr])
    void update(int node, int l, int r, int ql, int qr, int val) {
        if (qr <= l || r <= ql) return;          // không giao
        if (ql <= l && r <= qr) {
            cnt[node] += val;                    // phủ trọn nút này
        } else {
            int mid = (l + r) / 2;
            update(2*node,   l, mid, ql, qr, val);
            update(2*node+1, mid, r, ql, qr, val);
        }
        // Cập nhật len: nếu nút còn được phủ -> toàn bộ độ dài thực;
        // ngược lại gộp từ con (lá thì = 0).
        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<array<int,4>>& rects) { // mỗi rect = {x1,y1,x2,y2}
    vector<Event> ev;
    vector<int> ys;
    for (auto& r : rects) {
        int x1=r[0], y1=r[1], x2=r[2], y2=r[3];
        ev.push_back({x1, +1, y1, y2});
        ev.push_back({x2, -1, y1, y2});
        ys.push_back(y1); ys.push_back(y2);
    }
    // Nén tọa độ y: chỉ các giá trị y này mới là biên thay đổi.
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    sort(ev.begin(), ev.end());

    SegTree seg(ys);
    int m = ys.size();
    long long area = 0;
    int prevx = ev[0].x;
    for (auto& e : ev) {
        // Dải [prevx, e.x]: cao = len phủ hiện tại, rộng = e.x - prevx.
        area += seg.len[1] * (long long)(e.x - prevx);
        prevx = 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;
}

Độ phức tạp

Bài toán	Thời gian	Bộ nhớ
Độ dài hợp đoạn (1D)	$O (N \log N)$	$O (N)$
Diện tích hợp hình chữ nhật	$O (N \log N)$	$O (N)$

Thời gian: có $2 N$ sự kiện. Sắp xếp tốn $O (N \log N)$ . Với bài 1D, mỗi sự kiện chỉ cập nhật một biến đếm $O (1)$ , nên phần quét là $O (N)$ và sắp xếp chiếm chủ đạo. Với bài diện tích, mỗi sự kiện gọi một update trên cây phân đoạn tốn $O (\log N)$ , tổng $O (N \log N)$ .
Bộ nhớ: lưu $2 N$ sự kiện và (với bài diện tích) một cây phân đoạn $4 N$ nút trên các tọa độ $y$ đã nén — tất cả $O (N)$ .

So với cách ngây thơ: đếm phủ bằng cách rải lưới hoặc so từng cặp là $O (N^{2})$ hoặc tệ hơn (phụ thuộc miền tọa độ). Sweep line cắt xuống $O (N \log N)$ và không phụ thuộc độ lớn tọa độ nhờ nén.

⚠️ Lỗi thường gặp

Tràn số (overflow): kết quả diện tích/độ dài thường vượt int. Tích len * (x_cur - x_prev) với tọa độ tới $10^{8}$ cho ra cỡ $10^{16}$ — phải dùng long long và ép kiểu trước khi nhân ((long long)len * dx), nếu nhân hai int rồi mới gán vào long long thì đã tràn.
Cộng kết quả sai thời điểm: phải cộng đóng góp của dải [prev, x] trước khi cập nhật cnt/cây tại x. Cộng sau sẽ tính nhầm trạng thái của dải kế tiếp cho dải hiện tại, lệch hẳn kết quả.
Nửa đóng nửa mở khi nén tọa độ: trong cây phân đoạn theo $y$ , mỗi "lá" đại diện khoảng $[y s [i], y s [i + 1])$ chứ không phải một điểm. Nếu xử lý như điểm rời rạc (gán len cho lá theo điểm), độ dài sẽ thiếu/thừa. Luôn coi nút quản lý khoảng và len = ys[r] - ys[l] khi phủ trọn.
Thứ tự sự kiện cùng tọa độ: khi nhiều sự kiện trùng $x$ (ví dụ một hình đóng và một hình mở cùng $x$ ), thứ tự áp dụng có thể ảnh hưởng (nhất là khi đếm biên để tính chu vi, hoặc khi tính phủ "≥ K lớp"). Quy ước nhất quán: thường xử lý sự kiện mở trước, đóng sau để các hình kề cạnh được coi là dính liền; ngược lại với một số bài chu vi.
Quên nén tọa độ / nén nhầm: nếu để cây phân đoạn chạy trực tiếp trên tọa độ thật cỡ $10^{8}$ sẽ tràn bộ nhớ. Phải nén về $O (N)$ giá trị phân biệt. Lỗi phổ biến là lower_bound ra chỉ số rồi quên rằng số lá (khoảng) ít hơn số điểm đúng 1.
Trùng/biên rỗng: hình chữ nhật có $x_{1} = x_{2}$ (rộng 0) hay đoạn $l = r$ không đóng góp nhưng vẫn nên xử lý gọn để không chia/nhân ra giá trị âm; sắp xếp với tọa độ âm cũng cần long long nếu hiệu hai tọa độ có thể tràn int.

Biến thể / Mở rộng

Phủ "≥ K lớp": thay vì hỏi cnt > 0, ta hỏi cnt >= K. Cây phân đoạn cần lưu thêm độ dài phần được phủ đúng/ít nhất $K$ lần (giữ vài mức đếm).
Chu vi hợp của hình chữ nhật: vẫn sweep theo $x$ nhưng tại mỗi cạnh dọc cộng phần thay đổi của tổng độ dài biên theo $y$ (giá trị tuyệt đối của hiệu len trước/sau), đồng thời cộng cạnh ngang. Đòi hỏi cây phân đoạn lưu thêm số "đoạn liên thông" được phủ.
Đếm giao điểm đoạn thẳng (Bentley–Ottmann): active set là một multiset các đoạn sắp theo $y$ tại đường quét; sự kiện gồm cả điểm giao mới phát sinh.
Sweep theo góc (angular sweep) và sweep + cây Fenwick để đếm cặp/điểm trong vùng — xem các bài luyện bên dưới.
Liên hệ: kỹ thuật này thường đi cùng nén tọa độ và cây phân đoạn.

Bài tập luyện

Sơn Hàng Rào (paintfencebr) — (Sơ cấp) Quét 1D đơn thuần: đếm độ dài đoạn được sơn ≥ 2 lớp, làm quen với sự kiện mở/đóng và đếm phủ.
Tầm Nhìn (stampede) — (Trung cấp) Mỗi con bò cắt trục $y$ trong một khoảng thời gian; sắp các khoảng rồi quét để đếm khoảng không bị che hoàn toàn.
Sơn Hàng Rào — Bạc (paintfencesi) — (Trung cấp) Mở rộng lên "phủ ≥ K lớp" kèm nén tọa độ, bước đệm trước khi dùng cây phân đoạn.
Trồng Cỏ — Bạc (overplants) — (Trung cấp) Đúng bài kinh điển diện tích hợp của hình chữ nhật bằng sweep + cây phân đoạn trên trục $y$ nén; khớp trực tiếp với ví dụ trong bài.
Bò Lười — Gold (lazycowg) — (Kỳ cựu) Sweep nâng cao kết hợp cây phân đoạn và khoảng cách Manhattan (xoay 45°), luyện tư duy biến đổi bài toán trước khi quét.