Examples

Problem: Test if a 2d point set fits into a 2d container

In contrast to to the 3d container loading problem, the 2d container loading problem can be solved exactly in O(n·log(n)) time. To test if a 2d point set fits into a 2d container, 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 test if the convex hull fits into a given bounding rectangle can be done in O(h) time with h being the number of vertices of the 2d convex hull.

Solution using G#

  1.        public static void ContainerLoadingExample()
  2.         {
  3.             // A container with dimension 3 x 1. Center point and
  4.             // rotation angle are arbitrary
  5.             Point center = new Point(0, 0, 0);
  6.             BoundingRectangle container = new BoundingRectangle(3, 1, center, 0);
  7.  
  8.             // Generate some points in a rectangle. This is the item to load
  9.             PointSet ps = SamplePoints.RandomInRectangle(100, 3, 1);
  10.            
  11.             // Instantiate a 2d convex hull
  12.             ConvexHull2d ch = new ConvexHull2d();
  13.  
  14.             // Assign the item to load
  15.             ch.InitialPoints = ps;
  16.  
  17.             // Compute the 2d convex hull of the item to load
  18.             ch.ComputeHull();
  19.  
  20.             // Test if the item fits into the container
  21.             BoundingRectangle br = ch.FitsInto(container);
  22.             if ( br == null )
  23.             {
  24.                 Console.WriteLine("Item does not fit into container!");
  25.                 return;
  26.             }
  27.                        
  28.             // Since it fits into the container, we can visualize the
  29.             // bounding box
  30.             // Make a scene
  31.             Scene sc = new Scene();
  32.  
  33.             // Set the point style
  34.             sc.PointDisplayMode = 3;
  35.             sc.PointSize = 0.003;
  36.            
  37.             // Make a layer for the 2d convex hull
  38.             Scene.Layer iLayer = new Scene.Layer("Item", 92);
  39.  
  40.             // Make a layer for the initial points
  41.             Scene.Layer pLayer = new Scene.Layer("Initial_Points", 52);
  42.  
  43.             // Make a layer for the container
  44.             Scene.Layer cLayer = new Scene.Layer("container", 1);
  45.  
  46.             // Make a layer for the bounding rectangle
  47.             Scene.Layer bLayer = new Scene.Layer("Item_bounding_rectangle", 5);
  48.  
  49.             // Transform the container so that we can actually see that
  50.             // the item fits into the container
  51.             container.Center = br.Center;
  52.             container.RotationAngle = br.RotationAngle;
  53.  
  54.             // Add the hull to the scene
  55.             sc.Add(ch.Edges, iLayer);
  56.             sc.Add(ch.InitialPoints, pLayer);
  57.             sc.Add(container.GetEdges(), cLayer);
  58.             sc.Add(br.GetEdges(), bLayer);
  59.  
  60.             // Output the scene as dxf
  61.             sc.WriteDxf(@"c:\container_loading_2d.dxf");
  62.         }

Output

2d convex hull of 100 points (green), the given container (red) and a bounding rectangle fitting into the container (blue)

<<back