Jak sprawdzić, czy wielokąt jest monotoniczny względem dowolnej linii?

Definicja : Wielokąt w płaszczyźnie jest nazywany monotonicznym w stosunku do linii prostej , jeśli każda linia prostopadła do przecina najwyżej dwa razy. $P$ $L$ $L$ $P$

Biorąc pod uwagę wielokąt , czy można ustalić, czy istnieje jakaś linia tak że wielokąt jest monotoniczny względem ? Jeśli tak to jak? $P$ $L$ $P$ $L$

Wcześniej zadałem powiązane pytanie (gdzie zapytałem, jak ustalić, czy wielokąt jest monotoniczny w odniesieniu do konkretnej linii), ale teraz interesuje mnie przypadek, gdy nie jest podane lub określone z góry. $L$

algorithms computational-geometry

— com
źródło

Dlaczego po prostu nie obrócić / przesunąć układu współrzędnych, aby stał się osią a następnie ponownie uruchomić stary algorytm? Dodatkowa praca powinna być możliwa do zarządzania w .

L

$L$

x

$x$

O (1)

$\mathcal{O}(1)$

— HdM

@HdM: Linia L nie jest podawana jako część danych wejściowych.

— Tsuyoshi Ito

To jest możliwe.

Rozważmy wielokąt i rozważmy „wklęsłe” wierzchołki. Określają dokładnie, które linie przecinają wielokąt więcej niż dwa razy. Na poniższym rysunku zaznaczyłem przedziały (na czerwono) zakazanych kątów. Jeśli położysz je razem i zobaczysz dziurę w czerwonym dysku, wówczas dozwolone kąty (na niebiesko). Wielobok jest wówczas monotonny względem dowolnej linii nachylenia (na zielono). $δ$ $-1/\tan δ$

Asteroidy

Teraz algorytm.

Niech będzie tym wierzchołkiem wielokąta. Najpierw oblicz bezwzględny kąt krawędzi i kąt wewnętrzny wierzchołka . Użyj funkcji dostępnej we wszystkich dobrych językach programowania. $v_i=(x_i, y_i)$ $i$ $α_i$ $(v_iv_{i+1})$ $β_i$ $v_i$ atan2

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

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

β_{ja} = α_{ja + 1} - α_{ja} + {\begin{cases} 0 & gdyby α_{ja + 1} \geq α_{ja} \\ 2) π & gdyby α_{ja + 1} < α_{ja} \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.$

Odwróć kolejność wierzchołków, jeśli nie są one w kolejności przeciwnej do ruchu wskazówek zegara, tj. Jeśli nie jest ujemne. ( : przeciwnie do ruchu wskazówek zegara, : zgodnie z ruchem wskazówek zegara). $s=\sum_i β_i-nπ$ $s=-2π$ $s=2π$

Poniższe dotyczy tylko kątów wewnętrznych większych niż , to . Czerwone na moim zdjęciu. Celem jest znalezienie kąta który nie jest w modulo . Mianowicie takie, że dla wszystkich takie, że : $m$ $π$ $β_j>π$ $δ$ $∪_j[α_{j+1},α_j]$ $π$ $j$ $β_j>π$

(δ < α_{jot + 1} \lor α_{jot} < δ) gdyby α_{jot + 1} < α_{jot}

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

(α_{jot} < δ < α_{jot + 1}) gdyby α_{jot} < α_{jot + 1}

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

gdzie jest tutaj znormalizowaną wartością w . Drugi przypadek odpowiada interwałowi, który wykracza poza (więc tym razem musi znajdować się „wewnątrz”). $α_j$ $α_j$ $[0,π)$ $π$ $δ$

Prawdopodobnie jest na to szybszy sposób, ale jednym z jest posortowanie wartości do i przetestowanie pod kątem . $O(n^2)$ $α_j\mbox{ mod }π$ $γ_1,…γ_m$ $δ∈\{\frac{γ_1}2,\frac{γ_1+γ_2}2,…,\frac{γ_{m-1}+γ_m}2,\frac{γ_m+π}2\}$

Jeśli trzeba znaleźć następnie istnieje i nachylenia . W przeciwnym razie nie jest monotonne. $δ$ $L$ $-1/\tan δ$ $P$

— jmad
źródło

Jakiego oprogramowania użyłeś do zrobienia tej ilustracji?

— jojman

@ jojman Nie pamiętam, ale musiał to być GIMP, nie pamiętam żadnego innego programu, z którego wtedy korzystałbym.

— jmad