Examples

Problem: Find the minimum area and perimeter enclosing rectangles of a planar set of points

To find the bounding rectangles that enclose a planar point set with minimal area or perimeter, we first compute the 2d convex hull of the point set in O(n·log(n)) time with n being the number of points in the set. Then, the bounding rectangles can be found in O(h) time with h being the number of vertices of the 2d convex hull.

Solution using G#

  1.        public static void BoundingRectangleExample()
  2.         {
  3.             // Generate some points in a square
  4.             PointSet ps = SamplePoints.RandomInRectangle(20, 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.             // Compute the minimum area enclosing rectangle
  16.             BoundingRectangle ma = ch.MinimumAreaEnclosingRectangle();
  17.  
  18.             // Compute the minimum perimeter enclosing rectangle
  19.             BoundingRectangle mp = ch.MinimumPerimeterEnclosingRectangle();
  20.  
  21.             // visualize: ----------------------------------------------------
  22.             // Make a scene
  23.             Scene sc = new Scene();
  24.  
  25.             // Set the point style
  26.             sc.PointDisplayMode = 3;
  27.             sc.PointSize = 0.003;
  28.            
  29.             // Make a layer for the 2d convex hull
  30.             Scene.Layer eLayer = new Scene.Layer("Hull", 92);
  31.  
  32.             // Make a layer for the initial points
  33.             Scene.Layer ipLayer = new Scene.Layer("Initial_Points", 52);
  34.  
  35.             // Make a layer for the minimum area enclosing rectangle
  36.             Scene.Layer maLayer = new Scene.Layer("Min_A", 1);
  37.  
  38.             // Make a layer for the minimum perimeter enclosing rectangle
  39.             Scene.Layer mpLayer = new Scene.Layer("Min_P", 5);
  40.  
  41.             // Add the hull to the scene
  42.             sc.Add(ch.Edges, eLayer);
  43.             sc.Add(ch.InitialPoints, ipLayer);
  44.             sc.Add(ma.GetEdges(), maLayer);
  45.             sc.Add(mp.GetEdges(), mpLayer);
  46.  
  47.             // Output the scene as dxf
  48.             sc.WriteDxf(@"c:\bounding_rectangles.dxf");
  49.         }

Output

2d convex hull of 20 points (green), minimum area enclosing rectangle (red) and minimum perimeter enclosing rectangle (blue)

<<back