Changeset 15308 for branches/2817-BinPackingSpeedup

Timestamp:

08/06/17 23:04:05 (7 years ago)

Author:

abeham

Message:

#2817:

• fixed remaining bugs

File:

• branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs (modified) (13 diffs)

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

@@ -65 +65 @@
 
     public override void PackItem(int itemID, PackingItem item, PackingPosition position) {
+      // base call is deliberately omitted, because UpdateResidualSpace needs to be fitted in before
+      // generating new extreme points
+      Items[itemID] = item;
+      Positions[itemID] = position;
       ExtremePoints.Remove(position);
       ResidualSpace.Remove(position);
       UpdateResidualSpace(item, position);
-      base.PackItem(itemID, item, position);
+      GenerateNewExtremePointsForNewItem(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(position))
+        GenerateNewExtremePointsForNewItem(above.Item2, above.Item1);
+      foreach (var front in GetItemsInfront(position))
+        GenerateNewExtremePointsForNewItem(front.Item2, front.Item1);
+      foreach (var right in GetItemsOnRight(position))
+        GenerateNewExtremePointsForNewItem(right.Item2, right.Item1);
+      AddNewItemToOccupationLayers(itemID, item, position);
     }
 
@@ -82 +94 @@
         var below = ProjectDown(sourcePoint);
         var residualSpace = CalculateResidualSpace(below);
