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();
  13.     ground.TriangulationPoints.Add(new Point(-50, -50, 0));
  14.     ground.TriangulationPoints.Add(new Point(50, -50, 0));
  15.     ground.TriangulationPoints.Add(new Point(50, 50, 0));
  16.     ground.TriangulationPoints.Add(new Point(-50, 50, 0));
  17.  
  18.     //The four outer boundary edges
  19.     ground.Boundaries.Add(
  20.         new Constraint(
  21.         new Edge(new Point(10, 00, 0), new Point(30, 00, 0)),
  22.         Constraint.ConstraintType.Boundary));
  23.     ground.Boundaries.Add(
  24.         new Constraint(
  25.         new Edge(new Point(30, 00, 0), new Point(30, 20, 0)),
  26.         Constraint.ConstraintType.Boundary));
  27.     ground.Boundaries.Add(
  28.         new Constraint(
  29.         new Edge(new Point(30, 20, 0), new Point(10, 20, 0)),
  30.         Constraint.ConstraintType.Boundary));
  31.     ground.Boundaries.Add(
  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
  37.     ground.Boundaries.AddRange(
  38.         ConvertToConstraint(
  39.         Chiemsee.Lake(),
  40.         Constraint.ConstraintType.Boundary));           //The lake
  41.     ground.Boundaries.AddRange(
  42.         ConvertToConstraint(
  43.         Chiemsee.HerrenChiemsee(),
  44.         Constraint.ConstraintType.Boundary)); //Herrenchiemsee island
  45.     ground.Boundaries.AddRange(
  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();
  59.     water.TriangulationPoints.Add(new Point(0, 0, 0));
  60.     water.TriangulationPoints.Add(new Point(50, 0, 0));
  61.     water.TriangulationPoints.Add(new Point(50, 50, 0));
  62.     water.TriangulationPoints.Add(new Point(0, 50, 0));
  63.  
  64.     //The lake with its islands
  65.     water.Boundaries.AddRange(
  66.         ConvertToConstraint(
  67.         Chiemsee.Lake(),
  68.         Constraint.ConstraintType.Boundary));           //The lake
  69.     water.Boundaries.AddRange(
  70.         ConvertToConstraint(
  71.         Chiemsee.HerrenChiemsee(),
  72.         Constraint.ConstraintType.Boundary)); //Herrenchiemsee island
  73.     water.Boundaries.AddRange(
  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);
  86.     sc.Add(ground.GetTriangles(), groundLayer);
  87.     sc.Add(water.GetTriangles(), waterLayer);
  88.     sc.Add(Constraint.GetEdges(ground.Constraints), boundaryLayer);
  89.     sc.Add(Constraint.GetEdges(ground.Boundaries), boundaryLayer);
  90.     sc.WriteDxf(@"e:\conforming_delaunay.dxf");
  91.  
  92.     Console.WriteLine("Done!");
  93.     Console.ReadLine();
  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.     {
  105.         constraints.Add(new Constraint(edges[i], type));
  106.     }
  107.     return constraints;
  108. }

Output

626 boundaries forming the Chiemsee lake and islands plus 4 boundaries to define an enclosing rectangle.
The triangulated non-water area
The triangulated water area
A rendered detail view on the mesh

<< back