Bab ini mempelajari algoritma untuk menyelesaikan masalah geometri. Ini adalah fondasi dari robotika, desain otomotif (CAD), hingga peta digital (GIS).
1. Lambung Cembung (Convex Hull)
Bayangkan Anda memiliki sekumpulan paku yang ditancapkan di papan kayu. Jika Anda melingkarkan karet gelang di sekeliling semua paku tersebut dan melepaskannya, bentuk yang terbentuk oleh karet gelang itu adalah Convex Hull.
- Aplikasi: Digunakan dalam pengenalan pola, statistik, dan untuk menentukan batas terluar dari sekumpulan data.
2. Triangulasi Delaunay
Ini adalah teknik membagi sekumpulan titik menjadi segitiga-segitiga sehingga tidak ada titik yang berada di dalam lingkaran luar (circumcircle) dari segitiga mana pun.
- Aplikasi: Digunakan untuk membuat mesh (jaring) dalam pemodelan 3D dan simulasi fisika (seperti aliran udara pada sayap pesawat). Segitiga yang dihasilkan cenderung “gemuk” dan tidak terlalu pipih, yang sangat ideal untuk perhitungan komputer.
3. Diagram Voronoi
Diagram ini membagi ruang menjadi wilayah-wilayah berdasarkan jarak ke sekumpulan titik tertentu. Setiap wilayah berisi semua titik yang lebih dekat ke “titik pusatnya” daripada ke titik pusat lainnya.
- Aplikasi: * Telekomunikasi: Menentukan menara seluler mana yang paling dekat dengan ponsel Anda.
- Layanan Darurat: Menentukan rumah sakit mana yang paling cepat menjangkau lokasi kecelakaan.
4. Deteksi Tabrakan (Collision Detection)
Ini adalah masalah geometri komputasi yang paling kritis dalam industri game dan robotika. Bagaimana komputer tahu bahwa dua objek yang bergerak (misalnya karakter game dan dinding) telah bersentuhan?
- Teknik: Menggunakan Bounding Boxes (kotak pembatas) atau Bounding Spheres untuk menyederhanakan bentuk kompleks, sehingga pengecekan tabrakan bisa dilakukan ribuan kali per detik.