Computational Geometry

Computational geometry adalah bidang algoritma yang berhubungan dengan bentuk geometris: titik, garis, polygon, dan bangun ruang. Aplikasi: computer graphics, GIS (geographic information systems), robot motion planning, computer-aided design. Beberapa algoritma klasik: convex hull (pembungkus terkecil berbentuk convex polygon), point in polygon (ray casting), segment intersection, closest pair of points, dan line arrangement. Inti dari computational geometry adalah operasi pada vektor 2D: cross product dan dot product. Pada Chapter ini kita mengimplementasikan convex hull dengan Andrew’s monotone chain, point in polygon dengan ray casting, dan deteksi segment intersection.

Aturan: Cross Product dan Orientasi #

Untuk tiga titik A, B, C di bidang 2D, cross product (B - A) × (C - A) memberi:

• Positif (> 0): C berada di kiri garis AB (orientasi counter-clockwise / CCW).
• Negatif (< 0): C di kanan garis AB (orientasi clockwise / CW).
• Nol (= 0): A, B, C kolinear.

cross(A, B, C) = (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x)

Cross product adalah pondasi hampir semua algoritma computational geometry. Gunakan long long (bukan int) untuk menghindari overflow koordinat besar.

Mekanisme: Andrew’s Monotone Chain untuk Convex Hull #

Algoritma Andrew’s monotone chain:

1. Sort titik by (x, y).
2. Bangun lower hull: iterasi titik dari kiri ke kanan. Untuk setiap titik baru p, selama dua titik terakhir di hull + p membentuk belokan kanan (cross ≤ 0), pop titik terakhir.
3. Bangun upper hull: iterasi titik dari kanan ke kiri, proses sama.
4. Gabung lower dan upper hull (tanpa duplikat endpoint).

Kompleksitas O(n log n) untuk sort + O(n) untuk hull construction.

Implementasi Convex Hull, Point in Polygon, Segment Intersection #

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

struct Point {
    long long x, y;
    Point(long long x = 0, long long y = 0) : x(x), y(y) {}
    Point operator-(const Point& o) const { return Point(x - o.x, y - o.y); }
    long long cross(const Point& o) const { return x * o.y - y * o.x; }
    long long dot(const Point& o) const { return x * o.x + y * o.y; }
    long long norm_sq() const { return x * x + y * y; }
};

// Cross product (b - a) x (c - a)
long long cross(const Point& a, const Point& b, const Point& c) {
    return (b - a).cross(c - a);
}

// Andrew's monotone chain for convex hull
std::vector<Point> convex_hull(std::vector<Point> pts) {
    int n = pts.size();
    if (n <= 1) return pts;
    std::sort(pts.begin(), pts.end(), [](const Point& a, const Point& b) {
        return a.x != b.x ? a.x < b.x : a.y < b.y;
    });
    pts.erase(std::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 <= 1) return pts;

    std::vector<Point> hull(2 * n);
    int k = 0;
    // Lower hull
    for (int i = 0; i < n; ++i) {
        while (k >= 2 && cross(hull[k-2], hull[k-1], pts[i]) <= 0) --k;
        hull[k++] = pts[i];
    }
    // Upper hull
    int lower = k + 1;
    for (int i = n - 2; i >= 0; --i) {
        while (k >= lower && cross(hull[k-2], hull[k-1], pts[i]) <= 0) --k;
        hull[k++] = pts[i];
    }
    hull.resize(k - 1);
    return hull;
}

// Point in polygon: ray casting algorithm
bool point_in_polygon(const std::vector<Point>& poly, const Point& p) {
    int n = poly.size();
    bool inside = false;
    for (int i = 0, j = n - 1; i < n; j = i++) {
        long long yi = poly[i].y, yj = poly[j].y;
        long long xi = poly[i].x, xj = poly[j].x;
        bool cond1 = (yi > p.y) != (yj > p.y);
        if (cond1) {
            double x_int = xi + (double)(p.y - yi) * (xj - xi) / (yj - yi);
            if (x_int > p.x) inside = !inside;
        }
    }
    return inside;
}

