Bagaimana saya menguji apakah poligon monoton sehubungan dengan garis arbitrer?

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

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

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$

algorithms computational-geometry 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 .

L

$L$

x

$x$

O (1)

$\mathcal{O}(1)$

HdM

@HdM: Baris L tidak diberikan sebagai bagian dari input.

Tsuyoshi Ito

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. $v_i=(x_i, y_i)$ $i$ $α_i$ $(v_iv_{i+1})$ $β_i$ $v_i$ atan2

α_{i} = atan2 (y_{i + 1} - y_{i}, x_{i + 1} - x_{i})

$α_i=\mbox{atan2}(y_{i+1}-y_i,x_{i+1}-x_i)$

β_{i} = α_{i + 1} - α_{i} + {\begin{cases} 0 & if α_{i + 1} \geq α_{i} \\ 2 π & if α_{i + 1} < α_{i} \end{cases}

$β_i = α_{i+1}-α_i+ \left\{ \begin{array}{ll} 0 & \mbox{ if } α_{i+1} ≥ α_i \\ 2π & \mbox{ if } α_{i+1} < α_i \\ \end{array} \right.$

Balikkan urutan simpul jika tidak dalam urutan berlawanan arah jarum jam, yaitu jika tidak negatif. ( : berlawanan arah jarum jam, : searah jarum jam). $s=\sum_i β_i-nπ$ $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} \lor α_{j} < δ) jika α_{j + 1} < α_{j}

$(δ<α_{j+1} ∨ α_j<δ) \mbox{ if } α_{j+1}<α_j$

(α_{j} < δ < α_{j + 1}) jika α_{j} < α_{j + 1}

$(α_j<δ<α_{j+1}) \mbox{ if } α_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 . $O(n^2)$ $α_j\mbox{ mod }π$ $γ_1,…γ_m$ $δ∈\{\frac{γ_1}2,\frac{γ_1+γ_2}2,…,\frac{γ_{m-1}+γ_m}2,\frac{γ_m+π}2\}$

Jika Anda telah menemukan beberapa maka ada dan dengan kemiringan . Jika tidak tidak monoton. $δ$ $L$ $-1/\tan δ$ $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

Bagaimana saya menguji apakah poligon monoton sehubungan dengan garis arbitrer?

Jawaban: