Algorytm O (n) wykrywający, czy linia przecina wypukły wielokąt, polega na sprawdzeniu, czy jakakolwiek krawędź wielokąta przecina linię i czy liczba przecięć jest nieparzysty lub parzysty.Asymptotycznie optymalny algorytm do obliczania, czy linia przecina wielokąt wypukły
Czy istnieje asymptotycznie szybszy algorytm, np. O (log n) jeden?
Odpowiedź lhf jest bliska poprawności. Oto wersja, która powinna naprawić problem z jego.
Niech wielobok ma wierzchołki v0, v1, ..., vn w kolejności przeciwnej do ruchu wskazówek zegara. Niech punkty x0 i x1 będą na linii.
Uwaga dwie rzeczy: Po pierwsze, znalezienie przecięcia dwóch linii (i określenie jego istnienia) można wykonać w stałym czasie. Po drugie, ustalenie, czy punkt jest po lewej, czy po prawej stronie linii, może być wykonane w stałym czasie.
Będziemy postępować zgodnie z tą samą podstawową ideą lhf, aby uzyskać algorytm O (log n). Przypadki bazowe są wtedy, gdy wielokąt ma 2 lub 3 wierzchołki. Oba mogą być obsługiwane w stałym czasie.
Określa, czy linia (v0, v (n/2)) przecina linię (x0, x1).
Przypadek 1: Nie przecinają się.
W tym przypadku linia, którą jesteśmy zainteresowani, znajduje się na lewo lub na prawo od linii dzielącej wielokąt, dzięki czemu możemy powrócić do tej połowy wielokąta. W szczególności, jeśli x0 znajduje się po lewej stronie (v0, v (n/2)), wówczas wszystkie wierzchołki w prawej "połowie", {v0, v1, ... v (n/2)} znajdują się po tej samej stronie (x0, x1) i dlatego wiemy, że nie ma przecięcia w "połowie" wielokąta.
Przypadek 2: przecinają się.
Ten przypadek jest nieco trudniejszy, ale możemy w dalszym ciągu zawężać punkt przecięcia do jednej "połówki" wielokąta w stałym czasie. Istnieją 3 subcases:
przypadków 2.1: przecięcia między punktami V0 i v (n/2)
W gotowe. Linia przecina wielokąt.
Przypadek 2.2: Przecięcie jest bliżej v0 (czyli poza wielokąta na stronie V0 za)
Sprawdź, czy linia (x0, x1) przecina się z linią (v0, v1).
Jeśli tak się nie stanie, linia nie przecina się z wielokątem.
Jeśli tak, znajdź skrzyżowanie, str. Jeśli p znajduje się na prawo od linii (v0, v (n/2)), to powracaj do prawej "połowy" wielokąta, {v0, v1, ..., v (n/2)}, w przeciwnym razie rekurencyjnie w lewo "połowa" {v0, v (n/2), ... vn}.
Podstawową ideą w tym przypadku jest to, że wszystkie punkty wielokąta znajdują się po jednej stronie linii (v0, v1). Jeśli (x0, x1) odchodzi od (v0, v1) po jednej stronie jej przecięcia z (v0, v (n/2)). Wiemy, że po tej stronie nie może być żadnego przecięcia z wielokątem.
przypadku 2.3: przecięcie jest bliżej v (n/2)
Ten przypadek jest obsługiwany w sposób podobny do Case 2.2, ale stosując odpowiednie sąsiada v (n/2).
Skończyliśmy. Dla każdego poziomu wymaga to dwóch przecięć linii, sprawdzenia lewy-prawy i ustalenia, gdzie znajduje się punkt na linii. Każda rekursja dzieli liczbę wierzchołków o 2 (technicznie dzieli je co najmniej o 4/3). Otrzymujemy więc czas działania O (log n).
Skarbce mogą okazać się przydatne.
Przypomnijmy, że wypukła część przestrzeni afinicznej jest przecięciem wszystkich jej hiperplan kopert: możesz uzyskać przybliżenie swojego wielokąta (przeczytaj "wielobok wypukły"), biorąc pod uwagę tylko przecięcie podzbioru koperty hiperpłaszczyzny, przetestuj przecięcie linii z tym przybliżeniem i doprecyzuj w razie potrzeby.
Wszystko to działa lepiej, jeśli spodziewasz się małej liczby skrzyżowań.
Wystarczy znaleźć punkt A znajdujący się po lewej stronie linii i kolejny punkt po prawej stronie. Pozostaje pytanie, jak szybko znaleźć te punkty.
weź losowo dwa punkty A i B z wypukłego poligonu.
jeśli te dwa punkty są najdalej na innej stronie linii, linia przecina poligon, w przeciwnym razie nie
Przy okazji można również znaleźć faktyczne punkty przecięcia w O (log n).
Algorytm jest nieprawidłowy. 1) sekwencje wierzchołków AB i BA mogą nie być poprawne dla wyszukiwania trójskładnikowego. 2) Posiadanie punktów o maksymalnej odległości od l na tych polilinii nie gwarantuje, że punkty znajdują się po przeciwnych stronach badanej linii. Nawet gdy linia przecina wielokąt. –
Albo odległość nie powinna być absolutna (tak, że z jednej strony jest ujemna, z drugiej dodatnia), albo z jednej strony l przechodzi przez A i przez B na drugą. – Sarmun
Pomógłaby odległość bezwzględna, ale nie we wszystkich przypadkach. Zobacz http://jurajblaho.wz.cz/path2816.png. Rozkaz A-> B w CW nie jest odpowiedni do wyszukiwania trójskładnikowego, ponieważ rośnie, maleje i ostatecznie wzrasta. –
Myślę, że this article daje jasne rozwiązanie O (log n). Znajdź skrajności w kierunku prostopadłym do danej linii.
Proszę, wyjaśnij, co jest lewą/prawą połówką wielokąta. Być może lepiej byłoby użyć terminów v0-> vk lub vk-> v0 przy założeniu, że zamówienie to CCW. –
Za każdym razem, gdy mówiłem, że lewą/prawą połowę wyjaśniłem, wymieniłem wierzchołki w tej połowie. W szczególności, lewa połowa to wierzchołki, które nie znajdują się po prawej stronie linii (v0, v (n/2)), {v0, v1, ..., v (n/2)}. Używam terminu nie po prawej, ponieważ jest to zbiór wierzchołków po lewej stronie linii plus te na linii. –
+1 Dopóki nie znajdę kontrprzykładu. Uwaga: Myślę, że wyjaśnienie jest błędne. W kolejności CCW prawa połowa to v0-> v (n/2). –