Changeset 15585 for branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation

Timestamp:

01/09/18 15:46:53 (7 years ago)

Author:

rhanghof

Message:

#2817:

• Bugfixes for the line projection based extreme point creation
• Bugfixes for the tests

Location:

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

Files:

• ExtremePointCreator.cs (modified) (4 diffs)
• LineProjectionBasedEPCreator.cs (modified) (2 diffs)

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

@@ -20 +20 @@
 
     /// <summary>
-    /// Updates the residual space for a given bin packing
+    /// Updates the residual space for a given bin packing.
     /// </summary>
     /// <param name="binPacking"></param>
@@ -26 +26 @@
     /// <param name="position"></param>
     protected abstract void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position);
+
+    /// <summary>
+    /// Adds an extreme point to the bin packing.
+    /// </summary>
+    /// <param name="binPacking"></param>
+    /// <param name="position"></param>
+    /// <returns></returns>
     protected abstract bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position);
 
@@ -214 +221 @@
 
     /// <summary>
-    /// Returns true, if the given poisition and the related residual space is within the residual space of the given extreme point
-    /// </summary>
-    /// <param name="pos"></param>
+    /// Returns true, if the given poisition (pos) and the related residual space is within any residual space of the given extreme point (ep).
+    /// </summary>
+    /// <param name="pos">Given poisition</param>
     /// <param name="rsPos"></param>
-    /// <param name="ep"></param>
+    /// <param name="ep">Given extreme point</param>
     /// <param name="rsEp"></param>
     /// <returns></returns>
@@ -226 +233 @@
 
     /// <summary>
-    /// Returns true, if the given poisition and the related residual space is within the residual space of the given extreme point
-    /// </summary>
-    /// <param name="pos"></param>
+    /// Returns true, if the given poisition (pos) and the related residual space is within the residual space of the given extreme point (ep).
+    /// </summary>
+    /// <param name="pos">Given poisition</param>
     /// <param name="rsPos"></param>
-    /// <param name="ep"></param>
+    /// <param name="ep">Given extreme point</param>
     /// <param name="rsEp"></param>
     /// <returns></returns>
     protected virtual bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, ResidualSpace rsPos, PackingPosition ep, ResidualSpace rsEp) {
+      /*old implementation
       return rsEp.Width >= pos.X - ep.X + rsPos.Width
           && rsEp.Height >= pos.Y - ep.Y + rsPos.Height
-          && rsEp.Depth >= pos.Z - ep.Z + rsPos.Depth;
+          && rsEp.Depth >= pos.Z - ep.Z + rsPos.Depth;*/
+
+      var x = pos.X >= ep.X && pos.X + rsPos.Width <= ep.X + rsEp.Width;
+      var y = pos.Y >= ep.Y && pos.Y + rsPos.Height <= ep.Y + rsEp.Height;
+      var z = pos.Z >= ep.Z && pos.Z + rsPos.Depth <= ep.Z + rsEp.Depth;
+
+      return x && y && z;
     }
 

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

@@ -23 +23 @@
         GenerateNewExtremePointsForItem(binPacking, it, p);
       }
