Changeset 9598 for branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/PackingPlans

Timestamp:

06/07/13 15:35:12 (12 years ago)

Author:

jhelm

Message:

#1966: Fixed a bug which caused the stacking-contraint to be wrongly enforced; Did some cleanup;

Location:

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/PackingPlans

Files:

• BinPacking.cs (modified) (3 diffs)
• BinPacking2D.cs (modified) (3 diffs)
• BinPacking3D.cs (modified) (9 diffs)

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/PackingPlans/BinPacking.cs

@@ -105 +105 @@
     }
 
+
+    public int PointOccupation(D position) {
+      foreach (var ipEntry in ItemPositions) {
+        if (ItemMeasures[ipEntry.Key].EnclosesPoint(ipEntry.Value, position))
+          return ipEntry.Key;
+      }
+      return -1;
+    }
     public bool IsPointOccupied(D position) {
       foreach (var ipEntry in ItemPositions) {
@@ -110 +118 @@
           return true;
       }
-
       return false;
     }
     public bool IsPositionFeasible(I currentItem, D position) {
-      //In this case feasability is defined as following: 1. the item fits into the bin-borders; 2. the item does not collide with another already packed item
+      //In this case feasability is defined as following: 1. the item fits into the bin-borders; 2. the point is supported by something; 3. the item does not collide with another already packed item
       if (!BinMeasures.Encloses(position, currentItem))
         return false;
@@ -127 +134 @@
     public abstract int ShortestPossibleSideFromPoint (D position);
     public abstract bool IsStaticStable (I item, D position);
-    
-    //public bool IsPositionFeasible1(I currentItem, D position) {
-    //  if (!BinMeasures.Encloses(position, currentItem))
-    //    return false;
-
-    //  return OccupiedPoints.IsPositionFeasible (currentItem, position);
-    //}
   }   
 }

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/PackingPlans/BinPacking2D.cs

@@ -62 +62 @@
       if (sourcePointX.X < BinMeasures.Width && sourcePointX.Y < BinMeasures.Height) {
         //Traversing down the y-axis        
-        while (sourcePointX.Y > 0 && !IsPointOccupied(new TwoDimensionalPacking(0, sourcePointX.X, sourcePointX.Y - 1))) {
+        while (sourcePointX.Y > 0 && (-1).Equals(IsPointOccupied(new TwoDimensionalPacking(0, sourcePointX.X, sourcePointX.Y - 1)))) {
           sourcePointX.Y--;
         }
@@ -75 +75 @@
       if (sourcePointY.X < BinMeasures.Width && sourcePointY.Y < BinMeasures.Height) {
         //Traversing down the x-axis  
-        while (sourcePointY.X > 0 && !IsPointOccupied(new TwoDimensionalPacking (0,sourcePointY.X - 1, sourcePointY.Y))) {
+        while (sourcePointY.X > 0 && (-1).Equals(IsPointOccupied(new TwoDimensionalPacking (0,sourcePointY.X - 1, sourcePointY.Y)))) {
           sourcePointY.X--;
         }
@@ -166 +166 @@
     }
 
-
     public override int ShortestPossibleSideFromPoint(TwoDimensionalPacking position) {
       int shortestSide = int.MaxValue;

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/PackingPlans/BinPacking3D.cs

@@ -61 +61 @@
       var sourcePointX = new ThreeDimensionalPacking(0, position.X + newWidth, position.Y, position.Z);
       if (sourcePointX.X < BinMeasures.Width && sourcePointX.Y < BinMeasures.Height && sourcePointX.Z < BinMeasures.Depth) {
-        //Traversing down the y-axis                                                                            
-        int currentYValue = sourcePointX.Y;
-        while (currentYValue > 0 && !IsPointOccupied(new ThreeDimensionalPacking (0, sourcePointX.X, currentYValue, sourcePointX.Z))) {
-          currentYValue--;
-        }
-        ExtremePoints.Add(new ThreeDimensionalPacking(0, sourcePointX.X, currentYValue, sourcePointX.Z));
-
-        //Traversing down the z-axis
-        int currentZValue = sourcePointX.Z;
-        while (currentZValue > 0 && !IsPointOccupied(new ThreeDimensionalPacking (0, sourcePointX.X, sourcePointX.Y, currentZValue - 1))) {
-          currentZValue--;
-        }
-        ExtremePoints.Add(new ThreeDimensionalPacking(0, sourcePointX.X, sourcePointX.Y, currentZValue));
+        //Traversing down the y-axis            
+        ThreeDimensionalPacking current = new ThreeDimensionalPacking(0, sourcePointX.X, sourcePointX.Y, sourcePointX.Z);
+        while (current.Y > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveDown (current))) {
+          current = ThreeDimensionalPacking.MoveDown(current);
+        }
+        ExtremePoints.Add((ThreeDimensionalPacking)current.Clone());
+        while (current.X > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveLeft(current))) {
+          current = ThreeDimensionalPacking.MoveLeft(current);
+        }
+        ExtremePoints.Add(current);
+
+        //Traversing down the z-axis                 
+        current = new ThreeDimensionalPacking(0, sourcePointX.X, sourcePointX.Y, sourcePointX.Z);
+        while (current.Z > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveBack (current))) {
+          current = ThreeDimensionalPacking.MoveBack(current);
+        }
+        ExtremePoints.Add((ThreeDimensionalPacking)current.Clone());
+        while (current.Y > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveDown(current))) {
+          current = ThreeDimensionalPacking.MoveDown(current);
+        }
+        ExtremePoints.Add(current);
       }
 
