Testen, ob ein polygon einfach oder Komplex
Für ein polygon definiert als eine Folge von (x,y) Punkte, wie kann ich erkennen, ob es Komplex ist oder nicht? Ein Komplexes polygon hat Schnittpunkte mit sich selbst, wie gezeigt:
Gibt es eine bessere Lösung als die überprüfung jedes paar, das hätte eine Zeit-Komplexität von O(N2)?
InformationsquelleAutor der Frage Drew Noakes | 2010-10-22
Schreibe einen Kommentar
Du musst angemeldet sein, um einen Kommentar abzugeben.
Gibt es sweep-Methoden bestimmen kann diese viel schneller als eine brute-force-Ansatz. Darüber hinaus können Sie verwendet werden, zu brechen, ein nicht-einfaches polygon in mehrere einfache Polygone.
Für details, siehe dieser Artikelinsbesondere code zum testen für ein einfaches polygon.
InformationsquelleAutor der Antwort Reed Copsey
Sehen Bentley-Ottmann-Algorithmus für einen sweep basierend O((N + I)log N) Methode.
Wobei N die Anzahl der Liniensegmente und I die Anzahl der Schnittpunkte.
InformationsquelleAutor der Antwort Amit Prakash
In der Tat, kann dies in linearer Zeit verwenden Chazelle die triangulation Algorithmus. Entweder triangulates das polygon-oder das polygon wird nicht einfach.
InformationsquelleAutor der Antwort Chao Xu