// Segment intersection (proper): returns true iff AB and CD intersect properly.
bool segments_intersect(const Point& a, const Point& b, const Point& c, const Point& d) {
    long long c1 = cross(a, b, c);
    long long c2 = cross(a, b, d);
    long long c3 = cross(c, d, a);
    long long c4 = cross(c, d, b);
    if (((c1 > 0 && c2 < 0) || (c1 < 0 && c2 > 0)) &&
        ((c3 > 0 && c4 < 0) || (c3 < 0 && c4 > 0))) return true;
    return false;
}

long long polygon_area(const std::vector<Point>& poly) {
    long long area2 = 0;
    int n = poly.size();
    for (int i = 0; i < n; ++i) {
        int j = (i + 1) % n;
        area2 += poly[i].cross(poly[j]);
    }
    return std::llabs(area2) / 2;
}

int main() {
    std::vector<Point> pts = {
        {0, 0}, {4, 0}, {4, 4}, {0, 4},
        {1, 1}, {3, 1}, {3, 3}, {1, 3},
        {2, 5},
        {-1, 2}
    };
    auto hull = convex_hull(pts);
    std::cout << "Convex hull (" << hull.size() << " vertices):\n";
    for (const auto& p : hull) std::cout << "  (" << p.x << ", " << p.y << ")\n";
    std::cout << "Luas hull = " << polygon_area(hull) << '\n';

    std::cout << "\nPoint in polygon test:\n";
    std::vector<Point> square = {{0, 0}, {4, 0}, {4, 4}, {0, 4}};
    std::cout << "  (2, 2) in square? " << (point_in_polygon(square, {2, 2}) ? "yes" : "no") << '\n';
    std::cout << "  (5, 5) in square? " << (point_in_polygon(square, {5, 5}) ? "yes" : "no") << '\n';
    std::cout << "  (-1, 2) in square? " << (point_in_polygon(square, {-1, 2}) ? "yes" : "no") << '\n';

    std::cout << "\nSegment intersection test:\n";
    Point a(0, 0), b(4, 4), c(0, 4), d(4, 0);
    std::cout << "  AB (0,0)-(4,4) vs CD (0,4)-(4,0): " << (segments_intersect(a, b, c, d) ? "intersect" : "no") << '\n';
    Point e(0, 0), f(4, 0), g(2, 1), h(2, 5);
    std::cout << "  EF (0,0)-(4,0) vs GH (2,1)-(2,5): " << (segments_intersect(e, f, g, h) ? "intersect" : "no") << '\n';
    return 0;
}

Output yang Dihasilkan:

Convex hull (6 vertices):
  (-1, 2)
  (0, 0)
  (4, 0)
  (4, 4)
  (2, 5)
  (0, 4)
Luas hull = 20

Point in polygon test:
  (2, 2) in square? yes
  (5, 5) in square? no
  (-1, 2) in square? no

Segment intersection test:
  AB (0,0)-(4,4) vs CD (0,4)-(4,0): intersect
  EF (0,0)-(4,0) vs GH (2,1)-(2,5): no

Bedah Kode Baris-per-Baris #

