Jak wykryć, czy wielokąt ma przekroje własne?

Question

Wyobraź sobie, że masz wielokąt 2D (a dokładniej 2D closed polygonal chain). Jak sprawdzisz, czy zawiera on samo-skrzyżowania? Może być wypukły lub wklęsły, zorientowany zgodnie lub przeciwnie do ruchu wskazówek zegara.

Teraz mogę po prostu uruchomić standardowy algorytm O(N log N), aby sprawdzić, czy dwa dowolne segmenty przecinają się. Uważam jednak, że ponieważ mamy jakąś dodatkową strukturę - kolejność segmentów i fakt, że każde dwa kolejne segmenty spotykają się w punktach końcowych - można opracować prostszy i szybszy (być może O(N)?) Algorytm.

Wszelkie pomysły?

Answer 1

Czy potrzebujesz po prostu sprawdzić, czy nie masz skrzyżowań, lub znaleźć wszystkie? Ten ostatni jest trudniejszy niż O(N log N), ponieważ możesz mieć skrzyżowania O(n^2) z segmentami n.

Jeśli potrzebujesz tylko dowiedzieć się, czy istnieją skrzyżowania własne, lub znaleźć niewielką ich liczbę, to spójrz na here. Ten artykuł wydaje się wymagać dokładnie tego, czego potrzebujesz, szczególnie w sekcji planaryzacji wieloboku. Wątpię, aby implementacja opisanego algorytmu była prosta lub opłacalna dla każdego problemu o rozsądnej wielkości. Ale taki algorytm istnieje. Zastrzeżenie: Nie próbowałem przejrzeć tego artykułu i zrozumieć go.