Changeset 14976 for branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs
- Timestamp:
- 05/12/17 14:10:55 (7 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs
r14162 r14976 20 20 #endregion 21 21 22 using System; 22 23 using System.Collections.Generic; 23 24 using System.Linq; … … 35 36 : base(binShape) { 36 37 ExtremePoints = new SortedSet<PackingPosition>(); 37 ExtremePoints.Add(binShape.Origin); 38 ResidualSpace = new Dictionary<PackingPosition, Tuple<int,int,int>>(); 39 AddExtremePoint(binShape.Origin); 38 40 InitializeOccupationLayers(); 39 41 } … … 43 45 : base(original, cloner) { 44 46 this.ExtremePoints = new SortedSet<PackingPosition>(original.ExtremePoints.Select(p => cloner.Clone(p))); 47 this.ResidualSpace = new Dictionary<PackingPosition, Tuple<int, int, int>>(); 48 foreach (var o in original.ResidualSpace) 49 this.ResidualSpace.Add(cloner.Clone(o.Key), Tuple.Create(o.Value.Item1, o.Value.Item2, o.Value.Item3)); 45 50 } 46 51 public override IDeepCloneable Clone(Cloner cloner) { … … 60 65 current = PackingPosition.MoveDown(current); 61 66 } 62 ExtremePoints.Add((PackingPosition)current.Clone());67 AddExtremePoint((PackingPosition)current.Clone()); 63 68 while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) { 64 69 current = PackingPosition.MoveLeft(current); 65 70 } 66 ExtremePoints.Add(current);71 AddExtremePoint(current); 67 72 68 73 //Traversing down the z-axis … … 71 76 current = PackingPosition.MoveBack(current); 72 77 } 73 ExtremePoints.Add((PackingPosition)current.Clone());74 while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) { 75 current = PackingPosition.MoveDown(current); 76 } 77 ExtremePoints.Add(current);78 AddExtremePoint((PackingPosition)current.Clone()); 79 while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) { 80 current = PackingPosition.MoveDown(current); 81 } 82 AddExtremePoint(current); 78 83 } 79 84 … … 86 91 current = PackingPosition.MoveLeft(current); 87 92 } 88 ExtremePoints.Add((PackingPosition)current.Clone());89 while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) { 90 current = PackingPosition.MoveDown(current); 91 } 92 ExtremePoints.Add(current);93 AddExtremePoint((PackingPosition)current.Clone()); 94 while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) { 95 current = PackingPosition.MoveDown(current); 96 } 97 AddExtremePoint(current); 93 98 94 99 //Traversing down the z-axis … … 97 102 current = PackingPosition.MoveBack(current); 98 103 } 99 ExtremePoints.Add((PackingPosition)current.Clone());100 while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) { 101 current = PackingPosition.MoveDown(current); 102 } 103 ExtremePoints.Add(current);104 AddExtremePoint((PackingPosition)current.Clone()); 105 while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) { 106 current = PackingPosition.MoveDown(current); 107 } 108 AddExtremePoint(current); 104 109 } 105 110 … … 112 117 current = PackingPosition.MoveLeft(current); 113 118 } 114 ExtremePoints.Add((PackingPosition)current.Clone());115 while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) { 116 current = PackingPosition.MoveDown(current); 117 } 118 ExtremePoints.Add(current);119 AddExtremePoint((PackingPosition)current.Clone()); 120 while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) { 121 current = PackingPosition.MoveDown(current); 122 } 123 AddExtremePoint(current); 119 124 120 125 //Traversing down the y-axis … … 123 128 current = PackingPosition.MoveDown(current); 124 129 } 125 ExtremePoints.Add((PackingPosition)current.Clone());130 AddExtremePoint((PackingPosition)current.Clone()); 126 131 while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) { 127 132 current = PackingPosition.MoveLeft(current); 128 133 } 129 ExtremePoints.Add(current); 134 AddExtremePoint(current); 135 } 136 } 137 138 private void AddExtremePoint(PackingPosition current) { 139 if (ExtremePoints.Add(current)) { 140 var tuple = Tuple.Create(BinShape.Width - current.X, BinShape.Height - current.Y, BinShape.Depth - current.Z); 141 ResidualSpace.Add(current, tuple); 130 142 } 131 143 } … … 137 149 item.Height, 138 150 rotated ? item.Width : item.Depth, 139 item.TargetBin );151 item.TargetBin, item.Weight, item.Material); 140 152 141 153 int epIndex = 0; … … 212 224 if (positionFound != null) { 213 225 PackItem(itemID, item, positionFound); 226 if (!(positionFound.X == 0 && positionFound.Y == 0 && positionFound.Z == 0)) { 227 UpdateResidualSpace(item, positionFound); 228 } 214 229 sequence.Remove(itemID); 215 230 } 216 231 } 232 } 233 public override bool ExtremePointBasedPacking(int itemID, IList<PackingItem> items, bool stackingConstraints) { 234 var item = items[itemID]; 235 var positionFound = FindExtremePointForItem(item, false, stackingConstraints); 236 if (positionFound != null) { 237 PackItem(itemID, item, positionFound); 238 return true; 239 } 240 return false; 217 241 } 218 242 public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray) { … … 227 251 } 228 252 } 229 230 253 public override int ShortestPossibleSideFromPoint(PackingPosition position) { 231 254 … … 320 343 for (int i = z1; i <= z2; i++) 321 344 result.AddRange(OccupationLayers[i]); 322 323 345 return result; 324 346 } 347 348 public void UpdateResidualSpace(PackingItem item, PackingPosition pos) { 349 foreach (var ep in ExtremePoints) { 350 if (ep.Z >= pos.Z && ep.Z <= pos.Z + item.Depth) { 351 if (ep.X <= pos.X && ep.Y >= pos.Y && ep.Y <= pos.Y + item.Height) { 352 var diff = pos.X - ep.X; 353 var newRSX = ResidualSpace[ep].Item1 < diff ? ResidualSpace[ep].Item1 : diff; 354 ResidualSpace[ep] = Tuple.Create(newRSX, ResidualSpace[ep].Item2, ResidualSpace[ep].Item3); 355 } 356 if (ep.Y <= pos.Y && ep.X >= pos.X && ep.X <= pos.X + item.Width) { 357 var diff = pos.Y - ep.Y; 358 var newRSY = ResidualSpace[ep].Item2 < diff ? ResidualSpace[ep].Item2 : diff; 359 ResidualSpace[ep] = Tuple.Create(ResidualSpace[ep].Item1, newRSY, ResidualSpace[ep].Item3); 360 } 361 } 362 if (ep.Z <= pos.Z && 363 ep.Y >= pos.Y && ep.Y <= pos.Y + item.Height && 364 ep.X >= pos.X && ep.X <= pos.X + item.Width) { 365 var diff = pos.Z - ep.Z; 366 var newRSZ = ResidualSpace[ep].Item3 < diff ? ResidualSpace[ep].Item3 : diff; 367 ResidualSpace[ep] = Tuple.Create(ResidualSpace[ep].Item1, ResidualSpace[ep].Item2, newRSZ); 368 } 369 } 370 return; 371 } 372 public int GetResidualSpace(PackingItem item, PackingPosition ep) { 373 return ((ResidualSpace[ep].Item1 - item.Width) + 374 (ResidualSpace[ep].Item2 - item.Height) + 375 (ResidualSpace[ep].Item3 - item.Depth)); 376 } 377 } 325 378 } 326 327 }
Note: See TracChangeset
for help on using the changeset viewer.