Constrained Delaunay triangulation

In this project, a crucial component involves using constrained Delaunay triangulation (CDT) to generate a mesh that respects specific constraints while attempting to maintain the properties of a Delaunay triangulation.

1. What is constrained Delaunay triangulation?

A constrained Delaunay triangulation is a type of triangulation that incorporates constrained edges, which are edges that must appear in the triangulation regardless of whether they meet the Delaunay criteria (source). In a typical Delaunay triangulation, the circumcircle of any triangle does not contain any other vertex from the triangulation within it (source). However, in a CDT, this condition is relaxed for constrained edges.


400px
Figure 1. Delaunay triangulation in the plane with circumcircles (source)

In a CDT, the triangulation respects the constraints (such as edges that must be present), but still tries to approximate the Delaunay condition as closely as possible for the non-constrained edges. This means that while the triangulation may not fully adhere to the Delaunay condition, it does so in a "constrained" manner, where the constrained edges effectively block the view, creating a "constrained empty circle" property (source).

The constrained Delaunay triangulation is particularly useful when the mesh must conform to specific features or boundaries where certain edges must be preserved. This ensures that the resulting mesh accurately represents the required constraints while maintaining the mesh’s overall quality.

2. Relationship with the Voronoi diagram

A Voronoi diagram is a partitioning of a plane into regions based on the distance to a specific set of points. Each region in the diagram corresponds to one of the points, and every location within a region is closer to that point than to any other point. The Delaunay triangulation is the dual graph of the Voronoi diagram. This means that by connecting the centers of the circumcircles in a Delaunay triangulation, you can produce the Voronoi diagram.


delaunay centers
Figure 2. Delaunay triangulation with all the circumcircles and their centers (in red) (source)

delaunay voronoi
Figure 3. Connecting the centers of the circumcircles produces the Voronoi diagram (in red) (source)

In the context of constrained Delaunay triangulation, the corresponding Voronoi diagram is also constrained. The constrained edges in the *CDT create boundaries in the Voronoi diagram, ensuring that the Voronoi regions respect these edges. This is particularly useful in applications where certain boundaries or features must be preserved in both the triangulation and the Voronoi diagram, providing a dual representation that honors the same constraints.

Overall, the use of constrained Delaunay triangulation ensures that the mesh accurately represents the required constraints while maintaining the mesh’s overall quality and its relationship with the Voronoi diagram.


Next: Project Structure


References