-    }
-
-    /// <summary>
-    /// Adds a new extreme point an the related residual spaces to a given bin packing.
-    /// - The given position has to be valid.
-    /// - The extreme point does not exist in the bin packing.
-    /// - There must be at minimum one valid residual space. A residual space is invalid if the space is zero.
-    /// </summary>
-    /// <param name="binPacking"></param>
-    /// <param name="position"></param>
-    /// <returns>True = the given point and its related residual spaces were successfully added to the bin packing</returns>
-    protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
-      if (position == null) {
-        return false;
-      }
-
-      if (PointIsInAnyItem(binPacking, new Vector3D(position))) {
-        return false;
-      }
-
-      if (binPacking.ExtremePoints.ContainsKey(position)) {
-        return false;
-      }
-
-      var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
-
-      if (rs.Count() <= 0) {
-        return false;
-      }
-
-      // todo 
-      /*
-       ist der extrempunkt im residual space eines anderen muss ueberprueft werden:
-          - ist der andere ep in der luft, kann auch dieser hinzugefuegt werden.
-          - hat der andere ep ein item unterhalb, darf dieser nicht hinzugefuegt werden.
-       -> neu methode basierend auf IsWithinResidualSpaceOfAnotherExtremePoint, die den ep oder rs zurueck gibt, der einen anderen rs einschließt.
-          eventuell gehoert diese logik in den ResidualSpaceCreator.
-      if (LiesOnAnyItem(binPacking, position)) {
-        return false;
-      }*/
-
-      binPacking.ExtremePoints.Add(position, rs);
-      return true;
-    }
-
+     
+      // remove not needed extreme points.
+      foreach (var extremePoint in binPacking.ExtremePoints.ToList()) {
+        // check if a residual space can be removed
+        foreach (var rs in extremePoint.Value.ToList()) {
+          if (ResidualSpaceCanBeRemoved(binPacking, extremePoint.Key, rs)) {
+            ((IList<ResidualSpace>)extremePoint.Value).Remove(rs);
+          }
+        }
+        // if the current extreme point has no more residual spaces, it can be removed.
+        if (((IList<ResidualSpace>)extremePoint.Value).Count <= 0) {
+          binPacking.ExtremePoints.Remove(extremePoint);
+        }
+      }
+    }
+    
+    /// <summary>
+    /// Returns true if a given residual space can be removed.
+    /// The given residual space can be removed if it is within another residual space and
+    /// - neither the position of the other residual space and the current extreme point have an item below or
+    /// - the current extreme point has an item below.
+    /// </summary>
+    /// <param name="binPacking"></param>
+    /// <param name="position"></param>
+    /// <param name="rs"></param>
+    /// <returns></returns>
+    private bool ResidualSpaceCanBeRemoved(BinPacking3D binPacking, PackingPosition position, ResidualSpace rs) {
+      foreach (var extremePoint in binPacking.ExtremePoints) {
+        if (position.Equals(extremePoint.Key)) {
+          continue;
+        }
+        if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(position), rs, extremePoint.Key, extremePoint.Value)) {
+          var itemBelowEp = LiesOnAnyItem(binPacking, extremePoint.Key);
+          var itemBelowPos = LiesOnAnyItem(binPacking, position);
+
+          if (itemBelowEp || !itemBelowEp && !itemBelowPos) {
+            return true;
+          }          
+        }
+      }
+      return false;
+    }
+    
+    /// <summary>
+    /// Returns true if the given position lies on an item or an the ground.
+    /// </summary>
+    /// <param name="binPacking"></param>
+    /// <param name="position"></param>
+    /// <returns></returns>
     private bool LiesOnAnyItem(BinPacking3D binPacking, PackingPosition position) {
       if (position.Y == 0) {
@@ -85 +89 @@
 
       return items.Count() > 0;
+    }
+
+
+    /// <summary>
+    /// Adds a new extreme point an the related residual spaces to a given bin packing.
+    /// - The given position has to be valid.
+    /// - The extreme point does not exist in the bin packing.
+    /// - There must be at minimum one valid residual space. A residual space is invalid if the space is zero.
+    /// </summary>
+    /// <param name="binPacking"></param>
+    /// <param name="position"></param>
+    /// <returns>True = the given point and its related residual spaces were successfully added to the bin packing</returns>
+    protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
+      if (position == null) {
+        return false;
+      }
+
+      if (PointIsInAnyItem(binPacking, new Vector3D(position))) {
+        return false;
+      }
+
+      if (binPacking.ExtremePoints.ContainsKey(position)) {
+        return false;
+      }
+
+      var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
+
+      if (rs.Count() <= 0) {
+        return false;
+      }
+
+      binPacking.ExtremePoints.Add(position, rs);
+      return true;
     }