LainnyaLanjutFase E–FE1E5

Convex Hull dengan Jarvis March

Jarvis March (gift wrapping) adalah algoritma geometri komputasi yang membentuk convex hull, yaitu poligon terkecil yang membungkus semua titik. Dimulai dari titik paling kiri, algoritma berulang kali memilih titik berikutnya yang membuat semua titik lain berada di sisi kiri garis (uji orientasi/left turn) hingga kembali ke titik awal. Visualisasi menampilkan sebaran titik dan garis hull yang terbentuk satu per satu.

Contoh kasus

Deteksi batas terluar objek dalam pengolahan citra atau menghitung area cakupan sinyal dari sekumpulan menara.

Silabus

Bungkus semua titik dengan poligon terkecil dengan berulang kali memilih titik terluar berikutnya.

Tujuan Belajar

·Memahami konsep convex hull (pembungkus terluar sekumpulan titik)
·Menjelaskan cara memilih titik hull lewat uji orientasi (belok kiri)
·Menerapkan pembentukan batas terluar dari sebaran titik

Cara Kerja

·Mulai dari titik paling kiri yang pasti bagian dari batas terluar.
·Dari titik sekarang, pilih titik berikutnya yang membuat semua titik lain ada di sisi kiri garis.
·Tarik garis ke titik terpilih sebagai bagian dari hull.
·Lanjutkan berputar sampai kembali ke titik awal, membentuk poligon pembungkus.

Prasyarat

·Koordinat titik pada bidang
·Konsep kiri/kanan garis (orientasi)

Contoh Nyata

·Deteksi batas terluar objek dalam pengolahan citra atau AI kamera.
·Menghitung area cakupan sinyal dari sekumpulan menara BTS.
·Menggambar area terluar yang mencakup semua pemain di peta game.

Kompleksitas O(n*h)