Next: Violation Dependency Graph Up: Top Previous: Constrained Delaunay Triangulation


A Priori Boundary Recovery

The objective of the a priori boundary recovery process is to guarantee that each constraining simplex is present in the intermediate constrained Delaunay triangulation immediately after all its vertices are inserted using the modified Watson's algorithm. A very simple criterion [28] is adopted to decide whether appears in the Delaunay triangulation. This is the empty-sphere property applied to the smallest -dimensional sphere circumscribed to . This criterion is sufficient but not a necessary condition. For example in [40], a more sophisticated but computationally more demanding optimization based approach was worked out resulting in a less restrictive criterion. The constraining simplex satisfying the empty-circumsphere property is called Delaunay facet. If the property is violated, is called violated facet and all the points inside the minimal circumsphere are called violating points. The modified Watson's algorithm ensures that a violated facet appears in the resulting triangulation if it is inserted (more precisely if its vertices are inserted) before all its violating points. Thus proper ordering of point insertion assures that even violated facets are present in the resulting constrained Delaunay triangulation. This point insertion ordering is driven by a violation dependency graph.



Subsections

Next: Violation Dependency Graph Up: Top Previous: Constrained Delaunay Triangulation

Daniel Rypl
2005-11-06