Bagaimana saya menguji apakah poligon monoton sehubungan dengan garis arbitrer?

16

Definisi : Sebuah poligon dalam bidang disebut monoton sehubungan dengan garis lurus , jika setiap garis ortogonal ke memotong paling banyak dua kaliPLLP

Diberikan poligon , apakah mungkin untuk menentukan apakah ada garis sehingga poligon adalah monoton sehubungan dengan ? Jika ya, bagaimana?L P LPLPL

Sebelumnya, saya bertanya pertanyaan yang terkait (di mana saya bertanya bagaimana untuk menentukan apakah poligon adalah monoton sehubungan dengan baris tertentu), tapi sekarang saya tertarik dalam kasus ketika adalah tidak diberikan atau ditentukan di muka.L

com
sumber
Mengapa tidak memutar / menggeser sistem koordinat sedemikian rupa sehingga menjadi sumbu dan kemudian menjalankan algoritme yang lama lagi? Pekerjaan tambahan harus dikelola dalam . LxO(1)
HdM
4
@HdM: Baris L tidak diberikan sebagai bagian dari input.
Tsuyoshi Ito

Jawaban:

16

Itu mungkin.

Pertimbangkan Anda poligon dan pertimbangkan simpul "cekung". Mereka menentukan dengan tepat garis mana yang akan memotong poligon lebih dari dua kali. Pada gambar berikut ini saya menandai interval (merah) dari sudut terlarang. Jika Anda menempatkan mereka bersama-sama dan melihat lubang di disk merah, maka ada sudut resmi (berwarna biru). Poligon tersebut kemudian monoton sehubungan dengan garis kemiringan (berwarna hijau).δ1/tanδ

Asteroid

Sekarang algoritma.

Biarkan menjadi simpul ke- dari poligon. Pertama hitung sudut absolut tepi dan sudut dalam dari simpul . Gunakan fungsi yang tersedia dalam semua bahasa pemrograman yang baik.vi=(xi,yi)iαi(vivi+1)βiviatan2

αi=atan2(yi+1yi,xi+1xi)
βi=αi+1αi+{0 if αi+1αi2π if αi+1<αi

Balikkan urutan simpul jika tidak dalam urutan berlawanan arah jarum jam, yaitu jika tidak negatif. ( : berlawanan arah jarum jam, : searah jarum jam).s=iβinπs=2πs=2π

Berikut ini hanya untuk sudut dalam yang lebih besar dari yaitu, . Yang merah di foto saya. Tujuannya adalah untuk menemukan sudut yang tidak ada dalam modulo . Yaitu sedemikian sehingga untuk semua sedemikian rupa sehingga :mπβj>πδj[αj+1,αj]πjβj>π

(δ<αj+1αj<δ) jika αj+1<αj
(αj<δ<αj+1) jika αj<αj+1

di mana sini nilai normal di . Kasus kedua sesuai dengan interval yang melampaui (jadi kali ini harus "di dalam").αjαj[0,π)πδ

Mungkin ada cara yang lebih cepat untuk melakukan ini tetapi satu di adalah mengurutkan nilai ke dan untuk menguji .HAI(n2)αj mod πγ1,...γmδ{γ12,γ1+γ22,...,γm-1+γm2,γm+π2}

Jika Anda telah menemukan beberapa maka ada dan dengan kemiringan . Jika tidak tidak monoton.δL.-1/berjemurδP

jmad
sumber
Perangkat lunak apa yang Anda gunakan untuk membuat ilustrasi itu?
jojman
@ Jojman Saya tidak ingat tapi itu harus GIMP, saya tidak ingat program lain yang akan saya gunakan saat itu.
jmad