Changeset 15308
 Timestamp:
 08/06/17 23:04:05 (3 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

branches/2817BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs
r15307 r15308 65 65 66 66 public override void PackItem(int itemID, PackingItem item, PackingPosition position) { 67 // base call is deliberately omitted, because UpdateResidualSpace needs to be fitted in before 68 // generating new extreme points 69 Items[itemID] = item; 70 Positions[itemID] = position; 67 71 ExtremePoints.Remove(position); 68 72 ResidualSpace.Remove(position); 69 73 UpdateResidualSpace(item, position); 70 base.PackItem(itemID, item, position); 74 GenerateNewExtremePointsForNewItem(item, position); 75 // if an item is fit in below, before, or left of another its extreme points have to be regenerated 76 foreach (var above in GetItemsAbove(position)) 77 GenerateNewExtremePointsForNewItem(above.Item2, above.Item1); 78 foreach (var front in GetItemsInfront(position)) 79 GenerateNewExtremePointsForNewItem(front.Item2, front.Item1); 80 foreach (var right in GetItemsOnRight(position)) 81 GenerateNewExtremePointsForNewItem(right.Item2, right.Item1); 82 AddNewItemToOccupationLayers(itemID, item, position); 71 83 } 72 84 … … 82 94 var below = ProjectDown(sourcePoint); 83 95 var residualSpace = CalculateResidualSpace(below); 84 if (!IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) { 96 if (IsNonZero(residualSpace) 97 && !IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) { 85 98 // add only if the projected point's residual space is not a subspace 86 99 // of another extreme point's residual space … … 91 104 var back = ProjectBackward(sourcePoint); 92 105 residualSpace = CalculateResidualSpace(back); 93 if (!IsWithinResidualSpaceOfAnotherExtremePoint(back, residualSpace)) { 106 if (IsNonZero(residualSpace) 107 && !IsWithinResidualSpaceOfAnotherExtremePoint(back, residualSpace)) { 94 108 // add only if the projected point's residual space is not a subspace 95 109 // of another extreme point's residual space … … 105 119 var left = ProjectLeft(sourcePoint); 106 120 var residualSpace = CalculateResidualSpace(left); 107 if (!IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) { 121 if (IsNonZero(residualSpace) 122 && !IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) { 108 123 // add only if the projected point's residual space is not a subspace 109 124 // of another extreme point's residual space … … 114 129 var back = ProjectBackward(sourcePoint); 115 130 residualSpace = CalculateResidualSpace(back); 116 if (!IsWithinResidualSpaceOfAnotherExtremePoint(back, residualSpace)) { 131 if (IsNonZero(residualSpace) 132 && !IsWithinResidualSpaceOfAnotherExtremePoint(back, residualSpace)) { 117 133 // add only if the projected point's residual space is not a subspace 118 134 // of another extreme point's residual space … … 128 144 var below = ProjectDown(sourcePoint); 129 145 var residualSpace = CalculateResidualSpace(below); 130 if (!IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) { 146 if (IsNonZero(residualSpace) 147 && !IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) { 131 148 // add only if the projected point's residual space is not a subspace 132 149 // of another extreme point's residual space … … 137 154 var left = ProjectLeft(sourcePoint); 138 155 residualSpace = CalculateResidualSpace(left); 139 if (!IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) { 156 if (IsNonZero(residualSpace) 157 && !IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) { 140 158 // add only if the projected point's residual space is not a subspace 141 159 // of another extreme point's residual space … … 146 164 } 147 165 166 private bool IsNonZero(Tuple<int, int, int> rs) { 167 return rs.Item1 > 0 && rs.Item2 > 0 && rs.Item3 > 0; 168 } 169 148 170 private bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> residualSpace) { 149 var eps = ExtremePoints.Where(x => pos.IsInside(x, ResidualSpace[x]));171 var eps = ExtremePoints.Where(x => !pos.Equals(x) && pos.IsInside(x, ResidualSpace[x])); 150 172 return eps.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, residualSpace, x, ResidualSpace[x])); 151 173 } … … 158 180 private bool AddExtremePoint(PackingPosition pos) { 159 181 if (ExtremePoints.Add(pos)) { 160 var rs = Tuple.Create(BinShape.Width  pos.X, BinShape.Height  pos.Y, BinShape.Depth  pos.Z);182 var rs = CalculateResidualSpace(new Vector3D(pos)); 161 183 ResidualSpace.Add(pos, rs); 162 184 // Check if existing extreme points are shadowed by the new point … … 239 261 .Where(x => x != null && x.Y >= pos.Y) 240 262 .MinItems(x => x.Y).First(); 263 } 264 265 private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsAbove(PackingPosition pos) { 266 var line = new Line3D(pos, new Vector3D(0, 1, 0)); 267 return Items.Select(x => new { 268 Item = x.Value, 269 Position = Positions[x.Key], 270 Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Bottom)) 271 }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y) 272 .Select(x => Tuple.Create(x.Position, x.Item)); 273 } 274 275 private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsInfront(PackingPosition pos) { 276 var line = new Line3D(pos, new Vector3D(0, 0, 1)); 277 return Items.Select(x => new { 278 Item = x.Value, 279 Position = Positions[x.Key], 280 Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Back)) 281 }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y) 282 .Select(x => Tuple.Create(x.Position, x.Item)); 283 } 284 285 private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnRight(PackingPosition pos) { 286 var line = new Line3D(pos, new Vector3D(1, 0, 0)); 287 return Items.Select(x => new { 288 Item = x.Value, 289 Position = Positions[x.Key], 290 Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Left)) 291 }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y) 292 .Select(x => Tuple.Create(x.Position, x.Item)); 241 293 } 242 294 … … 429 481 430 482 public void UpdateResidualSpace(PackingItem item, PackingPosition pos) { 431 foreach (var ep in ExtremePoints ) {483 foreach (var ep in ExtremePoints.ToList()) { 432 484 var rs = ResidualSpace[ep]; 433 485 var depth = pos.Rotated ? item.Width : item.Depth; 434 486 var width = pos.Rotated ? item.Depth : item.Width; 487 var changed = false; 435 488 if (ep.Z >= pos.Z && ep.Z < pos.Z + depth) { 436 489 if (ep.X <= pos.X && ep.Y >= pos.Y && ep.Y < pos.Y + item.Height) { 437 490 var diff = pos.X  ep.X; 438 491 var newRSX = Math.Min(rs.Item1, diff); 439 ResidualSpace[ep] = Tuple.Create(newRSX, rs.Item2, rs.Item3); 492 rs = Tuple.Create(newRSX, rs.Item2, rs.Item3); 493 changed = true; 440 494 } 441 495 if (ep.Y <= pos.Y && ep.X >= pos.X && ep.X < pos.X + width) { 442 496 var diff = pos.Y  ep.Y; 443 497 var newRSY = Math.Min(rs.Item2, diff); 444 ResidualSpace[ep] = Tuple.Create(rs.Item1, newRSY, rs.Item3); 498 rs = Tuple.Create(rs.Item1, newRSY, rs.Item3); 499 changed = true; 445 500 } 446 501 } 447 502 if (ep.Z <= pos.Z && 448 ep.Y >= pos.Y && ep.Y < pos.Y + item.Height && 449 ep.X >= pos.X && ep.X < pos.X + width) { 450 var diff = pos.Z  ep.Z; 451 var newRSZ = Math.Min(rs.Item3, diff); 452 ResidualSpace[ep] = Tuple.Create(rs.Item1, rs.Item2, newRSZ); 503 ep.Y >= pos.Y && ep.Y < pos.Y + item.Height && 504 ep.X >= pos.X && ep.X < pos.X + width) { 505 var diff = pos.Z  ep.Z; 506 var newRSZ = Math.Min(rs.Item3, diff); 507 rs = Tuple.Create(rs.Item1, rs.Item2, newRSZ); 508 changed = true; 509 } 510 if (changed) { 511 if (IsNonZero(rs) && !IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), rs)) { 512 ResidualSpace[ep] = rs; 513 } else { 514 ExtremePoints.Remove(ep); 515 ResidualSpace.Remove(ep); 516 } 453 517 } 454 518 } … … 544 608 return new Vector3D(a.X  b.X, a.Y  b.Y, a.Z  b.Z); 545 609 } 610 611 public override bool Equals(object obj) { 612 var packPos = obj as PackingPosition; 613 if (packPos != null) { 614 return X == packPos.X && Y == packPos.Y && Z == packPos.Z; 615 } 616 var vec = obj as Vector3D; 617 if (vec != null) { 618 return X == vec.X && Y == vec.Y && Z == vec.Z; 619 } 620 return false; 621 } 546 622 } 547 623 … … 553 629 public Line3D(Vector3D point, Vector3D direction) { 554 630 Point = point; 631 Direction = direction; 632 } 633 public Line3D(PackingPosition position, Vector3D direction) { 634 Point = new Vector3D(position); 555 635 Direction = direction; 556 636 }
Note: See TracChangeset
for help on using the changeset viewer.