Sweep Line

Sweep line adalah paradigma di mana kita membayangkan sebuah garis vertikal/horisontal “menyapu” ruang dari kiri ke kanan, mengolah setiap event saat garis melewatinya. Banyak masalah geometri dan interval dapat direduksi menjadi daftar event terurut. Pada Chapter ini kita akan mempelajari dua aplikasi kanonik: menghitung tumpang-tindih interval maksimum dan menemukan irisan semua interval. Kita juga akan menyentuh masalah lanjutan seperti luas persegi panjang gabungan (union area).

Intuisi: Garis Sapu dan Event #

Aturan #

Setiap interval [l, r] menghasilkan dua event:

Event buka di x = l: mulai aktif.
Event tutup di x = r + 1: berhenti aktif.

Sortir semua event berdasarkan koordinat, lalu proses berurutan. Antara dua event berturut-turut, jumlah interval aktif tetap konstan.

flowchart LR A["Event: (1, +1), (4, -1), (2, +1), (6, -1), (3, +1), (5, -1)"] --> B["Sort: (1,+1), (2,+1), (3,+1), (4,-1), (5,-1), (6,-1)"] B --> C["Sweep: aktif=1,2,3,2,1,0"] C --> D["Max overlap = 3"]

Aplikasi 1: Tumpang-Tindih Maksimum #

Aturan #

Diberikan n interval [l_i, r_i] (inclusive integer). Cari jumlah maksimum interval yang tumpang-tindih di satu titik.

Mekanisme: Event dengan Tanda +1 / -1 #

Konversi setiap interval ke dua event: (l_i, +1) dan (r_i + 1, -1). Sortir berdasarkan koordinat. Saat menyapu, akumulasi jumlah aktif; lacak maksimum.

Kode: Max Overlap #

cpp
#include <iostream>
#include <vector>
#include <algorithm>

int max_overlap(const std::vector<std::pair<int,int>>& intervals) {
    std::vector<std::pair<int,int>> events;
    for (auto [l, r] : intervals) {
        events.push_back({l, +1});
        events.push_back({r + 1, -1});
    }
    std::sort(events.begin(), events.end());
    int active = 0, best = 0;
    for (auto [x, delta] : events) {
        active += delta;
        best = std::max(best, active);
    }
    return best;
}

int main() {
    std::vector<std::pair<int,int>> intervals = {
        {1, 5}, {2, 6}, {3, 8}, {7, 9}, {4, 10}
    };
    std::cout << "max overlap = " << max_overlap(intervals) << '\n';
    return 0;
}

Output yang Dihasilkan:

text

max overlap = 4

Baris events.push_back({l, +1});: event buka — interval mulai aktif di koordinat l.
Baris events.push_back({r + 1, -1});: event tutup — interval berhenti aktif tepat setelah r. Gunakan r+1 agar konsisten untuk interval integer inclusive.
Baris std::sort(events.begin(), events.end());: sort berdasarkan koordinat x. Bila ada event di koordinat yang sama, sort menurut delta (secara default, -1 sebelum +1 — tutup dulu sebelum buka; ini benar untuk definisi “tumpang-tindih” yang ketat).
Baris active += delta;: akumulasi perubahan saat garis melewati event.
Baris best = std::max(best, active);: simpan maksimum interval aktif.
Hasil 4: titik x = 4 dicakup oleh interval [1,5], [2,6], [3,8], [4,10] = 4 interval. Sesuai.

Aplikasi 2: Irisan Semua Interval #

Aturan #

Diberikan n interval, temukan irisan mereka — sebuah interval [L, R] di mana L = max(l_i) dan R = min(r_i). Bila L > R, irisan kosong.

Mekanisme #

Sangat sederhana: iterasi semua interval, lacak L dan R.

Kode: Intersection of All Intervals #

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

std::pair<long long,long long> intersect_all(const std::vector<std::pair<long long,long long>>& intervals) {
    long long L = LLONG_MIN, R = LLONG_MAX;
    for (auto [l, r] : intervals) {
        L = std::max(L, l);
        R = std::min(R, r);
    }
    return {L, R};
}

int main() {
    std::vector<std::pair<long long,long long>> a = {{1, 10}, {3, 8}, {4, 9}, {2, 6}};
    auto [L, R] = intersect_all(a);
    std::cout << "intersection = [" << L << ", " << R << "]\n";

    std::vector<std::pair<long long,long long>> b = {{1, 5}, {6, 10}};
    auto [L2, R2] = intersect_all(b);
    if (L2 > R2) std::cout << "intersection = empty\n";
    else std::cout << "intersection = [" << L2 << ", " << R2 << "]\n";
    return 0;
}

Output yang Dihasilkan:

text

intersection = [4, 6]
intersection = empty

Baris long long L = LLONG_MIN, R = LLONG_MAX;: inisialisasi sentinel — L sangat kecil, R sangat besar. Setiap interval akan mempersempit.
Baris L = std::max(L, l);: ambil batas kiri terbesar (paling ketat).
Baris R = std::min(R, r);: ambil batas kanan terkecil (paling ketat).
Hasil [4, 6]: dari {1,10, 3,8, 4,9, 2,6} — max(left) = 4, min(right) = 6. Sesuai.
Hasil empty: {1,5, 6,10} — max(left) = 6, min(right) = 5, dan 6 > 5, jadi irisan kosong.

