Temukan garis lurus terpanjang antara dua titik di permukaan poligon

8

Bentuk saya adalah poligon yang agak cekung, dan saya ingin tahu diameter maksimalnya. Saya membayangkan garis lurus antara dua titik pada permukaan poligon, sehingga garis tersebut tidak melewati luar poligon.

Apakah ada algoritma umum untuk ini?

Dalam kasus saya, saya tertarik pada 2D. Bentuk saya adalah tumor dalam gambar medis. Jadi kita juga dapat mengasumsikan: 1 centroid selalu di dalam poligon. 2 kerapatan titik tinggi, yaitu titik berikutnya selalu dekat dengan yang sebelumnya.

mathematics computational-geometry polygon jiggunjer
sumber
1
Ada kaliper berputar tetapi itu hanya berfungsi untuk poligon cembung. Kalau tidak, Anda dapat menggunakannya sebagai dasar untuk solusi brute force.
ratchet freak
3
Nah jika O (n ^ 2) bukan masalah maka uji semua pasangan titik
joojaa
2
Sebenarnya ini sedikit lebih terlibat: bayangkan 2 kamar dihubungkan oleh koridor sempit. Diameter terbesar akan berakhir di dinding di ruangan yang berbeda dan tidak akan berakhir pada titik mana pun.
ratchet freak
1
Apakah Anda mencari algoritme yang berfungsi dalam kasus paling umum atau dapatkah dibatasi misalnya pada kasus 2D? Ini mungkin lebih mudah untuk diselesaikan dengan beberapa informasi atau batasan tentang input. Anda menggunakan kata poligon yang mungkin mengisyaratkan hanya 2D, juga pertanyaan yang Anda tautkan menyarankan kasus 2D. Juga, apakah cukup untuk mempertimbangkan jarak vertex-vertex atau apakah Anda membutuhkan hasil yang benar untuk kasus-kasus seperti ratchet freak yang disebutkan dalam komentarnya ?
Nero
2
Juga, saya khawatir tentang bentuk C yang memiliki ketebalan sangat sempit, tetapi interior terbuka yang besar; dan jari-jari kelengkungan yang besar. Diameternya (seperti yang Anda definisikan) akan sangat kecil karena itu hanya akan menjadi pendek yang mengikuti kelengkungan C. Namun kanker nodul ukuran ukuran interior akan cukup memprihatinkan. Jadi mungkin lambung cembung yang Anda inginkan untuk menghitung diameter.
Wyck

Jawaban:

1

Saya tidak punya jawaban yang pasti untuk ini, karena jawabannya jauh dari sepele. Saya menyarankan agar Anda melihat geometri komputasi karena ini jelas merupakan masalah visibilitas - tebakan saya adalah bahwa solusi sudah ada. Ide saya sendiri adalah: untuk setiap segmen garis dalam poligon, temukan bagian yang terlihat dari segmen garis lainnya dan kemudian pilih pasangan titik yang paling jauh terpisah. Tautan inspirasional: Wikipedia tentang 'visibilitas poligon' .

luar
sumber