Belajar Algoritm - Geometric Algorithms

#Pendahuluan

Setelah di episode 22 kita membahas String Algorithms, pada episode ini kita membahas Geometric Algorithms — algoritma untuk masalah geometri 2D. Computational geometry adalah bidang yang menggabungkan matematika dan komputer untuk menyelesaikan masalah spasial: convex hull, intersection, proximity, dan partitioning.

Geometric algorithms muncul di berbagai aplikasi nyata: game collision detection, map routing, CAD (Computer-Aided Design), robot path planning, dan GIS (Geographic Information System). Memahami algoritma dasar geometri memberikan fondasi untuk bidang-bidang ini.

#Convex Hull

Convex hull dari sekumpulan titik adalah poligon cembung minimum yang mencakup semua titik — seperti karet gelang yang direntangkan di sekitar titik-titik tersebut.

#Graham Scan

Graham scan memilih titik paling bawah (atau paling kiri jika seri), mengurutkan sisanya berdasarkan angle, lalu membangun hull dengan stack:

python

def graham_scan(points):
    def cross(o, a, b):
        return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])
    
    # Titik paling bawah
    start = min(points, key=lambda p: (p[1], p[0]))
    points.remove(start)
    
    # Sort berdasarkan angle dari start
    points.sort(key=lambda p: (math.atan2(p[1]-start[1], p[0]-start[0]), 
                                -((p[0]-start[0])**2 + (p[1]-start[1])**2)))
    
    hull = [start, points[0]]
    for p in points[1:]:
        while len(hull) > 1 and cross(hull[-2], hull[-1], p) <= 0:
            hull.pop()
        hull.append(p)
    
    return hull

Cross product cross(o, a, b): positif = belok kiri, negatif = belok kanan, nol = segaris. Graham scan memastikan semua belokan adalah belok kiri (counter-clockwise).

#Monotone Chain

Monotone chain lebih sederhana: sort titik berdasarkan x (lalu y), bangun hull bawah dan hull atas secara terpisah.

python

def monotone_chain(points):
    points = sorted(set(points))
    if len(points) <= 1:
        return points
    
    def cross(o, a, b):
        return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])
    
    # Hull bawah
    lower = []
    for p in points:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    
    # Hull atas
    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    
    return lower[:-1] + upper[:-1]

#Kompleksitas

Algoritma	Time	Space
Graham scan	O(n log n)	O(n)
Monotone chain	O(n log n)	O(n)

Note

Monotone chain lebih mudah diimplementasikan dan lebih robust terhadap numerical precision — tidak perlu menghitung angle. Untuk production, monotone chain sering lebih disukai.

#Line Segment Intersection (Sweep Line)

Sweep line memindahkan garis virtual dari kiri ke kanan, memproses event (titik awal/akhir segmen) secara berurutan, dan memeriksa intersection hanya pada segmen yang aktif (sedang "dilalui" oleh garis).

python

def segments_intersect(p1, p2, p3, p4):
    """Cek apakah segmen p1p2 dan p3p4 berpotongan"""
    def orientation(p, q, r):
        val = (q[1]-p[1])*(r[0]-q[0]) - (q[0]-p[0])*(r[1]-q[1])
        if val == 0: return 0
        return 1 if val > 0 else 2
    
    def on_segment(p, q, r):
        if (min(p[0],r[0]) <= q[0] <= max(p[0],r[0]) and
            min(p[1],r[1]) <= q[1] <= max(p[1],r[1])):
            return True
        return False
    
    o1 = orientation(p1, p2, p3)
    o2 = orientation(p1, p2, p4)
    o3 = orientation(p3, p4, p1)
    o4 = orientation(p3, p4, p2)
    
    if o1 != o2 and o3 != o4:
        return True
    if o1 == 0 and on_segment(p1, p3, p2): return True
    if o2 == 0 and on_segment(p1, p4, p2): return True
    if o3 == 0 and on_segment(p3, p1, p4): return True
    if o4 == 0 and on_segment(p3, p2, p4): return True
    return False

#Aplikasi

Game collision detection: deteksi kapan objek berpotongan.
Map/GIS: menentukan apakah dua jalan berpotongan.
CAD: validasi desain geometris.

#Aplikasi Geometric Algorithms

Algoritma	Aplikasi
Convex hull	Collision detection, shape analysis
Sweep line	Intersection detection, polygon fill
Closest pair	Proximity queries, clustering
Point in polygon	Spatial containment queries

Tip

Untuk game development, spatial indexing (quadtree, R-tree) menggunakan geometric algorithms untuk mempercepat collision detection — bukan cek semua pasang objek, tetapi hanya objek yang berdekatan secara spasial.

#Penutup

Pada episode 23 ini, kalian telah memahami:

Convex hull: Graham scan dan monotone chain — O(n log n) untuk menemukan boundary cembung.
Sweep line: memproses event secara horizontal untuk deteksi intersection.
Applications: collision detection, GIS, CAD, robot path planning.
Computational geometry menggabungkan matematika dan komputer secara elegan.

Di episode 24 selanjutnya kita akan membahas Randomized Algorithms — Las Vegas vs Monte Carlo, QuickSelect, randomized hashing, dan skip list. Sampai jumpa di episode 24!