Lambung cembung cenderung berguna di berbagai bidang, terkadang secara tidak terduga. Pada artikel ini, saya akan menjelaskan Ide dasar lambung cembung 2d dan cara menggunakan pemindaian graham untuk menemukannya. Jadi jika Anda sudah mengetahui tentang pemindaian graham, maka artikel ini bukan untuk Anda, tetapi jika belum, artikel ini akan membuat Anda terbiasa dengan beberapa konsep yang relevan.
Apa itu lambung cembung?
Lambung cembung suatu himpunan titik didefinisikan sebagai poligon cembung terkecil yang melingkupi semua titik dalam himpunan tersebut. Cembung artinya poligon tidak memiliki sudut yang ditekuk ke dalam.
Tepi merah pada poligon kanan menutup sudut yang bentuknya cekung, kebalikan dari cembung.
Cara yang berguna untuk memikirkan lambung cembung adalah analogi karet gelang. Misalkan titik-titik pada himpunan tersebut adalah paku-paku yang mencuat pada permukaan datar. Bayangkan sekarang, apa jadinya jika Anda mengambil karet gelang dan merentangkannya pada kuku. Mencoba untuk menyusutkan kembali ke panjang aslinya, karet gelang akan menutup paku, menyentuh paku yang paling menonjol dari tengah.
Untuk mewakili lambung cembung yang dihasilkan dalam kode, kami biasanya menyimpan daftar titik yang menahan karet gelang ini, yaitu daftar titik pada lambung cembung.
Perhatikan bahwa kita masih perlu mendefinisikan apa yang akan terjadi jika tiga titik terletak pada garis yang sama. Jika Anda membayangkan karet gelang itu ada titik yang menyentuh salah satu paku tetapi tidak menekuk sama sekali, berarti paku di sana terletak pada garis lurus di antara dua paku lainnya. Tergantung pada masalahnya, kita mungkin menganggap paku sepanjang garis lurus ini sebagai bagian keluaran, karena menyentuh karet gelang. Sebaliknya, kita juga bisa mengatakan bahwa paku ini tidak boleh menjadi bagian dari keluaran, karena bentuk karet gelangnya tidak berubah ketika kita melepasnya. Keputusan ini tergantung pada masalah yang sedang Anda kerjakan, dan yang terbaik adalah jika Anda memiliki masukan di mana tidak ada tiga titik yang segaris (hal ini sering terjadi pada tugas-tugas mudah untuk kompetisi pemrograman) maka Anda bahkan dapat mengabaikan masalah ini sepenuhnya.
Menemukan lambung cembung
Melihat sekumpulan titik, intuisi manusia memungkinkan kita dengan cepat mengetahui titik mana yang cenderung menyentuh lambung cembung, dan mana yang lebih dekat ke pusat sehingga menjauhi lambung cembung. Namun menerjemahkan intuisi ini ke dalam kode membutuhkan sedikit usaha.
Untuk menemukan convexhull dari sekumpulan titik, kita dapat menggunakan algoritma yang disebut Graham Scan, yang dianggap sebagai salah satu algoritma geometri komputasi pertama. Dengan menggunakan algoritma ini, kita dapat menemukan himpunan titik-titik yang terletak pada lambung cembung, beserta urutan kemunculan titik-titik tersebut saat mengelilingi lambung cembung.
Algoritmenya dimulai dengan menemukan sebuah titik, yang kita tahu pasti terletak pada lambung cembung. Titik dengan koordinat y terendah misalnya dapat dianggap sebagai pilihan yang aman. Jika ada beberapa titik pada koordinat y yang sama, kita ambil titik yang memiliki koordinat x terbesar (hal ini juga berlaku untuk titik sudut lainnya, misalnya x terendah pertama, lalu y terendah). ).
Selanjutnya, kita mengurutkan titik-titik lainnya berdasarkan sudut letaknya jika dilihat dari titik awal. Jika dua titik kebetulan berada pada sudut yang sama, titik yang lebih dekat ke titik awal harus muncul lebih awal dalam pengurutan.
Sekarang, ide dari algoritma ini adalah untuk menelusuri susunan yang telah diurutkan ini, menentukan untuk setiap titik, apakah ia terletak pada lambung cembung atau tidak. Artinya, untuk setiap tiga titik yang kita temui, kita tentukan apakah titik-titik tersebut membentuk sudut cembung atau cekung. Jika sudutnya cekung, maka kita tahu, bahwa titik tengah dari triplet ini tidak mungkin terletak pada lambung cembung.
(Perhatikan bahwa istilah sudut cekung dan cembung harus digunakan dalam kaitannya dengan keseluruhan poligon, hanya satu sudut saja yang tidak boleh cembung atau cekung, karena ada tidak akan ada arah referensi.)
Titik-titik yang terletak pada lambung cembung kita simpan dalam tumpukan, sehingga kita dapat menambahkan titik-titik jika kita mencapai titik-titik tersebut dalam perjalanan mengelilingi titik-titik yang telah diurutkan, dan menghapusnya jika kita mengetahui bahwa titik-titik tersebut membentuk sudut cekung.
(Sebenarnya, kita harus mengakses dua titik teratas tumpukan, oleh karena itu kita menggunakan std::vector sebagai gantinya, tapi kita menganggapnya sebagai semacam tumpukan, karena kita selalu hanya memikirkan beberapa elemen teratas.)
Dengan berkeliling pada susunan titik-titik yang diurutkan, kita menambahkan titik tersebut ke tumpukan, dan jika kemudian kita menemukan bahwa titik tersebut bukan milik convexhull, kita menghapusnya.
Kita dapat mengukur apakah sudut saat ini tertekuk ke dalam atau ke luar dengan menghitung perkalian silang dan memeriksa apakah hasilnya positif atau negatif. Gambar di atas menunjukkan triplet titik yang sudut yang dibentuknya cembung, oleh karena itu titik tengah dari ketiga titik tersebut tetap berada di tumpukan untuk saat ini.
Lanjut ke poin berikutnya, kita tetap melakukan hal yang sama: periksa apakah sudutnya cembung dan jika tidak, hilangkan titik tersebut. Kemudian lanjutkan menambahkan poin berikutnya dan ulangi.
Sudut yang ditandai dengan warna merah ini adalah cekung, oleh karena itu kita hilangkan titik tengah dari tumpukan karena tidak dapat menjadi bagian dari lambung cembung.
Bagaimana kita tahu bahwa ini akan memberi kita jawaban yang benar?
Menulis bukti yang teliti berada di luar cakupan artikel ini, tetapi saya dapat menuliskan ide dasarnya. Namun, saya mendorong Anda untuk terus maju dan mencoba mengisi kekosongan tersebut!
Karena kita menghitung perkalian silang di setiap sudut, kita tahu pasti bahwa kita mendapatkan poligon cembung. Sekarang kita tinggal membuktikan, bahwa poligon cembung ini benar-benar melingkupi semua titik.
(Sebenarnya, Anda juga perlu menunjukkan bahwa ini adalah poligon cembung terkecil yang memenuhi kondisi ini, namun hal ini dapat dengan mudah diperoleh dari titik sudut poligon cembung kita yang merupakan bagian dari himpunan awal poin.)
Misalkan, terdapat titik P di luar poligon yang baru saja kita temukan.
Karena setiap poin telah ditambahkan ke tumpukan satu kali, kita tahu bahwa P telah dihapus dari tumpukan pada suatu saat. Artinya, P bersama dengan titik-titik tetangganya, sebut saja O dan Q, membentuk sudut cekung.
Karena O dan Q terletak di dalam poligon (atau di perbatasannya), P harus terletak di dalam perbatasan juga, karena poligon berbentuk cembung dan sudut yang dibentuk O dan Q dengan P cekung terhadap poligon.
Jadi kami menemukan kontradiksi, yang berarti titik P seperti itu tidak mungkin ada.
Penerapan
Implementasi yang disediakan di sini memiliki fungsi convex_hull, yang mengambil std::vector yang berisi titik-titik sebagai std::pairs int dan mengembalikan std::vector lain yang berisi titik-titik yang terletak pada lambung cembung.
Analisis runtime dan memori
Selalu berguna untuk memikirkan algoritma kompleksitas dalam kaitannya dengan notasi Big-O, yang tidak akan saya jelaskan di sini, karena Michael Olorunnisola di sini telah melakukan pekerjaan yang jauh lebih baik dalam menjelaskannya daripada yang mungkin saya lakukan:
Pengurutan titik pada awalnya membutuhkan waktu O(n log n), namun setelah itu, setiap langkah dapat dihitung dalam waktu yang konstan. Setiap poin ditambahkan dan dihapus dari tumpukan paling banyak satu kali, ini berarti waktu proses terburuk terletak di O(n log n).
Penggunaan memori, yang saat ini terletak di O(n), dapat dioptimalkan dengan menghilangkan kebutuhan akan tumpukan dan melakukan operasi secara langsung pada larik masukan. Kita dapat memindahkan titik-titik yang terletak pada lambung cembung ke awal larik masukan dan menyusunnya dalam urutan yang benar, dan titik lainnya akan dipindahkan ke larik lainnya. Fungsi tersebut kemudian dapat mengembalikan hanya satu variabel bilangan bulat yang menunjukkan jumlah titik dalam larik yang terletak pada lambung cembung. Tentu saja, hal ini memiliki sisi negatifnya, yaitu fungsinya menjadi jauh lebih rumit, oleh karena itu saya menyarankan untuk tidak melakukannya, kecuali Anda membuat kode untuk sistem tertanam atau memiliki masalah memori yang serupa. Untuk sebagian besar situasi, trade-off probabilitas bug/penghematan memori tidak sepadan.
Algoritma Lainnya
Alternatif untuk Graham Scan adalah “algoritma Chan,” yang secara efektif didasarkan pada ide yang sama tetapi lebih mudah untuk diterapkan. Masuk akal untuk terlebih dahulu memahami cara kerja Graham Scan.
Jika Anda benar-benar merasa senang dan ingin mengatasi masalah dalam tiga dimensi, lihatlah algoritma yang diperkenalkan oleh Preparata dan Hong dalam makalah mereka tahun 1977 “Convex Hulls of Finite Sets of Points in Two and Three Dimensions”.