Aplikasi 3: Luas Gabungan Persegi Panjang (Union Area) #

Aturan #

Diberikan n persegi panjang bersisi sejajar sumbu, hitung luas gabungan (wilayah yang diliputi minimal satu persegi panjang). Solusi naif: O(n²). Dengan sweep line + segment tree: O(n² log n) atau O(n log n) dengan lazy segment tree.

Mekanisme: Sweep Vertikal + Segment Tree #

Untuk setiap persegi panjang [x1, x2] × [y1, y2], buat dua event vertikal: (x1, +1, y1, y2) (buka) dan (x2, -1, y1, y2) (tutup).
Sort event berdasarkan x.
Antara dua x berturut-turut, lebar Δx konstan. Luas = (total panjang y aktif) × Δx.
Gunakan segment tree dengan lazy propagation pada sumbu y (setelah coordinate compression) untuk melacak total panjang y yang aktif.

Kode: Union Area (Sederhana, O(n²)) #

cpp
#include <iostream>
#include <vector>
#include <algorithm>

double union_area(std::vector<std::tuple<double,double,double,double>> rects) {
    // rects: (x1, y1, x2, y2)
    std::vector<std::pair<double,int>> events;
    std::vector<double> ys;
    for (auto [x1, y1, x2, y2] : rects) {
        events.push_back({x1, +1});
        events.push_back({x2, -1});
        ys.push_back(y1);
        ys.push_back(y2);
    }
    std::sort(events.begin(), events.end());
    std::sort(ys.begin(), ys.end());
    ys.erase(std::unique(ys.begin(), ys.end()), ys.end());

    std::vector<int> cnt(ys.size() - 1, 0);
    double area = 0;
    double prev_x = events.front().first;
    for (auto [x, delta] : events) {
        double dx = x - prev_x;
        double active_y = 0;
        for (size_t i = 0; i + 1 < ys.size(); ++i) {
            if (cnt[i] > 0) active_y += (ys[i+1] - ys[i]);
        }
        area += dx * active_y;
        prev_x = x;
        // Update cnt untuk semua segmen y yang ter-cover event ini
        for (auto [x1, y1, x2, y2] : rects) {
            if (x1 == x || x2 == x) {
                // Cek apakah event ini cocok
            }
        }
        // Implementasi sederhana: loop rects untuk apply delta
        for (auto& [rx1, ry1, rx2, ry2] : rects) {
            if (rx1 == x && delta == +1) {
                for (size_t i = 0; i + 1 < ys.size(); ++i) {
                    if (ys[i] >= ry1 && ys[i+1] <= ry2) cnt[i]++;
                }
            } else if (rx2 == x && delta == -1) {
                for (size_t i = 0; i + 1 < ys.size(); ++i) {
                    if (ys[i] >= ry1 && ys[i+1] <= ry2) cnt[i]--;
                }
            }
        }
    }
    return area;
}

int main() {
    std::vector<std::tuple<double,double,double,double>> rects = {
        {0, 0, 4, 4},   // 16
        {2, 2, 6, 6},   // 16, overlap 4 dengan yang pertama
        {1, 1, 3, 3}    // 4, fully inside pertama
    };
    std::cout << "union area = " << union_area(rects) << '\n';
    return 0;
}

Output yang Dihasilkan:

text

union area = 28

Baris std::vector<std::pair<double,int>> events;: daftar event sweep vertikal. Setiap persegi panjang menghasilkan dua event: buka di x1, tutup di x2.
Baris std::vector<double> ys;: koordinat y unik untuk diskritisasi sumbu vertikal.
Baris std::vector<int> cnt(ys.size() - 1, 0);: cnt[i] = jumlah persegi panjang aktif yang menutupi segmen ys[i]..ys[i+1].
Baris double active_y = 0;: jumlah panjang y yang sedang aktif (cnt[i] > 0).
Baris area += dx * active_y;: kontribusi luas antara dua event x berturut-turut = lebar × tinggi aktif.
Block update cnt: saat event di x, untuk setiap persegi panjang yang dimulai/berakhir di x, update cnt pada segmen y yang sesuai. O(n) per event — total O(n²).
Hasil 28: persegi panjang [0,0,4,4] (luas 16) ∪ [2,2,6,6] (luas 16, overlap 4 dengan pertama) ∪ [1,1,3,3] (luas 4, sepenuhnya di dalam pertama). Union = 16 + 16 - 4 (overlap) + 0 (third fully inside) = 28. Sesuai.

Ringkasan #

Sweep line = konversi interval/objek ke daftar event terurut, lalu proses berurutan.
Max overlap: dua event per interval (+1 di l, -1 di r+1). Sort, akumulasi, lacak max. O(n log n).
Intersection of all: L = max(l_i), R = min(r_i). Kosong bila L > R. O(n).
Union area rectangles: sweep vertikal + segment tree pada y (coordinate compression + lazy). O(n log n) atau O(n²) untuk versi sederhana.
Banyak soal geometri 1D dan 2D dapat direduksi ke sweep line — kuasai pola “sort + akumulasi”.