Wie kann man feststellen, ob ein Delaunay-Dreieck intern oder extern ist?

Question

Ich schreibe ein Programm, das eine Implementierung der Medial Axis Extraction erfordert, zu der auch die Delaunay-Triangulation gehört. Externe Mittelachsen sind unerwünscht, daher sollen die entsprechenden externen Dreiecke entfernt werden. Glücklicherweise bin ich auf eine Seite mit vielen Diagrammen, auch ein Hinweis auf eine Methode zur Bestimmung innerer und äußerer Delaunay-Dreiecke ("basierend auf dem gestrichelten Linienumfang"), aber es ist nur ein Hinweis, ohne detaillierte Erklärung. Kennt jemand den Algorithmus?

EDIT: Ich vergaß zu erwähnen, dass die Anfangspunkte von der Grenze eines geschlossenen Polygons abgetastet werden. Meine Absicht ist es, zu bestimmen, ob jedes Delaunay-Dreieck innerhalb des Polygons liegt.

Answer 1

Diese Lösung setzt voraus, dass Sie über eine Datenstruktur verfügen, die die Delaunay-Triangulation mit Hilfe eines "virtuellen unendlichen Delaunay-Eckpunkts" wie folgt darstellt CGAL tut es ( siehe Details hier ).

Die Idee besteht darin, die Delaunay-Randkanten zu finden, d. h. die Kanten, die zwei aufeinanderfolgende Probepunkte miteinander verbinden, und dann die Delaunay-Triangulation zu "durchfluten", um die Delaunay-Flächen zu klassifizieren. Man weiß, dass der unendliche Eckpunkt außen liegt, so dass man seine Nachbarn (und die Nachbarn der Nachbarn usw.) als außen klassifizieren kann, solange man keine Grenzkanten überquert. Erreicht man eine Begrenzungskante, kann man das Nachbardreieck einfach als innen markieren und in ähnlicher Weise fortfahren.

Eingabe Menge von Punkten, die den Rand einer geschlossenen Form dicht abtasten, die auch Löcher enthalten kann
Ausgabe : Voronoi-Diagramm im Inneren der Form (Annäherung an die Mittelachse der Form)

1. Berechnen Sie die Delaunay-Triangulation Ihrer Punkte
2. Markieren Sie die Delaunay-Kanten, die zwei aufeinanderfolgende Probepunkte verbinden. (Siehe Seite 4-5 der vorliegenden Arbeit wie Sie dies mit einem lokalen Test an jeder Delaunay-Kante erreichen können)
3. Alle unendlichen Delaunay-Flächen als OUTSIDE klassifizieren und in eine Warteschlange stellen Q .
4. Während Q nicht leer ist
   1. Delaunay-Fläche f = Pop aus Q
   2. Für jedes nicht klassifizierte Nachbardreieck t von f
      • wenn die Delaunay-Kante, die von t et f markiert ist, klassifizieren. t als das Gegenteil von f
      • sonst klassifizieren t das gleiche wie f
      • drücken. t a Q
5. Für jede Delaunay-Kante e
   • wenn die beiden benachbarten Delaunay-Dreiecke d1 , d2 werden beide als INTERIOR eingestuft, wobei das Segment, das den Mittelpunkt von d1 et d2 .

Für eine Eingabe wie diese

kann die folgende Annäherung der Mittelachse berechnet werden:

Sie können überprüfen, wie sich diese Annäherung an die Mittelachse in der Praxis verhält, indem Sie die kostenlose Windows-Binärversion von Mesecina . Quellcode aquí .

Answer 2

Haben Sie schon einmal überlegt, eine andere Form der Triangulation zu verwenden, die keine externen Dreiecke erzeugt? Ich habe einmal einen Kurs belegt, in dem die theoretischen Aspekte der Polygon-Triangulation ausführlich erörtert wurden. Vielleicht gibt Ihnen ein Blick auf die Kurs-Website einen Einblick? http://cgm.cs.mcgill.ca/~godfried/unterricht/cg-web.html#Dreiecksbildung

Edit: Eigentlich ist mir gerade noch etwas eingefallen. Wenn Sie bereits das Polygon haben, das Sie zu triangulieren versuchen, können Sie den Satz von Green verwenden. Der Satz von Green verwendet den Umfang eines Polygons, um dessen Fläche zu berechnen! Noch wichtiger ist, dass Sie in diesem Fall anhand des Vorzeichens der Fläche feststellen können, ob ein Punkt auf der einen oder der anderen Seite einer Linie liegt. Bei Polygonen ist der Satz von Green ein einfaches Subtraktionsproblem. Nehmen Sie also einen beliebigen Punkt, von dem Sie WISSEN, dass er innerhalb des Polygons liegt, und berechnen Sie die Fläche gegen jede Kante des Polygons. Damit wissen Sie, auf welcher Seite jeder Linie sich Ihr Punkt befinden muss. Nehmen Sie nun einfach einen Punkt innerhalb jedes Dreiecks und machen Sie dasselbe. Wenn eines der Vorzeichen falsch ist, handelt es sich um ein äußeres Dreieck. (Hinweis: Je nach der Form Ihres Polygons kann es sein, dass dies nicht wirklich funktioniert. Bei konvexen Polygonen sollte es gut funktionieren, aber bei Konkavitäten könnte es zusätzliche Komplikationen geben).

Answer 3

Vielleicht mache ich hier zu viele Annahmen, aber es klingt so, als hätten Sie ein Polygon, das aus einer Reihe von Punkten besteht, und als würden Sie diese Punkte triangulieren. Sie wollen dann alle Dreiecke, die außerhalb des Polygons liegen, verwerfen, richtig?

Warum nicht einfach das Polygon triangulieren (mit monotoner Zerlegung oder etwas Ähnlichem), so dass keine externen Dreiecke entstehen? Ich nehme an, dass dies die Laufzeit erhöhen könnte (zuerst triangulieren in O(nlogn) Zeit und dann eine Delaunay-Triangulation in O(n^2) Zeit erstellen), aber vielleicht gibt es einen schnelleren Weg, dies zu tun.

Answer 4

Der Algorithmus, den sie präsentieren, scheint ein bisschen kaputt zu sein, wie sie in einer ihrer Abbildungen zeigen, und das könnte der Grund dafür sein, dass es keine nützlichen Zitate in Google Scholar zu geben scheint.

Die Anwendung des von ihnen vorgeschlagenen Algorithmus auf ein nicht konvexes Polygon zeigt, dass er nicht immer eine tatsächliche Triangulation wiederherstellt. http://www.cc.kyoto-su.ac.jp/~atsushi/Jun/Topics/Teddy/images/example2_2.jpg