Examlpes

Problem: Find the Delaunay triangulation of a projectable set of points

A 2d Delaunay triangulation is the triangulation of the projection of 3d points onto the XY-plane so that the resulting triangles are the "least sliver" ones of all possible triangulations. 

A 2d Delaunay triangulation can not triangulate points with identical X and Y coordinates. Practically, this means that vertical or recessing walls or "caves" can not be triangulated.

However, if a projectable view on the points exists, you may apply a coordinate transformation on the points, triangulate and re-transform the points to obtain a valid triangulaton.

Solution using D#

  1.        public static void DelaunayExample()
  2.         {
  3.             // Create a sample point set
  4.             PointSet ps = SamplePoints.SupershapeStarfish(10000);
  5.  
  6.             // Instantiate a delaunay triangulation
  7.             DelaunayTriangulation2d dt = new DelaunayTriangulation2d();
  8.  
  9.             // Assign the point set to triangulate
  10.             dt.TriangulationPoints = ps;
  11.  
  12.             // Triangulate the point set
  13.             dt.Triangulate();
  14.  
  15.             // You may add points to the existing triangulation
  16.             dt.AddPointToCurrentTriangulation(new Point(0.5, 0.5, 0));
  17.  
  18.             // Get the triangulation
  19.             List<Triangle> triangles = dt.GetTriangles();
  20.  
  21.             // visualize: ---------------------------------------------------
  22.             // Make a scene
  23.             Scene sc = new Scene();
  24.  
  25.             // Set the point style
  26.             sc.PointDisplayMode = 0;
  27.             sc.PointSize = 0;
  28.  
  29.             // Make a layer for the triangles
  30.             Scene.Layer tLayer = new Scene.Layer("Delaunay_Triangles", 1);
  31.  
  32.             // Make a layer for the triangulation points
  33.             Scene.Layer pLayer = new Scene.Layer("Triangulation_Points", 2);
  34.  
  35.             // Add the triangles and the triangulation points to the scene
  36.             sc.Add(triangles, tLayer);
  37.             sc.Add(dt.TriangulationPoints, pLay);
  38.  
  39.             // Output the scene as dxf
  40.             sc.WriteDxf(@"c:\delaunay.dxf");
  41.         }
  42.  

Output

Delaunay triangulation of 10001 random points on a starfish supershape.
Partial top view on the mesh.

<< back