Line Sweep Algorithms

Banyak persoalan geometri komputasi dapat diselesaikan dengan paradigma sweep line: bayangkan sebuah garis (biasanya vertical) bergerak dari kiri ke kanan melintasi plane. Saat garis melintasi suatu titik kritis (event), struktur data di-maintain untuk merefleksikan state saat ini. Persoalan menjadi lebih sederhana karena kita hanya fokus pada “titik-titik event” dan tidak perlu memproses seluruh plane. Aplikasi klasik: luas union of rectangles, closest pair of points, segment intersection detection, dan area of polygon. Pada Chapter ini kita mengimplementasikan luas union of rectangles dengan sweep line + coordinate compression, dan membahas aplikasi lain.

Aturan: Event-Driven Processing #

Sweep line bekerja dengan konsep event: titik di mana state berubah. Setiap event diproses saat garis sweep melintasinya. Contoh untuk union of rectangles:

Event “start rectangle”: masukkan y-range [y1, y2] ke active set.
Event “end rectangle”: keluarkan y-range dari active set.
Luas segmen [prev_x, cur_x] × active_y_height diakumulasi.

Karena kita hanya perlu tahu berapa tinggi y yang aktif di antara dua event x, tidak perlu membuat grid 2D — cukup koordinat kritis y dan counter.

Mekanisme: Coordinate Compression + Active Counter #

Untuk union of rectangles:

Identifikasi koordinat kritis y: kumpulkan semua y1 dan y2 dari rectangles, sort, unique. Misal hasilnya ys = [y_0, y_1, ..., y_{m-1}]. Setiap segmen (y_i, y_{i+1}) adalah “slot”.
Buat events: untuk setiap rectangle, dua event: start (x1, y1, y2, is_start=true) dan end (x2, y1, y2, is_start=false).
Sort events by x (mulai dulu sebelum selesai bila x sama, agar overlap di boundary dihitung benar).
Sweep: iterasi events. Untuk setiap event:
- Bila e.x > prev_x: hitung luas segmen [prev_x, e.x] × active_height. Tambahkan ke total.
- Update count[i] untuk setiap slot (ys[i], ys[i+1]) yang berada di [e.y1, e.y2]. Start: +1. End: -1.
- prev_x = e.x.
Active height: jumlah ys[i+1] - ys[i] untuk semua i dengan count[i] > 0.

flowchart TD A["Sort events by x"] --> B["Iterate events"] B --> C{"e.x > prev_x?"} C -- Ya --> D["Compute width = e.x - prev_x<br/>Compute active_y_height<br/>total_area += width * active_y_height"] C -- Tidak --> E["Skip area computation"] D --> F["Update count for y-range"] E --> F F --> G["prev_x = e.x"] G --> B

Implementasi Luas Union of Rectangles #

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

struct Event {
    int x;
    int y1, y2;
    bool is_start;  // true = masuk, false = keluar
    bool operator<(const Event& o) const {
        if (x != o.x) return x < o.x;
        // mulai dulu sebelum selesai untuk overlap yang tepat di boundary
        return is_start > o.is_start;
    }
};

int main() {
    // Rectangles: (x1, y1, x2, y2)
    std::vector<std::vector<int>> rects = {
        {1, 1, 4, 4},
        {3, 2, 6, 5},
        {5, 1, 7, 3}
    };

    std::vector<Event> events;
    for (const auto& r : rects) {
        events.push_back({r[0], r[1], r[3], true});   // start at x1
        events.push_back({r[2], r[1], r[3], false});  // end at x2
    }
    std::sort(events.begin(), events.end());

    std::vector<int> ys;
    for (const auto& r : rects) { ys.push_back(r[1]); ys.push_back(r[3]); }
    std::sort(ys.begin(), ys.end());
    ys.erase(std::unique(ys.begin(), ys.end()), ys.end());

    int m = ys.size();
    std::vector<int> count(m - 1, 0);  // count[i] = jumlah rectangle covering (ys[i], ys[i+1])

    long long total_area = 0;
    int prev_x = events[0].x;
    for (const auto& e : events) {
        if (e.x > prev_x) {
            int width = e.x - prev_x;
            int active_h = 0;
            for (int i = 0; i + 1 < m; ++i) {
                if (count[i] > 0) active_h += ys[i + 1] - ys[i];
            }
            total_area += (long long)width * active_h;
        }
        int ya = std::lower_bound(ys.begin(), ys.end(), e.y1) - ys.begin();
        int yb = std::lower_bound(ys.begin(), ys.end(), e.y2) - ys.begin();
        for (int i = ya; i < yb; ++i) {
            count[i] += e.is_start ? 1 : -1;
        }
        prev_x = e.x;
    }

    std::cout << "Luas union rectangles = " << total_area << '\n';

    std::cout << "\nVerifikasi manual: 9 + 9 + 4 - 2 - 1 = 19\n";
    return 0;
}