@@ -82 +90 @@
       var sourcePointY = new ThreeDimensionalPacking(0, position.X, position.Y + newItem.Height, position.Z);
       if (sourcePointY.X < BinMeasures.Width && sourcePointY.Y < BinMeasures.Height && sourcePointY.Z < BinMeasures.Depth) {
-        //Traversing down the x-axis  
-        int currentXValue = sourcePointY.X;
-        while (currentXValue > 0 && !IsPointOccupied(new ThreeDimensionalPacking (0, currentXValue - 1, sourcePointY.Y, sourcePointY.Z))) {
-          currentXValue--;
-        }
-        ExtremePoints.Add(new ThreeDimensionalPacking(0, currentXValue, sourcePointY.Y, sourcePointY.Z));
-
-        //Traversing down the z-axis
-        int currentZValue = sourcePointY.Z;
-        while (currentZValue > 0 && !IsPointOccupied(new ThreeDimensionalPacking (0, sourcePointY.X, sourcePointY.Y, currentZValue - 1))) {
-          currentZValue--;
-        }
-        ExtremePoints.Add(new ThreeDimensionalPacking(0, sourcePointY.X, sourcePointY.Y, currentZValue));
+        //Traversing down the x-axis          
+        ThreeDimensionalPacking current = new ThreeDimensionalPacking(0, sourcePointY.X, sourcePointY.Y, sourcePointY.Z);
+        while (current.X > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveLeft(current))) {
+          current = ThreeDimensionalPacking.MoveLeft(current);
+        }
+        ExtremePoints.Add((ThreeDimensionalPacking)current.Clone());
+        while (current.Y > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveDown(current))) {
+          current = ThreeDimensionalPacking.MoveDown(current);
+        }
+        ExtremePoints.Add(current);
+
+        //Traversing down the z-axis                                                                   
+        current = new ThreeDimensionalPacking(0, sourcePointY.X, sourcePointY.Y, sourcePointY.Z);
+        while (current.Z > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveBack(current))) {
+          current = ThreeDimensionalPacking.MoveBack(current);
+        }
+        ExtremePoints.Add((ThreeDimensionalPacking)current.Clone());
+        while (current.Y > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveDown(current))) {
+          current = ThreeDimensionalPacking.MoveDown(current);
+        }
+        ExtremePoints.Add(current);
       }
 
@@ -104 +120 @@
       var sourcePointZ = new ThreeDimensionalPacking(0, position.X, position.Y, position.Z + newDepth);
       if (sourcePointZ.X < BinMeasures.Width && sourcePointZ.Y < BinMeasures.Height && sourcePointZ.Z < BinMeasures.Depth) {
-        //Traversing down the x-axis  
-        int currentXValue = sourcePointZ.X;
-        while (currentXValue > 0 && !IsPointOccupied(new ThreeDimensionalPacking (0, currentXValue - 1, sourcePointZ.Y, sourcePointZ.Z))) {
-          currentXValue--;
-        }
-        ExtremePoints.Add(new ThreeDimensionalPacking(0, currentXValue, sourcePointZ.Y, sourcePointZ.Z));
-
-        //Traversing down the y-axis                                                                            
-        int currentYValue = sourcePointZ.Y;
-        while (currentYValue > 0 && !IsPointOccupied(new ThreeDimensionalPacking (0, sourcePointZ.X, currentYValue, sourcePointZ.Z))) {
-          currentYValue--;
-        }
-        ExtremePoints.Add(new ThreeDimensionalPacking(0, sourcePointZ.X, currentYValue, sourcePointZ.Z));
+        //Traversing down the x-axis                                                                             
+        ThreeDimensionalPacking current = new ThreeDimensionalPacking(0, sourcePointZ.X, sourcePointZ.Y, sourcePointZ.Z);
+        while (current.X > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveLeft(current))) {
+          current = ThreeDimensionalPacking.MoveLeft(current);
+        }
+        ExtremePoints.Add((ThreeDimensionalPacking)current.Clone());
+        while (current.Y > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveDown(current))) {
+          current = ThreeDimensionalPacking.MoveDown(current);
+        }
+        ExtremePoints.Add(current);
+
+        //Traversing down the y-axis                                                                     
+        current = new ThreeDimensionalPacking(0, sourcePointZ.X, sourcePointZ.Y, sourcePointZ.Z);
+        while (current.Y > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveDown(current))) {
+          current = ThreeDimensionalPacking.MoveDown(current);
+        }
+        ExtremePoints.Add((ThreeDimensionalPacking)current.Clone());
+        while (current.X > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveLeft(current))) {
+          current = ThreeDimensionalPacking.MoveLeft(current);
+        }
+        ExtremePoints.Add(current);
       }
 
