Examples

Problem: Find the 3d convex hull of a spatial set of points

A 3d convex hull encloses a spatial point set with a minimal surface area. The following example generates random points in the unit cube and then computes the convex hull of these points.

Coplanar facets are not merged. Consequently, the 3d convex hull will always consist of triangles.

Solution using G#

  1.        public static void ConvexHullExample()
  2.         {
  3.             // Generate some points in the unit cube
  4.             PointSet ps = SamplePoints.RandomInCube(1000, 1, 1, 1);
  5.  
  6.             // Instantiate a 3d convex hull
  7.             ConvexHull3d ch = new ConvexHull3d();
  8.  
  9.             // Assign the initial point set
  10.             ch.InitialPoints = ps;
  11.  
  12.             // Compute the 3d convex hull in O(n*log(n)) time
  13.             ch.ComputeHull();
  14.  
  15.             // Get the triangles forming the hull
  16.             List<Triangle> triangles = ch.Triangles;
  17.  
  18.             // visualize: ----------------------------------------------------
  19.             // Make a scene
  20.             Scene sc = new Scene();
  21.  
  22.             // Set the point style
  23.             sc.PointDisplayMode = 0;
  24.             sc.PointSize = 0;
  25.  
  26.             // Make a layer for the triangles
  27.             Scene.Layer tLayer = new Scene.Layer("Hull_Triangles", 1);
  28.  
  29.             // Make a layer for the initial points
  30.             Scene.Layer ipLayer = new Scene.Layer("Initial_Points", 2);
  31.  
  32.             // Make a layer for the vertices on the hull
  33.             Scene.Layer hpLayer = new Scene.Layer("Hull_Points", 3);
  34.                        
  35.             // Add the hull to the scene
  36.             sc.Add(triangles, tLayer);
  37.             sc.Add(ch.InitialPoints, ipLayer);
  38.             sc.Add(ch.Vertices, hpLayer);
  39.  
  40.             // Output the scene as dxf
  41.             sc.WriteDxf(@"c:\hull.dxf");
  42.         }

Output

Convex hull of 1000 points in the unit cube.
Wireframe hull and internal points

<<back