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

Timestamp:

12/13/17 09:47:49 (6 years ago)

Author:

rhanghof

Message:

#2817:

• Changed the calculation algorithm for creating extreme points by using line based projection
• Changed the calculation of the residual spaces for line based projection

File:

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

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

@@ -15 +15 @@
   /// </summary>
   public class PointProjectionBasedEPCreator : ExtremePointCreator {
-    public override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
-      GenerateNewExtremePointsForNewItem(binPacking, item, position);
+    protected override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
+      GenerateNewExtremePointsForItem(binPacking, item, position);
 
       // if an item is fit in below, before, or left of another its extreme points have to be regenerated
       foreach (var above in GetItemsAbove(binPacking, position)) {
-        GenerateNewExtremePointsForNewItem(binPacking, above.Item2, above.Item1);
+        GenerateNewExtremePointsForItem(binPacking, above.Item2, above.Item1);
       }
       foreach (var front in GetItemsInfront(binPacking, position)) {
-        GenerateNewExtremePointsForNewItem(binPacking, front.Item2, front.Item1);
+        GenerateNewExtremePointsForItem(binPacking, front.Item2, front.Item1);
       }
       foreach (var right in GetItemsOnRight(binPacking, position)) {
-        GenerateNewExtremePointsForNewItem(binPacking, right.Item2, right.Item1);
+        GenerateNewExtremePointsForItem(binPacking, right.Item2, right.Item1);
       }
     }
     
-    public override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
+    protected override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
       foreach (var ep in binPacking.ExtremePoints.ToList()) {
-        var rs = binPacking.ResidualSpace[ep];
+        var rs = binPacking.ResidualSpaces[ep];
         var depth = position.Rotated ? item.Width : item.Depth;
         var width = position.Rotated ? item.Depth : item.Width;
@@ -39 +39 @@
           if (ep.X <= position.X && ep.Y >= position.Y && ep.Y < position.Y + item.Height) {
             var diff = position.X - ep.X;
-            var newRSX = Math.Min(rs.Item1, diff);
-            rs = Tuple.Create(newRSX, rs.Item2, rs.Item3);
+            var newRSX = Math.Min(rs.Width, diff);
+            rs = ResidualSpace.Create(newRSX, rs.Height, rs.Depth);
             changed = true;
           }
           if (ep.Y <= position.Y && ep.X >= position.X && ep.X < position.X + width) {
             var diff = position.Y - ep.Y;
-            var newRSY = Math.Min(rs.Item2, diff);
-            rs = Tuple.Create(rs.Item1, newRSY, rs.Item3);
+            var newRSY = Math.Min(rs.Height, diff);
+            rs = ResidualSpace.Create(rs.Width, newRSY, rs.Depth);
             changed = true;
           }
@@ -55 +55 @@
             ep.X >= position.X && ep.X < position.X + width) {
           var diff = position.Z - ep.Z;
-          var newRSZ = Math.Min(rs.Item3, diff);
-          rs = Tuple.Create(rs.Item1, rs.Item2, newRSZ);
+          var newRSZ = Math.Min(rs.Depth, diff);
+          rs = ResidualSpace.Create(rs.Width, rs.Height, newRSZ);
           changed = true;
         }
 
         if (changed) {
-          if (IsNonZero(rs) && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) {
-            binPacking.ResidualSpace[ep] = rs;
+          if (!rs.IsZero() && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) {
+            binPacking.ResidualSpaces[ep] = rs;
           } else {
             binPacking.ExtremePoints.Remove(ep);
-            binPacking.ResidualSpace.Remove(ep);
+            binPacking.ResidualSpaces.Remove(ep);
           }
         }
@@ -83 +83 @@
       if (binPacking.ExtremePoints.Add(position)) {
         var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
-        binPacking.ResidualSpace.Add(position, rs);
+        binPacking.ResidualSpaces.Add(position, rs);
         // Check if the existing extreme points are shadowed by the new point
         // This is, their residual space fit entirely into the residual space of the new point
         foreach (var ep in binPacking.ExtremePoints.Where(x => x != position && new Vector3D(x).IsInside(position, rs)).ToList()) {
-          if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), binPacking.ResidualSpace[ep], position, rs)) {
+          if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), binPacking.ResidualSpaces[ep], position, rs)) {
             binPacking.ExtremePoints.Remove(ep);
-            binPacking.ResidualSpace.Remove(ep);
+            binPacking.ResidualSpaces.Remove(ep);
           }
         }