Examples

Problem: Test if a 3d set of points fits into a container

Testing if a 3d point cloud can be loaded into a rectangular container is a suprisingly complex task. The best known exact algorithm has O(n3) complexity,  which is of little practical use. G# provides a very efficient approximative solution for the 3d container loading problem. It bases on the empirical observation that the principal axes of the mass moment of inertia establish a pretty good basis for a somewhat minimal bounding box.

Note that an exact solution can be found in O(n·log(n)) time for the 2d container loading problem.

Solution using G#

  1. public static void LoadingExample()
  2. {
  3.     // Generate a "container" with dimensions 12 x 2.3 x 2.3
  4.     // The orientation in space does not matter, so the
  5.     // orientation along the global axes is just as good.
  6.     BoundingBox container = new BoundingBox(12.0, 2.3, 2.3,
  7.                                             CoordinateSystem.Global());
  8.  
  9.     // Generate an "item" to load into the container:
  10.     // Create some points and transform them to somewhere in space
  11.     PointSet item = SamplePoints.RandomInSphere(1000, 1);
  12.     item.Add(new Point(11, 0, 0));
  13.     item.TransformCoordinates(CoordinateSystem.Global(),
  14.                             CoordinateSystem.RandomCoordinateSystem());
  15.    
  16.     // Now the item is a point cloud somewhere in space. We will now
  17.     // find a pretty tight bounding box for the item.
  18.  
  19.     // Instantiate a convex hull
  20.     ConvexHull3d convexHullOfItem = new ConvexHull3d();
  21.  
  22.     // Compute the convex hull for the item to load:
  23.     convexHullOfItem.InitialPoints = item;
  24.     convexHullOfItem.ComputeHull();
  25.  
  26.     // Get the bounding box
  27.     BoundingBox boundingBoxOfItem =
  28.                         convexHullOfItem.PrincipalAxesBoundingBox();
  29.  
  30.     // Some properties of the bounding box:
  31.     Console.WriteLine("BB length: " + boundingBoxOfItem.Length);
  32.     Console.WriteLine("BB width : " + boundingBoxOfItem.Width);
  33.     Console.WriteLine("BB height: " + boundingBoxOfItem.Height);
  34.     Console.WriteLine("BB volume: " + boundingBoxOfItem.Volume());
  35.      // Test if the item fits into the container:
  36.     Console.WriteLine(boundingBoxOfItem.FitsInto(container));
  37.     Console.ReadLine();
  38.  
  39.     // Visualize: ----------------------------------------------------
  40.     // Make a scene
  41.     Scene sc = new Scene();
  42.  
  43.     // Make a layer for the triangles
  44.     Scene.Layer itemLayer = new Scene.Layer("Item_Hull", 90);
  45.  
  46.     // Make a layer for the bounding box of the item
  47.     Scene.Layer itembBoxLayer = new Scene.Layer("Item_Bounding_Box", 91);
  48.  
  49.     // Add the surface of the convex hull of the item
  50.     sc.Add(convexHullOfItem.Triangles, itemLayer);
  51.  
  52.     // Add the surface of the bounding of the item
  53.     sc.Add(boundingBoxOfItem.GetSurface(), itembBoxLayer);
  54.  
  55.     // Output the scene as dxf
  56.     sc.WriteDxf(@"c:\hull.dxf");
  57. }

Output

Convex hull of the item and principal axes bounding box

Here's another example:

  1.       PointSet item = SamplePoints.RandomInCube(500, 11, 2.2, 1.5);

Output

Convex hull of the item and principal axes bounding box
View along an edge of the bounding box

<<back