Output yang Dihasilkan:

text
Luas union rectangles = 19

Verifikasi manual: 9 + 9 + 4 - 2 - 1 = 19

Bedah Kode Baris-per-Baris #

struct Event { int x, y1, y2; bool is_start; }: event menyimpan posisi x, rentang y yang terdampak, dan tipe (mulai/akhir rectangle).
operator<: sort event by x naik. Bila x sama, prioritaskan is_start = true lebih dulu (start sebelum end). Ini agar saat dua rectangle berbagi boundary x, kita masukkan dulu rectangle baru sebelum mengeluarkan yang lama — sehingga active height tidak pernah nol di tengah boundary.
std::vector<int> ys: kumpulkan semua y1 dan y2, sort, unique. Inilah coordinate compression — mengubah koordinat y kontinu menjadi slot-slot diskret.
std::vector<int> count(m - 1, 0): untuk setiap slot (ys[i], ys[i+1]), simpan berapa rectangle yang aktif covering slot ini. count[i] > 0 artinya slot aktif (di-cover).
for (const auto& e : events): sweep line utama. Iterasi event berurutan.
if (e.x > prev_x): bila ada jarak x antara event sebelumnya dan event saat ini, hitung luas segmen tersebut.
width = e.x - prev_x: lebar segmen x.
active_h = Σ (ys[i+1] - ys[i]) for count[i] > 0: jumlah tinggi slot-slot yang aktif. Slot dihitung sebagai ys[i+1] - ys[i] (jarak antar y kritis).
total_area += width * active_h: luas segmen = lebar × tinggi aktif. Tambahkan ke total.
ya = lower_bound(ys, e.y1): indeks awal y-range event. yb = lower_bound(ys, e.y2): indeks akhir.
for (int i = ya; i < yb; ++i) count[i] += e.is_start ? 1 : -1: untuk setiap slot (ys[i], ys[i+1]) yang berada dalam [e.y1, e.y2], increment (start) atau decrement (end) counter. Setelah loop, count[i] merefleksikan berapa rectangle covering slot i.
prev_x = e.x: update posisi sweep line.
Verifikasi:
- R1: (1,1)-(4,4), area 3×3 = 9.
- R2: (3,2)-(6,5), area 3×3 = 9.
- R3: (5,1)-(7,3), area 2×2 = 4.
- Overlap R1 ∩ R2: x∈[3,4], y∈[2,4], area = 1×2 = 2.
- Overlap R2 ∩ R3: x∈[5,6], y∈[2,3], area = 1×1 = 1.
- Union = 9 + 9 + 4 - 2 - 1 = 19. ✓

Kompleksitas #

Aspek	Sederhana (count array)	Optimal (segment tree)
Sort events	O(n log n)	O(n log n)
Coordinate compression	O(n log n)	O(n log n)
Per event	O(m) untuk update count	O(log m)
Total	O(n²) worst	O(n log n)

Untuk demo, count array sederhana cukup. Untuk kompetisi dengan n ≥ 10^5, segment tree dengan lazy tag wajib.

Aplikasi Lain Sweep Line #

1. Closest Pair of Points #

Sweep vertical line, maintain set of points dalam strip lebar d (jarak terkecil saat ini). Untuk setiap titik baru, cek hanya titik-titik dalam strip y-range [y-d, y+d] (≤ 7 titik). Kompleksitas O(n log n).

2. Segment Intersection #

Sweep x, maintain ordered set of active segments (diurutkan by y saat ini). Saat dua segment berdekatan dalam set dan bertukar urutan, periksa intersection. Kompleksitas O((n + k) log n) di mana k = jumlah intersection.

3. Interval Scheduling / Coverage #

Sort intervals by start time.
Sweep time, track kapan interval aktif.
Hitung panjang waktu covered, max overlap, dll.

4. Point in Polygon (Ray Casting) #

Sweep sinar horizontal dari titik query. Hitung berapa kali polygon edge disilang. Bila ganjil → dalam polygon.

5. Area of Polygon (Shoelace via Sweep) #

Alternatif untuk hitung luas polygon non-self-intersecting. Lebih sederhana dengan rumus shoelace langsung.

Ringkasan #

Sweep line = paradigma event-driven processing untuk masalah geometri.
Konsep inti: kumpulkan “events” (titik kritis), sort, proses berurutan dengan struktur data pendukung.
Union of rectangles: events = rectangle start/end. Coordinate compression y. Active counter per slot. Luas = Σ (width × active_height).
Kompleksitas optimal O(n log n) dengan segment tree, atau O(n²) dengan count array sederhana.
Aplikasi lain: closest pair of points, segment intersection, interval scheduling, point in polygon.
Generalisasi: koordinat compression + ordered structure (set/map) + event loop.