-        if (!IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) {
+        if (IsNonZero(residualSpace)
+          && !IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) {
           // add only if the projected point's residual space is not a sub-space
           // of another extreme point's residual space
@@ -91 +104 @@
         var back = ProjectBackward(sourcePoint);
         residualSpace = CalculateResidualSpace(back);
-        if (!IsWithinResidualSpaceOfAnotherExtremePoint(back, residualSpace)) {
+        if (IsNonZero(residualSpace)
+          && !IsWithinResidualSpaceOfAnotherExtremePoint(back, residualSpace)) {
           // add only if the projected point's residual space is not a sub-space
           // of another extreme point's residual space
@@ -105 +119 @@
         var left = ProjectLeft(sourcePoint);
         var residualSpace = CalculateResidualSpace(left);
-        if (!IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) {
+        if (IsNonZero(residualSpace)
+          && !IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) {
           // add only if the projected point's residual space is not a sub-space
           // of another extreme point's residual space
@@ -114 +129 @@
         var back = ProjectBackward(sourcePoint);
         residualSpace = CalculateResidualSpace(back);
-        if (!IsWithinResidualSpaceOfAnotherExtremePoint(back, residualSpace)) {
+        if (IsNonZero(residualSpace)
+          && !IsWithinResidualSpaceOfAnotherExtremePoint(back, residualSpace)) {
           // add only if the projected point's residual space is not a sub-space
           // of another extreme point's residual space
@@ -128 +144 @@
         var below = ProjectDown(sourcePoint);
         var residualSpace = CalculateResidualSpace(below);
-        if (!IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) {
+        if (IsNonZero(residualSpace)
+          && !IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) {
           // add only if the projected point's residual space is not a sub-space
           // of another extreme point's residual space
@@ -137 +154 @@
         var left = ProjectLeft(sourcePoint);
         residualSpace = CalculateResidualSpace(left);
-        if (!IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) {
+        if (IsNonZero(residualSpace)
+          && !IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) {
           // add only if the projected point's residual space is not a sub-space
           // of another extreme point's residual space
@@ -146 +164 @@
     }
 
+    private bool IsNonZero(Tuple<int, int, int> rs) {
+      return rs.Item1 > 0 && rs.Item2 > 0 && rs.Item3 > 0;
+    }
+
     private bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> residualSpace) {
-      var eps = ExtremePoints.Where(x => pos.IsInside(x, ResidualSpace[x]));
+      var eps = ExtremePoints.Where(x => !pos.Equals(x) && pos.IsInside(x, ResidualSpace[x]));
       return eps.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, residualSpace, x, ResidualSpace[x]));
     }
@@ -158 +180 @@
     private bool AddExtremePoint(PackingPosition pos) {
       if (ExtremePoints.Add(pos)) {
-        var rs = Tuple.Create(BinShape.Width - pos.X, BinShape.Height - pos.Y, BinShape.Depth - pos.Z);
+        var rs = CalculateResidualSpace(new Vector3D(pos));
         ResidualSpace.Add(pos, rs);
         // Check if existing extreme points are shadowed by the new point
@@ -239 +261 @@
                   .Where(x => x != null && x.Y >= pos.Y)
                   .MinItems(x => x.Y).First();
+    }
+
+    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsAbove(PackingPosition pos) {
+      var line = new Line3D(pos, new Vector3D(0, 1, 0));
+      return Items.Select(x => new {
+        Item = x.Value,
+        Position = Positions[x.Key],
+        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Bottom))
+      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
+        .Select(x => Tuple.Create(x.Position, x.Item));
+    }
+
+    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsInfront(PackingPosition pos) {
+      var line = new Line3D(pos, new Vector3D(0, 0, 1));
+      return Items.Select(x => new {
+        Item = x.Value,
+        Position = Positions[x.Key],
+        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Back))
+      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
+        .Select(x => Tuple.Create(x.Position, x.Item));
+    }
+
+    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnRight(PackingPosition pos) {
+      var line = new Line3D(pos, new Vector3D(1, 0, 0));
+      return Items.Select(x => new {
+        Item = x.Value,
+        Position = Positions[x.Key],
+        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Left))
+      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
+        .Select(x => Tuple.Create(x.Position, x.Item));
     }
 
@@ -429 +481 @@
     
     public void UpdateResidualSpace(PackingItem item, PackingPosition pos) {
-      foreach (var ep in ExtremePoints) {
+      foreach (var ep in ExtremePoints.ToList()) {
         var rs = ResidualSpace[ep];
         var depth = pos.Rotated ? item.Width : item.Depth;
         var width = pos.Rotated ? item.Depth : item.Width;
+        var changed = false;
         if (ep.Z >= pos.Z && ep.Z < pos.Z + depth) {
           if (ep.X <= pos.X && ep.Y >= pos.Y && ep.Y < pos.Y + item.Height) {
             var diff = pos.X - ep.X;
             var newRSX = Math.Min(rs.Item1, diff);
-            ResidualSpace[ep] = Tuple.Create(newRSX, rs.Item2, rs.Item3);
+            rs = Tuple.Create(newRSX, rs.Item2, rs.Item3);
+            changed = true;
           }
           if (ep.Y <= pos.Y && ep.X >= pos.X && ep.X < pos.X + width) {
             var diff = pos.Y - ep.Y;
             var newRSY = Math.Min(rs.Item2, diff);
-            ResidualSpace[ep] = Tuple.Create(rs.Item1, newRSY, rs.Item3);
+            rs = Tuple.Create(rs.Item1, newRSY, rs.Item3);
+            changed = true;
           }
         }
         if (ep.Z <= pos.Z && 
-          ep.Y >= pos.Y && ep.Y < pos.Y + item.Height &&
-          ep.X >= pos.X && ep.X < pos.X + width) {
-            var diff = pos.Z - ep.Z;
-            var newRSZ = Math.Min(rs.Item3, diff);
-            ResidualSpace[ep] = Tuple.Create(rs.Item1, rs.Item2, newRSZ);
+            ep.Y >= pos.Y && ep.Y < pos.Y + item.Height &&
+            ep.X >= pos.X && ep.X < pos.X + width) {
+          var diff = pos.Z - ep.Z;
+          var newRSZ = Math.Min(rs.Item3, diff);
+          rs = Tuple.Create(rs.Item1, rs.Item2, newRSZ);
+          changed = true;
+        }
+        if (changed) {
+          if (IsNonZero(rs) && !IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), rs)) {
+            ResidualSpace[ep] = rs;
+          } else {
+            ExtremePoints.Remove(ep);
+            ResidualSpace.Remove(ep);
+          }
         }
       }
@@ -544 +608 @@
         return new Vector3D(a.X - b.X, a.Y - b.Y, a.Z - b.Z);
       }
+
+      public override bool Equals(object obj) {
+        var packPos = obj as PackingPosition;
+        if (packPos != null) {
+          return X == packPos.X && Y == packPos.Y && Z == packPos.Z;
+        }
+        var vec = obj as Vector3D;
+        if (vec != null) {
+          return X == vec.X && Y == vec.Y && Z == vec.Z;
+        }
+        return false;
+      }
     }
 
@@ -553 +629 @@
       public Line3D(Vector3D point, Vector3D direction) {
         Point = point;
+        Direction = direction;
+      }
+      public Line3D(PackingPosition position, Vector3D direction) {
+        Point = new Vector3D(position);
         Direction = direction;
       }