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


16

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.L L PP.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?L P LP.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.


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 . x O ( 1 )L.xO(1)
HdM

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

Odpowiedzi:


16

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 -1 / \ tan δ (na zielono). - 1 / tan δδ-1/dębnikδ

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.i α i ( v i v i + 1 ) β i v ivja=(xja,yja)jaαja(vjavja+1)βjavjaatan2

β i = α i + 1 - α i + { 0  jeśli  α i + 1α i 2 π  jeśli  α i + 1 < α i

αja=atan2(yja+1-yja,xja+1-xja)
βja=αja+1-αja+{0 gdyby αja+1αja2)π gdyby αja+1<αja

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 = - 2 π s = 2 πs=jaβja-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 :π β j > π δ j [ α j + 1 , α j ] π j β j > πmπβjot>πδjot[αjot+1,αjot]πjotβjot>π

( α j < δ < α j + 1 )  jeśli  α j < α j + 1

(δ<αjot+1αjot<δ) gdyby αjot+1<αjot
(αjot<δ<αjot+1) gdyby αjot<αjot+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 [0, π ) π δαjotαjot[0,π)πδ

Prawdopodobnie jest na to szybszy sposób, ale jednym z jest posortowanie wartości do i przetestowanie pod kątem .O(n2))αjot mod πγ1,γmδ{γ12),γ1+γ2)2),,γm-1+γm2),γm+π2)}

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


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
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.