Polygon Triangulation mit Löchern

Question

Ich suche nach einem Algorithmus oder einer Bibliothek (besser) ein Polygon in Dreiecke zu brechen. Ich werde mit dieser Dreiecke in einer Direct3D-Anwendung sein. Was sind die besten verfügbaren Optionen?

Hier ist, was ich bisher gefunden:

1. Ben Discoe Notizen
2. FIST: Fast Industrial-Strength Triangulation von Polygonen
3. Ich weiß, dass CGAL bietet Triangulation ist aber nicht sicher, ob es unterstützt Löcher.

Ich würde wirklich einige Meinungen von Menschen mit früheren Erfahrungen auf diesem Gebiet zu schätzen wissen.

Edit: Dies ist eine 2D-Polygon

.

Answer 1

Jonathan Shewchuk Triangle Bibliothek ist phänomenal; Ich habe es für die Automatisierung von Triangulation in der Vergangenheit verwendet. Sie können ihn bitten, zu versuchen, kleine / schmale Dreiecken, etc. zu vermeiden, so dass Sie kommen mit „gut“ Triangulation statt nur jede Triangulation.

Answer 2

Um Sie noch mehr Auswahl von Bibliotheken da draußen:

Polyboolean. Ich habe nie versucht, diese, aber es sieht vielversprechend aus: http: //www.complex-a5. ru / polyboolean / index.html

Allgemeiner Polygon Clipper. Dieser funktioniert sehr gut in der Praxis und tut Triangulation sowie Clipping und Löcher Löcher: http://www.cs.man.ac.uk/~toby/alan/software/

Meine persönliche Empfehlung: Verwenden Sie die Tesselation aus der GLU (OpenGL Utility Library). Der Code ist absolut solide, schneller als GPC und erzeugt weniger Dreiecke. Sie benötigen keine initialisiert OpenGL-Handle oder etwas Ähnliches müssen die lib verwenden.

Wenn Sie nicht wie die Idee zu OpenGL System Libs in einer DirectX-Anwendung enthalten gibt es eine Lösung auch: Laden Sie einfach die SGI OpenGL Referenzimplementierung Code und heben Sie den Triangulator von ihm. Es verwendet nur den OpenGL-Typedef-Namen und eine Hand voll von Aufzählungen. Das ist es. Sie können den Code extrahieren und einen Stand-alone-lib in einer Stunde machen oder zwei.

---

Generell mein Rat wäre, etwas zu verwenden, die alreay funktioniert und starten Sie nicht Ihre eigene Triangulation zu schreiben.

Es ist verlockend, Ihre eigene Rolle, wenn Sie über das Ohr-Clipping gelesen haben oder fegen-line-Algorithmus, aber Tatsache ist, dass algorithmische Geometrie-Algorithmen sind unglaublich schwer in einer Art und Weise zu schreiben, dass sie stabil arbeiten, niemals zum Absturz bringen und immer Rückkehr ein sinnvolles Ergebnis. Numerische Rundungsfehler akkumulieren und töten Sie am Ende.

Ich schrieb einen Triangulierungsalgorithmus in C für das Unternehmen mit denen ich arbeite. Erhalten des Kern-Algorithmus dauerte zwei Tage arbeiten. Bekommen es mit allen Arten von degenerierten Eingänge arbeiten dauerte weitere zwei Jahre (ich war nicht auf sie arbeiten Vollzeit, aber glauben Sie mir - ich es mehr Zeit damit verbracht, als ich sollte).

Answer 3

CGAL hat das Tool benötigen Sie: Constrained Triangulierungen

Sie einfach Grenzen des Polygons (incuding die Grenzen der Löcher) als Randbedingungen zur Verfügung stellen kann (am besten wäre, dass Sie alle Eckpunkte einfügen und dann die Einschränkungen als Paare von Vertex_handles angeben).

Sie können dann die Dreiecken der Triangulierung von jedem Traversierungsalgorithmus markieren: mit einem Dreieck fällt auf den unendlichen Vertex beginnen und markiert es als draußen zu sein, und jedes Mal, wenn Sie überqueren eine Einschränkung, wechseln Sie in den entgegengesetzten Tag (nach innen, wenn Sie zuvor wurden die Dreiecke als Außenseiter Tagging, außerhalb, wenn Sie Dreiecke als Insider vor) wurden Tagging.

Answer 4

Ich habe die poly2tri Bibliothek zu sein, genau zu finden, was ich für die Triangulation benötigt. Es produziert eine viel saubere Masche als andere Bibliotheken I (einschließlich libtess) versucht habe, und es tut auch Unterstützung Löcher. Es wurde zu einer Reihe von Sprachen umgewandelt. Die Lizenz ist New BSD , so können Sie es in jedem Projekt verwendet werden.

Poly2tri Bibliothek auf Google Code

Answer 5

Sie können die Löcher hinzufügen relativ leicht selbst. Grundsätzlich triangulieren zu der konvexen Hülle der Eingangspunkte, wie pro CGAL und löschen dann jedes Dreieck, dessen Inkreismittelpunkt liegt innerhalb eines der Polygone Loch (oder außerhalb jeder der äußeren Grenzen). Wenn du mit vielen Löchern in einer großen Datenmenge zu tun, Maskierungstechniken verwendet werden können, deutlich, diesen Prozess zu beschleunigen.

Bearbeiten: eine gemeinsame Erweiterung dieser Technik ist schwach Dreiecke auf dem Rumpf, um Unkraut, wobei die längste Kante oder kleinste Innenwinkel einen vorgegebenen Wert überschreitet. Dadurch wird einen besseren konkaven Rumpf bilden.

Answer 6

versuchen libtess2

https://code.google.com/p/libtess2/downloads/list

basierend auf dem ursprünglichen SGI GLU Tesselator (mit liberaler Lizenzierung). Löst einige Speichermanagementfragen rund um viele kleine mallocs.

Answer 7

Dies ist ein häufiges Problem in der Finite-Elemente-Analyse. Es heißt „automatische Netzgenerierung“ bezeichnet. Google gefunden diese Seite mit Links zu kommerziellen und Open-Source- Software. Sie vermuten in der Regel eine Art von CAD-Darstellung der Geometrie zu starten.

Answer 8

Eine weitere Option (mit einer sehr flexiblen Lizenz) ist in dem Hafen der Algorithmus von VTK:

vtkDelaunay2D

Dieser Algorithmus ziemlich gut funktioniert. Mit ihm direkt ist möglich, erfordert aber Links zu VTK, die mehr Aufwand haben, als Sie wollen (obwohl es viele andere nette Features, aber auch hat).

Es unterstützt Constraints (Löcher / Grenzen / etc) sowie Triangulation eine Oberfläche, die nicht notwendigerweise in der XY-Ebene ist. Es unterstützt auch einige Funktionen, die ich nicht an anderer Stelle gesehen haben (siehe die Hinweise auf Alpha-Werte).

Answer 9

Ich habe ein 3D-Polygon implementiert Triangulator in C # das Ohr Clipping-Methode verwendet wird. Es ist einfach zu bedienen, unterstützt Löcher, numerisch robust und unterstützt aribtrary (nicht selbstschneid) konvex / nicht-konvexen Polygonen.