1. struct Point: struct titik 2D dengan operator - (subtraction) dan methods cross, dot, norm_sq. Memakai long long untuk koordinat agar cross product tidak overflow untuk koordinat besar.
2. cross(a, b, c): cross product (B-A) × (C-A). Positif bila C di kiri garis AB (CCW), negatif bila di kanan (CW), nol bila kolinear.
3. std::sort(pts.begin(), pts.end(), ...): sort titik by (x, y) lexicographically. Sort by x utama, y sebagai tiebreaker.
4. std::unique: buang titik duplikat setelah sort. Konvex hull dengan titik duplikat bisa error.
5. while (k >= 2 && cross(hull[k-2], hull[k-1], pts[i]) <= 0) --k: kondisi pop. Bila hull[k-2], hull[k-1], pts[i] tidak membentuk belokan kiri (CCW strict), pop hull[k-1]. Gunakan <= 0 (bukan < 0) untuk menangani titik kolinear — exclude intermediate kolinear untuk minimal hull.
6. Lower hull (kiri ke kanan): proses titik dari leftmost ke rightmost. Setelah loop, hull berisi lower boundary.
7. Upper hull (kanan ke kiri): mulai dari rightmost - 1 ke leftmost. lower = k + 1 memastikan upper hull tidak overwrite lower hull.
8. hull.resize(k - 1): buang titik terakhir yang sama dengan titik pertama (penutup loop).
9. point_in_polygon (ray casting): untuk setiap edge polygon, cek apakah sinar horizontal dari p (ke arah +x) melewati edge. Variabel inside di-toggle setiap kali sinar melewati edge. Bila ganjil pada akhir, p di dalam polygon.
10. (yi > p.y) != (yj > p.y): cek apakah edge (i, j) membentang melewati y = p.y. Hanya edge yang melintasi y=p.y yang dapat disilang sinar.
11. x_int = xi + (p.y - yi) * (xj - xi) / (yj - yi): x-coordinate titik perpotongan edge dengan garis horizontal y=p.y. Bila x_int > p.x, sinar melewati edge dari kiri ke kanan → toggle inside.
12. segments_intersect: cek apakah A dan B berseberangan sisi terhadap garis CD, dan C dan D berseberangan terhadap garis AB. Bila ya, kedua segment intersect. Gunakan tanda cross product: (c1 > 0 && c2 < 0) || (c1 < 0 && c2 > 0) artinya C dan D di sisi berbeda garis AB.
13. polygon_area (shoelace): rumus shoelace |Σ (x_i * y_{i+1} - x_{i+1} * y_i)| / 2. Memberi luas polygon (absolute).
14. Verifikasi convex hull:
    • Input: 10 titik, termasuk square luar (0,0), (4,0), (4,4), (0,4) + inner square (1,1), (3,1), (3,3), (1,3) + (2, 5) + (-1, 2).
    • Hull harus = 6 titik: (-1, 2), (0, 0), (4, 0), (4, 4), (2, 5), (0, 4). Inner square tidak masuk hull.
    • Luas = 20. Shoelace: vertices (-1,2), (0,0), (4,0), (4,4), (2,5), (0,4). Sum cross = ((-1)*0 - 0*2) + (0*0 - 4*0) + (4*4 - 4*0) + (4*5 - 2*4) + (2*4 - 0*5) + (0*2 - (-1)*4) = 0 + 0 + 16 + 12 + 8 + 4 = 40. Area = 40/2 = 20. ✓
15. Verifikasi point in polygon: (2,2) di dalam square → yes. (5,5) di luar → no. (-1, 2) di luar (x < 0) → no. ✓
16. Verifikasi segment intersection: AB diagonal (0,0)-(4,4), CD diagonal (0,4)-(4,0). Kedua diagonal square berpotongan di (2,2). EF horizontal di y=0, GH vertikal dari y=1 ke y=5 — keduanya tidak intersect karena EF di y=0 (di luar GH range). ✓

Kompleksitas #

Aplikasi #

1. Convex hull: collision detection, bounding volume, pattern matching.
2. Point in polygon: GIS (apakah lokasi dalam boundary), game development (click detection pada shape).
3. Segment intersection: CAD (deteksi tabrakan garis), graph layout.
4. Closest pair: clustering, sensor network, mimimal spanning tree heuristik.
5. Polygon triangulation: rendering, mesh generation untuk finite element method.

Ringkasan #

• Computational geometry = algoritma pada bentuk geometris 2D/3D.
• Cross product (B-A) × (C-A) memberi orientasi (CCW/CW/kolinear).
• Convex hull (Andrew’s monotone chain): sort + linear scan lower/upper hull. O(n log n).
• Point in polygon (ray casting): toggle counter saat sinar horizontal melewati edge. O(n).
• Segment intersection: cek dua segment berseberangan sisi terhadap masing-masing. O(1).
• Polygon area (shoelace): |Σ (x_i * y_{i+1} - x_{i+1} * y_i)| / 2. O(n).
• Selalu gunakan long long untuk koordinat dan cross product untuk menghindari overflow.