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

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

File:

• branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/LineProjectionBasedEPCreator.cs (modified) (2 diffs)

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;
     }