Up: Top Previous: Bibliography

# Figures

Figure 1: Various triangulations of a 2D set of points: a) general triangulation, b) constrained triangulation, c) Delaunay triangulation, d) constrained Delaunay triangulation (constraining edges are in bold).

Figure 2: Boundary recovery - transformation of 2D Delaunay triangulation into constrained Delaunay triangulation using the diagonal (of shaded quadrilateral) swapping.

Figure 3: Violation dependency: a) set of points and constraining edges with their smallest circumscribed circles , b) dependency graph corresponding to the violation of the empty-circumsphere property of constraining edges, c) possible point insertion ordering ensuring presence of all constraining edges in the constrained Delaunay triangulation.

Figure 4: Cyclic violation dependency: a) set of points and constraining edges with their smallest circumscribed circles , b) dependency graph corresponding to the violation of the empty-circumsphere property of constraining edges.

Figure 5: Cyclic violation dependency graph: a) set of points and constraining edges with their smallest circumscribed circles , b) dependency graph corresponding to the violation of the empty-circumsphere property of constraining edges.

Figure 6: Perturbation of point to remove its violation of constraining edge : a) using perpendicular shift, b) using radial shift to setup its initial position before the iterative adjustment toward the final position .

Figure 7: Save violation of : a) without, b) with additional dependencies.

Figure 8: Save violation of with existing in the Delaunay triangulation: a) side view in the direction of , b) top view perpendicularly to . Shaded area should comply with empty-property.

Figure 9: Simple topological transformation. 2 tetrahedra are made from 3 by removal of edge intersecting constraining face .

Figure 10: Safe violation of due to simple topological transformation: a) side view in the direction of , b) top view perpendicularly to . Shaded area should comply with empty-property. All edges bounding have to be successively considered.

Up: Top Previous: Bibliography

Daniel Rypl
2005-11-06