Bagaimana saya bisa menambah dan mengurangi poligon cembung?

Saya memiliki dua poligon 2D cembung yang saling tumpang tindih . Saya mencari algoritma untuk mengurangi dan menambahkannya . Hasilnya harus berupa poligon cekung tunggal atau (bahkan lebih baik) satu set cembung terbesar yang membentuk hasil cekung (misalnya segitiga).

( Kiri: Poligon tumpang tindih awal. Tengah: Poligon cekung yang dihasilkan setelah menambahkan. Kanan: Satu set poligon cembung yang membentuk hasil cekung. Di sini akan lebih baik untuk mendapatkan polong cembung lebih besar dari segitiga untuk alasan kinerja. Pengurangan dari dua poligon yang tumpang tindih akan mengarah ke gambar yang sama seperti di sebelah kiri tetapi dengan area yang tumpang tindih tidak menjadi bagian dari poligon yang dihasilkan.)

Bagaimana saya bisa melakukan ini?

TL; DR Anda harus mengimplementasikan operasi boolean menggunakan pohon BSP.

Nah, sepertinya kita berbicara tentang Geometri Padat Konstruktif di sini. Saya telah mengimplementasikan CSG di tingkat komersial jadi saya tahu satu atau dua hal tentang itu.

Makalah klasik tentang CSG disebut Menggabungkan BSP Pohon Menghasilkan Operasi Set Polyhedral , sejujurnya itu terlalu banyak untuk dijelaskan di sini, tetapi secara singkat algoritma membahas tentang poligon yang terletak pada bidang yang sama dengan partisi ruang biner, pada dasarnya membangun pohon BSP dari setiap mesh poligonal. Langkah kedua adalah menggabungkan pohon-pohon BSP; Anda cukup mengambil satu pohon dan memasukkannya ke yang lain. Algoritme kemudian mulai menjelaskan bagaimana menangani setiap node daun untuk membagi dan mengurangi node, node yang tidak diperlukan dalam bentuk akhir akan dihapus, yang lain akan diberikan induk yang sesuai.

Tapi tunggu! Makalah itu pada dasarnya berbicara tentang jerat poligonal dan bidang 3D, TIDAK?

Algoritme dapat digeneralisasi ke dimensi apa pun, jadi dalam kasus 2D Anda, mudah untuk menggunakan segmen garis daripada bidang sebagai partisi biner. Jadi setiap poligon akan dikonversi menjadi pohon BSP daripada keduanya akan digabungkan. Akhirnya Anda melintasi pohon yang dihasilkan untuk menghasilkan poligon akhir,

Perhatikan bahwa algoritma dan CSG ini secara umum tidak berurusan dengan rendering dan mesh wajah secara langsung dan tidak benar-benar rendering siap, jadi Anda perlu mengekstraksi wajah pohon BSP akhir. Saya juga menemukan ray menelusuri pendekatan yang lebih mudah untuk memberikan hasil CSG, Anda hanya perlu sinar untuk melintasi pohon alih-alih mengekstraksi dan benar-benar membelah wajah (ingat kita hanya berurusan dengan partisi biner).

Mengenai ketahanan numerik. Baik untuk dicatat bahwa ada dua jenis perhitungan geometris,

• Yang didasarkan pada konstruksi, Anda membangun bentuk berdasarkan hasil dari operasi sebelumnya. Misalnya y = sqrt(x)dan kemudian digunakan ydalam operasi baru. Ini disebut konstruksi; masalahnya adalah bahwa kesalahan numerik akan terakumulasi dengan cepat.
• Atau ada operasi yang menggunakan predikat sebagai gantinya, pada dasarnya alih-alih menggunakan konstruksi Anda hanya bertanya apakah suatu kondisi benar / salah dan menggunakan nilai yang sama dalam operasi yang berbeda. Tes klasik meliputi incircle dan tes orientasi; ini juga diduga kesalahan numerik terutama jika Anda menggunakan presisi tunggal atau ganda tetapi biasanya akan memberikan hasil yang jauh lebih baik. solusi lain yang bervariasi pada kecepatan dan akurasi yang ada. Berikut adalah salah satu makalah terbaru yang menghindari konstruksi dengan menggunakan geometri berbasis bidang untuk memberikan hasil yang akurat. Saya juga akan mengutip dari makalah:

Konsep representasi berbasis bidang dari jerat poligonal pertama kali dijelaskan oleh Sugihara dan Iri [SI89]. Representasi semacam ini memberikan satu keuntungan penting ketika datang ke tugas-tugas yang melibatkan mengubah topologi padatan yang diwakili oleh jerat seperti evaluasi ekspresi Boolean: tidak ada informasi geometri primer baru yang harus dibangun untuk mendapatkan polyhedron yang dihasilkan

Dan akhirnya saya ingin menambahkan, jika Anda ingin memulai implementasi CSP BSP Anda, saya akan merekomendasikan memulai pada BSP Faqs .

Mengikuti contoh Anda:

Pilih titik awal pada poligon A, dan kemudian mulai memeriksa untuk memotong tepi searah jarum jam (atau berlawanan arah jarum jam). Jika tidak ada persimpangan, tambahkan simpul sebelumnya ke poligon yang Anda hasilkan. Jika ada persimpangan, tambahkan titik di mana mereka berpotongan dengan poligon yang Anda hasilkan, dan kemudian mulai iterasi di atas poligon B, dalam urutan belitan yang sama. Lakukan hal yang sama, sekali lagi bertukar ke poligon A jika persimpangan terjadi.

Setelah Anda mengumpulkan semua simpul untuk poligon baru, lakukan algoritma triangulasi. The Metode telinga kliping mudah untuk menerapkan, tetapi ada yang lebih cepat pilihan di luar sana.

Penting: pastikan simpul yang Anda mulai tidak berada di dalam poligon lain (lihat artikel ini untuk poin dalam tes poligon).

Iterasi pada setiap sisi, untuk memeriksa persimpangan akan menjadi algoritma O (n ^ 2). Anda bisa mempercepatnya dengan terlebih dahulu menemukan simpul yang ada di dalam poligon lain, karena ujung-ujungnya yang terhubung dengan simpul-simpul itu adalah yang bersilangan.

Jika Anda ingin poligon cekung , cukup pilih tepi terdekat antara dua poligon input, dan tambahkan dua tepi baru:

Cembung menjadi sedikit lebih rumit:

Satu pendekatan bersifat iteratif karena menambahkan simpul dari poligon kedua ke yang pertama, satu demi satu, mengubah poligon pertama menjadi sebuah wadah yang mencakup segalanya.

Pada dasarnya:

• Iterasi melalui simpul poligon kedua.
• Untuk setiap titik V, beralih melalui tepi poligon pertama:
• Temukan "rentang" tepi yang semuanya menghadap ke puncak
• ambil pasangan terluar dari simpul yang menentukan rentang itu, dan hapus semua tepi dalam rentang yang menghubungkannya
• Gambar dua segmen baru dari simpul luar ke simpul baru (dari poligon kedua), memastikan bahwa tepi baru menghadap ke arah yang benar.
• Lanjutkan ke simpul berikutnya dari poligon kedua

Berikut diagram yang menggambarkan proses untuk simpul pertama:

Metode yang lebih cepat adalah menemukan daftar tepian pada setiap poligon yang tidak menghadap poligon lain, menghapus semua yang lain, dan menghubungkan titik-titik akhir dari strip garis yang tersisa satu sama lain.

Mungkin orang lain bisa berpadu dengan beberapa saran pengurangan.