Dla wielokąta zdefiniowanego jako sekwencja (x, y) punktów, jak mogę wykryć, czy jest on złożony, czy nie? Złożona wielokąt przecinania się ze sobą, jak pokazano poniżej:Sprawdzanie, czy wielokąt jest prosty lub złożony
jest lepszym rozwiązaniem niż sprawdzanie każdej pary, które mają Złożoność obliczeniowa O (N)?
Istnieją metody usuwania, które mogą określać to znacznie szybciej niż podejście typu "brute force". Ponadto można je wykorzystać do rozbicia nie prostego wielokąta na wiele prostych wielokątów.
Aby uzyskać szczegółowe informacje, patrz this article, w szczególności ten code to test for a simple polygon.
Link do kodu to http://geomalgorithms.com/a09-_intersect-3.html#simple_Polygon() wersja z auto-escaped ze znacznika nie działa. –
Zobacz Bentley Ottmann Algorithm dla metody opartej na wymianie O ((N + I) log N) dla tego. Gdzie N to liczba segmentów linii, a I to liczba punktów przecięcia.
W rzeczywistości można to zrobić w czasie liniowym, używając algorytmu triangulacji Chazelle'a. Albo trianguluje wielokąt, albo dowiaduje się, że wielokąt nie jest prosty.
Poza tym, że istnieje kilka cennych praktycznych implementacji Chazelle z powodu jego złożoności do wdrożenia. –
Cóż, jeśli wielokąt zostanie wprowadzony przez użytkownika za pomocą komuksu, prawdopodobnie nie będziesz miał więcej niż 100 wierzchołków. W takim przypadku najpierw skorzystam z prostego rozwiązania i zobaczę, czy to wystarczy. –
@Nikita, pytanie mogło być mylące w tym względzie. Użytkownik może również edytować istniejący wielokąt z tysiącami wierzchołków. Niezależnie od tego nadal chcę wiedzieć, jakie jest najlepsze podejście. –