# Examlpes

## Problem: Compute a conforming Delaunay triangulation of a set of boundaries and constraints

A 2d conforming Delaunay triangulation (CDT) is a true Delaunay triangulation in which each boundary or constraint may have been subdivided into several edges by the insertion of additional points. This allows the edges to exist in the triangulation while maintaining the Delaunay property.

A CDT must contain at least one of the following items:

• An arbitrary number of triangulation points, which will be vertices of the triangles in the CDT.
• An arbitrary number of unordered open or closed edges, called constraints, whose start and end points will be vertices of the triangles in the CDT. No edge of a triangle will cross a constraint. This is achieved by inserting additional triangulation points.
• An arbitrary number of unordered edges defining closed regions, called boundaries, whose start and end points will be vertices of the triangles in the CDT. No edge will cross a boundary. Boundaries allow for defining holes or islands in a triangulation by removing triangles with a simple ray tracing algorithm.

Restrictions:

• A CDT can not triangulate points, constraints or boundaries with identical X and Y coordinates. This is, vertical or recessing walls or "caves" can not be triangulated.
• Intersecting constraints and/or boundaries will cause unpredictable results at the intersection points.
• The boundary edges must define an arbitrary number of closed regions or the ray tracing algorithm will fail.

The algorithm does not recheck if the boundaries or constraints intersect, nor does it recheck if the boundaries define closed regions.

Click here for more details on the implemented triangulation algorithm, valid input data and restrictions.

The following example is a CDT of the Chiemsee lake in Bavaria. It has the two islands Herrenchiemsee and Frauenchiemsee. You can download the edges forming the lake and the islands here.

## Solution using G#

1. public static void ConformingDelaunay()
2. {
3.     Global.AbsoluteEpsilon = 1e-6;
4.
5.     //-----------------------------------------------------------------
6.     //Triangulate the gound area
7.     //-----------------------------------------------------------------
8.     ConformingDelaunayTriangulation2d ground =
9.         new ConformingDelaunayTriangulation2d();
10.
11.     //Four points encompassing all boundaries
12.     ground.TriangulationPoints = new PointSet();
17.
18.     //The four outer boundary edges
20.         new Constraint(
21.         new Edge(new Point(10, 00, 0), new Point(30, 00, 0)),
22.         Constraint.ConstraintType.Boundary));
24.         new Constraint(
25.         new Edge(new Point(30, 00, 0), new Point(30, 20, 0)),
26.         Constraint.ConstraintType.Boundary));
28.         new Constraint(
29.         new Edge(new Point(30, 20, 0), new Point(10, 20, 0)),
30.         Constraint.ConstraintType.Boundary));
32.         new Constraint(
33.         new Edge(new Point(10, 20, 0), new Point(10, 00, 0)),
34.         Constraint.ConstraintType.Boundary));
35.
36.     //The lake with its islands
38.         ConvertToConstraint(
39.         Chiemsee.Lake(),
40.         Constraint.ConstraintType.Boundary));           //The lake
42.         ConvertToConstraint(
43.         Chiemsee.HerrenChiemsee(),
44.         Constraint.ConstraintType.Boundary)); //Herrenchiemsee island
46.         ConvertToConstraint(
47.         Chiemsee.FrauenChiemsee(),
48.         Constraint.ConstraintType.Boundary)); //Frauenchiemsee island
49.     ground.Triangulate();
50.
51.     //-----------------------------------------------------------------
52.     //Triangulate the water area
53.     //-----------------------------------------------------------------
54.     ConformingDelaunayTriangulation2d water =
55.         new ConformingDelaunayTriangulation2d();
56.
57.     //Four points encompassing all boundaries
58.     water.TriangulationPoints = new PointSet();
63.
64.     //The lake with its islands
66.         ConvertToConstraint(
67.         Chiemsee.Lake(),
68.         Constraint.ConstraintType.Boundary));           //The lake
70.         ConvertToConstraint(
71.         Chiemsee.HerrenChiemsee(),
72.         Constraint.ConstraintType.Boundary)); //Herrenchiemsee island
74.         ConvertToConstraint(
75.         Chiemsee.FrauenChiemsee(),
76.         Constraint.ConstraintType.Boundary)); //Frauenchiemsee island
77.     water.Triangulate();
78.
79.     //-----------------------------------------------------------------
80.     //Visualize ground and water
81.     //-----------------------------------------------------------------
82.     Scene sc = new Scene();
83.     Scene.Layer groundLayer = new Scene.Layer("Ground", 3);
84.     Scene.Layer waterLayer = new Scene.Layer("Water",5);
85.     Scene.Layer boundaryLayer = new Scene.Layer("Boundary", 7);
90.     sc.WriteDxf(@"e:\conforming_delaunay.dxf");
91.
92.     Console.WriteLine("Done!");
94. }
95.
96. /// <summary>A helper method to convert edges into constraints.</summary>
97. /// <param name="edges">A list of edges</param>
98. /// <param name="type">The desired constraint type.</param>
99. /// <returns>Returns a list of constraints.</returns>
100. public static List<Constraint> ConvertToConstraint(List<Edge> edges, Constraint.ConstraintType type)
101. {
102.     List<Constraint> constraints = new List<Constraint>();
103.     for (int i = 0; i < edges.Count; i++)
104.     {