Changeset 15307 for branches/2817-BinPackingSpeedup

Timestamp:

08/04/17 23:45:08 (7 years ago)

Author:

abeham

Message:

#2817:

• Added checkbox to control showing extreme points in visualization
  • Automatically determine size of extreme point cubes
• Fixed some bugs in extreme point generation

Location:

branches/2817-BinPackingSpeedup

Files:

• HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml (modified) (1 diff)
• HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml.cs (modified) (4 diffs)
• HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs (modified) (3 diffs)

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml

@@ -32 +32 @@
              Focusable="true"
              >
-    <Grid>
-        <Border BorderThickness="1" Background="{DynamicResource {x:Static SystemColors.ControlBrushKey}}">
-            <Viewport3D Name="viewport3D1" >
+    <Grid Margin="0,0,-64,-57">
+        <CheckBox Name="showExtremePointsCheckBox" Content="Show extreme points" VerticalAlignment="Top" HorizontalAlignment="Left" Margin="10,6,0,0" Unchecked="showExtremePointsCheckBoxOnUnchecked" Checked="showExtremePointsCheckBoxOnChecked"/>
+        <Border BorderThickness="1" Background="{DynamicResource {x:Static SystemColors.ControlBrushKey}}" Margin="0,30,0,0">
+            <Viewport3D Name="viewport3D1" Margin="0,-1,0,0" >
                 <Viewport3D.Camera>
                     <PerspectiveCamera x:Name="camMain" Position="0.5 8 8" LookDirection="0 -1 -1"> <!-- camera position for design time-->

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml.cs

@@ -55 +55 @@
     private double startAngleY;
     private int selectedItemKey;
+    private bool showExtremePoints;
 
     private BinPacking<BinPacking3D.PackingPosition, PackingShape, PackingItem> packing;
@@ -155 +156 @@
       }
 
-      // draw extreme-points
-      foreach (var ep in packing.ExtremePoints) {
-        var epModel = new GeometryModel3D { Geometry = new MeshGeometry3D(), Material = new DiffuseMaterial() { Brush = new SolidColorBrush(Colors.Red) } };
-        AddSolidCube((MeshGeometry3D)epModel.Geometry, ep.X, ep.Y, ep.Z, 10, 10, 10);
-        modelGroup.Children.Add(epModel);
+      if (showExtremePoints) {
+        // draw extreme-points
+        var maxMag = (int)Math.Log10(Math.Max(packing.BinShape.Depth, Math.Max(packing.BinShape.Height, packing.BinShape.Width)));
+        var cubeSize = (int)Math.Max(Math.Pow(10, maxMag - 2), 1);
+        foreach (var ep in packing.ExtremePoints) {
+          var epModel = new GeometryModel3D { Geometry = new MeshGeometry3D(), Material = new DiffuseMaterial() { Brush = new SolidColorBrush(Colors.Red) } };
+          AddSolidCube((MeshGeometry3D)epModel.Geometry, ep.X, ep.Y, ep.Z, cubeSize, cubeSize, cubeSize);
+          modelGroup.Children.Add(epModel);
+        }
       }
 
@@ -229 +234 @@
     private void Container3DView_OnMouseEnter(object sender, MouseEventArgs e) {
       Focus(); // for mouse wheel events
+    }
+    private void showExtremePointsCheckBoxOnChecked(object sender, RoutedEventArgs e) {
+      showExtremePoints = true;
+      UpdateVisualization();
+    }
+    private void showExtremePointsCheckBoxOnUnchecked(object sender, RoutedEventArgs e) {
+      showExtremePoints = false;
+      UpdateVisualization();
     }
 
@@ -471 +484 @@
     }
     #endregion
-
   }
 }

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs

@@ -125 +125 @@
       sourcePoint = new Vector3D(position.X, position.Y, position.Z + newDepth);
       if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) {
+        // Projecting onto the XZ-plane
+        var below = ProjectDown(sourcePoint);
+        var residualSpace = CalculateResidualSpace(below);
+        if (!IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) {
+          // add only if the projected point's residual space is not a sub-space
+          // of another extreme point's residual space
+          var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z);
+          AddExtremePoint(belowPoint);
+        }
         // Projecting onto the YZ-plane
         var left = ProjectLeft(sourcePoint);
-        var residualSpace = CalculateResidualSpace(left);
+        residualSpace = CalculateResidualSpace(left);
         if (!IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) {
           // add only if the projected point's residual space is not a sub-space
@@ -134 +143 @@
           AddExtremePoint(leftPoint);
         }
-        // Projecting onto the XZ-plane
-        var below = ProjectDown(sourcePoint);
-        residualSpace = CalculateResidualSpace(below);
-        if (!IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) {
-          // add only if the projected point's residual space is not a sub-space
-          // of another extreme point's residual space
-          var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z);
-          AddExtremePoint(belowPoint);
-        }
       }
     }
@@ -148 +148 @@
     private bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> residualSpace) {
       var eps = ExtremePoints.Where(x => pos.IsInside(x, ResidualSpace[x]));
-      return eps.Any(x => ResidualSpace[x].Item1 >= pos.X - x.X + residualSpace.Item1
-          && ResidualSpace[x].Item2 >= pos.Y - x.Y + residualSpace.Item2
-          && ResidualSpace[x].Item3 >= pos.Z - x.Z + residualSpace.Item3);
+      return eps.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, residualSpace, x, ResidualSpace[x]));
+    }
+    private bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> rsPos, PackingPosition ep, Tuple<int, int, int> rsEp) {
+      return rsEp.Item1 >= pos.X - ep.X + rsPos.Item1
+          && rsEp.Item2 >= pos.Y - ep.Y + rsPos.Item2
+          && rsEp.Item3 >= pos.Z - ep.Z + rsPos.Item3;
     }
 
     private bool AddExtremePoint(PackingPosition pos) {
       if (ExtremePoints.Add(pos)) {
-        ResidualSpace.Add(pos, Tuple.Create(BinShape.Width - pos.X, BinShape.Height - pos.Y, BinShape.Depth - pos.Z));
+        var rs = Tuple.Create(BinShape.Width - pos.X, BinShape.Height - pos.Y, BinShape.Depth - pos.Z);
+        ResidualSpace.Add(pos, rs);
+        // Check if existing extreme points are shadowed by the new point
+        // That is, their residual space fit entirely into the residual space of the new point
+        foreach (var ep in ExtremePoints.Where(x => x != pos && new Vector3D(x).IsInside(pos, rs)).ToList()) {
+          if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), ResidualSpace[ep], pos, rs)) {
+            ExtremePoints.Remove(ep);
+            ResidualSpace.Remove(ep);
+          }
+        }
         return true;
       }