Einfache 2d-polygon-triangulation
Versuchen zu triangulieren eine Reihe von einfache 2d-Polygone, habe ich dieses Algorithmus:
- 1) Für jeden vertex im polygon berechnen Sie den Winkel zwischen den beiden Kanten verbunden
- 2) Sortieren Sie Scheitelpunkte durch eine Verringerung Winkel in Bezug auf das innere des Polygons
- 3), Wenn es weniger als 3 vertices in der Menge, wir sind fertig
- 4) Nehmen Sie den letzten Eckpunkt in der Menge und Ausgabe-Dreieck durch ihn und seine zwei Nachbarn
- 5) Entfernen Sie die vertex aus dem set
- 6) Aktualisieren Sie die Winkel der beiden Nachbarn
- 7) Springe zu 2
Ich habe es getestet, und fand es zu arbeiten, auch wirklich groß und kompliziert einfache 2d-polygon (es arbeiten nicht für ein polygon mit einem Loch oder selbst schneidende Polygone).
Gibt es Ausnahmefälle, die produzieren Entartete Ergebnis?
Funktioniert dieser Algorithmus ist eine bekannt?
Wenn nicht, möchte ich sicher sein, dass dieser Algorithmus ist rock-solid, aber ich habe nicht die mathematische hintergrund, um es zu beweisen.
Vielen Dank.
- Möglich, Duplikat der Parkettierung einer beliebigen polygon von Fliesen Dreiecke
Schreibe einen Kommentar
Du musst angemeldet sein, um einen Kommentar abzugeben.
Sie tun, eine version von "ear clipping" - Ansatz zur triangulation, siehe: http://en.wikipedia.org/wiki/Polygon_triangulation
Ihren Algorithmus schlägt fehl, wenn ein anderes polygon-vertex (sagen wir mal von der anderen Seite des Polygons) endet innerhalb des Dreiecks 'Ohr' du-form. Betrachten Sie dieses Beispiel:
Ihren Algorithmus wählt den ersten, und stellen Sie ein Dreieck mit den beiden benachbarten Ränder (in Verbindung mit der gestrichelten Linie). Aber dieses Dreieck enthält weiteren Eckpunkt (B) und ist eindeutig falsch.
Die generalisierte ear-clipping-Ansatz richtet sich auf die Feststellung Ohren können Sie die Clips aus, die nicht über alle enthaltenen Scheitelpunkte.
Einfache Konvexe Polygone in O(n)
Dies ist, wenn Sie behandeln möchten einfache Polygone wie Rechtecke, Fünfecke, Sechsecke, und so weiter. Hier können Sie nur einen Ausgangspunkt, und schließen Sie es an alle anderen Knoten. Dieser Algorithmus ist trivial und was ich wirklich wollte, war eine Allgemeine Lösung konnte Griff konkave Polygone mit Löchern.
Im Hinblick auf den Umgang mit komplexer Polygone wie Payne zur Verfügung gestellt...
Beliebigen Vieleck Dreieck in O(n log n)
Zwar gibt es algorithmen, die schneller laufen, die schneller algorithmen sehr kompliziert werden. Kirkpatrick et al. finden Sie einen Algorithmus, laufen in O(n log log n) und Chazelle hat es in O(n). Aber am einfachsten zu implementieren ist wohl der Seidel-Algorithmus läuft in O(n log n).
Den Algorithmus ist ein 3-Schritt-Prozess
C-Quelle
Wenn Sie interessiert sind, in der C-Quelle kann entnommen werden,University of North Carolina at Chapel Hill. Im Allgemeinen ist die code-Qualität ist gut, die Griffe Löcher, aber wahrscheinlich müssen massiert werden, um Ihre Bedürfnisse.
Wenn ich verstehen dich richtig, du bist abhacken Dreiecke beginnend mit dem kleinsten inneren Winkel. Dies kann fehlschlagen, wenn das polygon ist nicht konvex. Betrachten Sie ein polygon mit den Eckpunkten (in der Reihenfolge) an: (0,0) (10,9) (9,9) (9,10). Der kleinste Winkel ist die, die auf der Herkunft, aber Sie können nicht sicher abgeschnitten, das Dreieck.
(Wenn Ihr polygon ist konvex, dann können Sie einfach wählen Sie einen Scheitelpunkt entfernen Sie ein Dreieck, und wiederholen Sie. Also ich vermute, Sie wollen, dass Ihr Algorithmus funktioniert auch für nicht-konvexe Polygone.)
Habe ich zu lösen hatte ein ähnliches problem vor, und der resultierende code könnte nützlich sein, um Sie oder jemand anderes bei dieser Suche:
Demo: http://cecchi.me/portfolio/triangulation
Quelle: http://cecchi.me/js/point-picking.js.src
Die Quelle ist ein bisschen schmutzig zu werden, um zu ermöglichen, einfacher animation, aber Sie sollten in der Lage sein zu sehen, wie ich das problem gelöst Payne wies darauf hin, mit konvexen Polygonen (der relevante code fängt in Zeile 200). Beachten Sie, dass meine Lösung noch nicht erlauben, auch für komplexe Polygone.
Während Ohr-clipping funktioniert Recht gut, vereinfachende Methoden verlangsamen das polygon erhöht die Komplexität, da die überprüfung der gesamten polygon, wenn einstürzenden jedes Ohr wird immer langsamer.
Der ear-clipping-Algorithmus von
libgdxist ein guter Ort, um zu starten, da es sehr robust - mit FAUST (Fast Industrial-Strength Triangulation von Polygonen).Habe ich diese als Grundlage für die polygon Tesselation, dann werden zusätzliche räumliche Optimierungen für die Punkt-in-Dreieck-tests (
O(n log n)stattO(n^2)).Finden Sie unter:
Beachten Sie, dass der Algorithmus nicht explizit unterstützen Löcher, die Sie verwenden können Schlüsselloch Kanten zwischen den einzelnen Inseln, die werden dann richtig trianguliert.