Examples

Problem: Find the 2d convex hull of a planar set of points

A 2d convex hull encloses a planar point set with minimal perimeter. The following example generates random points in a rectangle and computes the 2d convex hull of these points.

The imput points may be 2d or 3d. However, the z-coordinate is ignored when computing the 2d convex hull.

Solution using G#

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

Output

2d convex hull of 1000 points in a square.

<<back