Ich implementiere den Bowyer-Watson-Algorithmus wie unter @ vorgestell Wikipedia. In meiner Implementierung funktioniert alles so, wie ich es bis zum letzten Teil des Pseudocodes erwartet hätte:

for each triangle in triangulation // done inserting points, now clean up
     if triangle contains a vertex from original super-triangle
        remove triangle from triangulation

Wenn ich dem Pseudocode hier buchstäblich folge, kann es vorkommen, dass in meiner Delaunay-Triangulation Dreiecke fehlen.

Als Beispiel betrachten Sie bitte die Bilder unten. Die Sites, die ich trianguliere, werden als blaue Kreise gerendert. Die Dreiecke werden mit schwarzen Linien (ohne die Bildränder) gerendert und verbinden Standorte oder Eckpunkte von Begrenzungs- / Superdreiecken. Die Umkreise sind grau und ihre Mitten rot gerendert. Die Voronoi-Zellen sind jeweils mit einer anderen Farbe bemalt, um das Problem (hoffentlich) deutlicher zu machen.

Dieses Bild zeigt den Status der Triangulation, bevor die im obigen Pseudocode aufgeführten Schritte ausgeführt werden. Beachten Sie, dass sich zwei Eckpunkte des Superdreiecks jenseits der rechten und der unteren Bildhälfte befinden.

Diese Abbildung zeigt den Schritt nach dem Entfernen von Dreiecken, die Scheitelpunkte von Super-Dreiecken enthalten, ohne weitere Überlegungen:

Die oberen drei Eckpunkte sollten an der Stelle, an der sich die grünlich-bräunlichen Zellen treffen, ein neues Dreieck mit einem Umfangszentrum haben. Das Problem ist, dass sich der Eckpunkt, der im "Vorher" -Bild gezeigt wurde, innerhalb dieses Kreises befand, sodass die regelmäßige Verarbeitung des Algorithmus dieses Dreieck nie erzeugt hat.

Wie drücke ich diesen Randfall im Pseudocode aus, damit ich ihn überprüfen und lösen kann? Ich möchte einige schreckliche "Versuche jede Kombination von Sites, die ein Dreieck mit einem Superdreieck-Eckpunkt für eine gültige Umkreisschleife geteilt haben", vermeiden.

Ich habe die Zeitungen über Bowyer und Watson vor ein paar Jahren gelesen und werde sie bei Bedarf erneut lesen, um meine Antwort zu erhalten. Ich hatte gehofft, dass (1) jemand anderes die Antwort zur Verfügung hat und (2) ich die Antwort mit Stack Overflow nachschlagen könnte, falls ich jemals wieder auf diese Frage stoße.

Bearbeite

So habe ich eine relativ günstige aber unvollkommene Abhilfe gefunden. Mein Super-Dreieck ist programmgesteuert so festgelegt, dass es den Begrenzungsrahmen der Sites umgibt, ohne dessen Seiten zu schneiden. Diese Idee wurde durch alle möglichen frustrierenden Probleme mit Java verursacht, wenn man bedenkt, dass einige meiner berechneten Umkreiskoordinaten oder Entfernungen zwischen Koordinaten unendlich sind. Diese Vorsicht veranlasste mich, mein Superdreieck so klein zu machen, dass seine Scheitelpunkte manchmal in gültige Dreiecksumkreisungen fielen. Durch die Vergrößerung des Superdreiecks scheint das Problem zu verschwinden. Es ist jedoch möglich, dass ein Dreieck auf dem konvexen Rumpf so stumpf ist, dass einer der Scheitelpunkte immer noch in einen gültigen Umkreis fallen kann.

Ich denke, dies bedeutet, dass meine ursprüngliche Frage angesichts der Beschränkungen der Gleitkommazahl immer noch gültig ist. Gibt es eine kostengünstige Möglichkeit, um sicherzustellen, dass der Bowyer-Watson-Algorithmus eine gültige Triangulation generiert?