@@ -122 +146 @@
         OrderBy(ep => ep.Z).
         ThenBy(ep => ep.X).
-        ThenBy(ep => ep.Y).
-        ThenBy(ep => ShortestPossibleSideFromPoint(ep)));
+        ThenBy(ep => ep.Y)//.ThenBy(ep => ShortestPossibleSideFromPoint(ep)) 
+        );
     }
 
@@ -136 +160 @@
       int epIndex = 0;
       while (epIndex < ExtremePoints.Count && (
-        !IsPositionFeasible(item, ExtremePoints.ElementAt(epIndex)) || (stackingConstraints && !IsStaticStable(item, ExtremePoints.ElementAt(epIndex)))
+        !IsPositionFeasible(item, ExtremePoints.ElementAt(epIndex))
+        || !IsSupportedByAtLeastOnePoint(item, ExtremePoints.ElementAt(epIndex))
+        || (stackingConstraints && !IsStaticStable(item, ExtremePoints.ElementAt(epIndex)))
+        || (stackingConstraints && !IsWeightSupported(item, ExtremePoints.ElementAt(epIndex)))
       )) { epIndex++; }
 
@@ -146 +173 @@
       return null;
     }
+
     public override ThreeDimensionalPacking FindPositionBySliding(CuboidPackingItem measures, bool rotated) {
       //Starting-position at upper right corner (=left bottom point of item-rectangle is at position item.width,item.height)
@@ -217 +245 @@
       }
     }
-    
-
-    [Storable]
-    private bool depthWasDoubled = false;
-    public void DoubleDepth() {
-      if (!depthWasDoubled) {
-        var oldDepth = BinMeasures.Depth;
-        BinMeasures.Depth = BinMeasures.Depth * 2;
-        //OccupiedPoints.ChangeBinMeasures(BinMeasures);
-        depthWasDoubled = true;
-      }
-    }
-
+                                                   
     public override int ShortestPossibleSideFromPoint(ThreeDimensionalPacking position) {
 
@@ -265 +281 @@
 
       if (IsPointOccupied (new ThreeDimensionalPacking (0, position.X, position.Y - 1, position.Z))
-        && IsPointOccupied (new ThreeDimensionalPacking (0, position.X + item.Width - 1, position.Y - 1, position.Z))
-        && IsPointOccupied (new ThreeDimensionalPacking (0, position.X, position.Y - 1, position.Z + item.Depth - 1))
-        && IsPointOccupied (new ThreeDimensionalPacking (0, position.X + item.Width - 1, position.Y - 1, position.Z + item.Depth - 1)))
+        && IsPointOccupied (new ThreeDimensionalPacking (0, position.X + item.Width, position.Y - 1, position.Z))
+        && IsPointOccupied (new ThreeDimensionalPacking (0, position.X, position.Y - 1, position.Z + item.Depth))
+        && IsPointOccupied (new ThreeDimensionalPacking (0, position.X + item.Width, position.Y - 1, position.Z + item.Depth)))
         return true;
 
@@ -290 +306 @@
       return false;
     }
+
+
+    [Storable]
+    private bool depthWasDoubled = false;
+    public void DoubleDepth() {
+      if (!depthWasDoubled) {
+        var oldDepth = BinMeasures.Depth;
+        BinMeasures.Depth = BinMeasures.Depth * 2;
+        //OccupiedPoints.ChangeBinMeasures(BinMeasures);
+        depthWasDoubled = true;
+      }
+    }
+          
+    public bool IsSupportedByAtLeastOnePoint(CuboidPackingItem item, ThreeDimensionalPacking position) {
+      if (position.Y == 0)
+        return true;
+
+      int y = position.Y - 1;
+      for (int x = position.X; x < position.X + item.Width; x++)
+        for (int z = position.Z; z < position.Z + item.Depth; z++)
+          if (IsPointOccupied(new ThreeDimensionalPacking(0, x, y, z)))
+            return true;
+      
+      return false;
+    }
+    public bool IsWeightSupported(CuboidPackingItem item, ThreeDimensionalPacking ep) {
+      if (ep.Y == 0)
+        return true;
+
+      if (ItemMeasures[PointOccupation(new ThreeDimensionalPacking(0, ep.X, ep.Y - 1, ep.Z))].SupportsStacking(item)
+        && ItemMeasures[PointOccupation(new ThreeDimensionalPacking(0, ep.X + item.Width, ep.Y - 1, ep.Z))].SupportsStacking(item)
+        && ItemMeasures[PointOccupation(new ThreeDimensionalPacking(0, ep.X, ep.Y - 1, ep.Z + item.Depth))].SupportsStacking(item)
+        && ItemMeasures[PointOccupation(new ThreeDimensionalPacking(0, ep.X + item.Width, ep.Y - 1, ep.Z + item.Depth))].SupportsStacking(item))
+        return true;
+
+      return false;
+    }
   }
 }