Bagaimana cara mencari tahu apakah dua kurva Bezier planar berpotongan? Dengan "andal" maksud saya tes akan menjawab "ya" hanya ketika kurva berpotongan, dan "tidak" hanya ketika mereka tidak berpotongan. Saya tidak perlu tahu parameter apa yang ditemukan pada persimpangan. Saya juga ingin menggunakan angka floating-point dalam implementasi.
Saya menemukan beberapa jawaban pada StackOverflow yang menggunakan kurva-kotak terikat untuk tes: ini bukan apa yang saya cari karena tes tersebut dapat melaporkan persimpangan bahkan jika kurva tidak memotong.
Hal terdekat yang saya temukan sejauh ini adalah " irisan pembatas " oleh Sederberg dan Meyers tetapi "hanya" membedakan antara persimpangan paling-paling-satu dan dua-atau-lebih, sedangkan saya ingin tahu apakah ada paling-nol dan satu atau lebih persimpangan.
sumber
Jawaban:
Cara alternatif untuk merumuskan masalah adalah dengan mendefinisikan fungsi yang memberikan jarak antara titik pada dua kurva, sebagai fungsi dari parameter kurva. Kemudian cobalah mencari minimum global dari fungsi ini. Jika kurva bersilangan, minimum akan menjadi nol; kalau tidak minimum akan menjadi jarak positif.
Untuk menjadi eksplisit, diberikan sepasang kurva 2D yang didefinisikan oleh , tentukan jarak-kuadrat sebagaic1,c2:[0,1]→R2
Untuk kurva kubik, fungsi kemudian menjadi polinomial tingkat enam dalam dua variabel. Anda kemudian dapat menerapkan teknik optimasi numerik seperti metode simpleks atau keturunan gradien konjugat . Sayangnya fungsi tersebut dapat memiliki beberapa minimum lokal (ini bukan cembung), jadi pengoptimalan tidak mudah. Mungkin ada metode optimasi yang lebih khusus yang tersedia untuk polinomial, tetapi ini bukan bidang keahlian bagi saya.f
sumber
[Penafian: Saya pikir yang berikut ini harus berfungsi tetapi belum benar-benar mengkodekannya sendiri]
Saya tidak bisa memikirkan metode "sepele" untuk menghasilkan jawaban ya / tidak, tetapi berikut ini akan menjadi pendekatan yang masuk akal untuk solusi praktis untuk pertanyaan itu.
Anggap kurva kita masing-masing adalah A (s) dan B (t) dengan titik kontrol { A0, A1..An } dan { B0, .. Bm }.
Menurut saya, mengingat sepasang Beziers 2D yang ingin kami tentukan apakah berpotongan atau tidak, ada enam hal yang perlu dipertimbangkan:
Kasus di mana kita bisa "sepele" menentukan mereka tidak berpotongan.
Kasus di mana mereka berpotongan beberapa kali dan kita dapat "dengan mudah" menentukan mereka pasti berpotongan setidaknya sekali (tapi kita tidak benar-benar peduli di mana persimpangan itu terjadi)
Salah satu Beziers adalah degenerasi, yaitu titik (yang akan terjadi jika semua titik kontrol identik). Kita dapat berasumsi kita sudah menangani kasus di mana keduanya merupakan poin.
Satu atau lebih kurva ditutup, mis. A0 == An. Untuk membuat hidup lebih sederhana, kami akan membagi kurva tersebut dan mulai lagi.
Ada banyak titik persimpangan karena setiap subset dari "induk" Bezier dan mereka tumpang tindih.
Kami tidak yakin tentang kasus-kasus di atas dan perlu penyelidikan lebih lanjut
Untuk saat ini kami akan mengabaikan 3 dan 4, tetapi kembali lagi nanti.
Kasus 1
Saat Anda mengisyaratkan dalam pertanyaan Anda, jika masing-masing kotak pembatas dari titik kontrol A dan B ), tidak berpotongan, maka kurva tidak dapat berpotongan. Jelas ini adalah tes penolakan cepat tetapi terlalu konservatif. Seperti yang mungkin Anda ketahui, dengan kurva Bezier, cembung cembung pada titik kontrolnya membentuk ikatan yang lebih erat. Dengan demikian kita dapat menggunakan teknik sumbu pemisah untuk memutuskan apakah lambung A dan B tidak berpotongan. (misalnya seperti yang ditunjukkan di Wikipedia :)
Kasus 2
Jika uji kasus 1 gagal, Anda dapat memeriksa keberadaan "sepele" persimpangan. Sekarang mungkin ada cara yang lebih baik untuk melakukan ini, tetapi pendekatan berikut, yang relatif murah, terjadi pada saya:
Pertimbangkan hanya kurva A:
Jika kita melakukan hal yang sama dengan kurva B kita mendapatkan kasus (mungkin) berikut:
Kasus 6
Kasus 3 & 5
Di sinilah menjadi sedikit lebih membosankan.
Jika "case 3" berhasil melewati tes "case 1", menurut saya Anda harus menyelesaikan untuk persimpangan yang sebenarnya. Mengingat bahwa ada proses sederhana untuk memetakan titik kontrol N dari Bezier, A (s), ke titik N-1 dari Bezier, A '(s), mewakili turunan pertamanya maka (asalkan dilakukan perawatan untuk relatif jarang, apa yang disebut situasi "merosot" di mana turunan pertama tidak nol), maka iterasi Newton (pada satu dimensi) dapat digunakan untuk menemukan solusi potensial.
Perhatikan juga bahwa, karena titik kontrol A '(s) terikat pada nilai turunan, ada potensi untuk melakukan eliminasi awal beberapa kasus.
Kasus 5 tampaknya relatif tidak mungkin, jadi mungkin hanya jika setelah beberapa kali rekursi tidak ada bukti konklusif, orang dapat mencoba setiap titik akhir A terhadap kurva B dan sebaliknya. Ini hanya akan memberikan bukti persimpangan - bukan bukti non-persimpangan.
sumber