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.

The following example is a CDT of the Chiemsee lake in Bavaria. It has the two islands Herrenchiemsee and Frauenchiemsee.

Solution using G#

  1. public static void ConformingDelaunay()
  2. {
  3.     ConformingDelaunayTriangulation2d ground =
  4.         new ConformingDelaunayTriangulation2d();
  5.     ground.TriangulationPoints = new PointSet();
  6.     ground.Boundaries.Add(new Edge(new Point(10, 00, 0), new Point(30, 00, 0)));
  7.     ground.Boundaries.Add(new Edge(new Point(30, 00, 0), new Point(30, 20, 0)));
  8.     ground.Boundaries.Add(new Edge(new Point(30, 20, 0), new Point(10, 20, 0)));
  9.     ground.Boundaries.Add(new Edge(new Point(10, 20, 0), new Point(10, 00, 0)));
  10.     ground.Boundaries.AddRange(Chiemsee.Lake());         //The lake
  11.     ground.Boundaries.AddRange(Chiemsee.HerrenChiemsee());//Herrenchiemsee island
  12.     ground.Boundaries.AddRange(Chiemsee.FrauenChiemsee());//Frauenchiemsee island
  13.     ground.Triangulate();
  14.  
  15.     ConformingDelaunayTriangulation2d water =
  16.         new ConformingDelaunayTriangulation2d();
  17.     water.TriangulationPoints = new PointSet();
  18.     water.Boundaries.AddRange(Chiemsee.Lake());          //The lake
  19.     water.Boundaries.AddRange(Chiemsee.HerrenChiemsee());//Herrenchiemsee island
  20.     water.Boundaries.AddRange(Chiemsee.FrauenChiemsee());//Frauenchiemsee island
  21.     water.Triangulate();
  22.  
  23.     Scene sc = new Scene();
  24.     Scene.Layer groundLayer = new Scene.Layer("Ground", 3);
  25.     Scene.Layer waterLayer = new Scene.Layer("Water",5);
  26.     Scene.Layer boundaryLayer = new Scene.Layer("Boundary", 7);
  27.  
  28.     sc.Add(ground.GetTriangles(), groundLayer);
  29.     sc.Add(water.GetTriangles(), waterLayer);
  30.     sc.Add(ground.Constraints, boundaryLayer);
  31.     sc.Add(ground.Boundaries, boundaryLayer);
  32.     sc.WriteDxf(@"c:\conforming_delaunay.dxf");
  33.  
  34.     Console.WriteLine("Done!");
  35.     Console.ReadLine();
  36. }

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