Changeset 15306
 Timestamp:
 08/04/17 17:00:16 (18 months ago)
 Location:
 branches/2817BinPackingSpeedup
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

branches/2817BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml.cs
r15167 r15306 153 153 modelGroup.Children.Add(selectedModel); 154 154 } 155 } 156 157 // draw extremepoints 158 foreach (var ep in packing.ExtremePoints) { 159 var epModel = new GeometryModel3D { Geometry = new MeshGeometry3D(), Material = new DiffuseMaterial() { Brush = new SolidColorBrush(Colors.Red) } }; 160 AddSolidCube((MeshGeometry3D)epModel.Geometry, ep.X, ep.Y, ep.Z, 10, 10, 10); 161 modelGroup.Children.Add(epModel); 155 162 } 156 163 
branches/2817BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs
r15305 r15306 65 65 66 66 public override void PackItem(int itemID, PackingItem item, PackingPosition position) { 67 ExtremePoints.Remove(position); 67 68 ResidualSpace.Remove(position); 69 UpdateResidualSpace(item, position); 68 70 base.PackItem(itemID, item, position); 69 71 } … … 78 80 if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) { 79 81 // Projecting onto the XZplane 80 var line = new Line3D(sourcePoint, new Vector3D(0, 1, 0)); 81 var below = itemPlacement.Select(x => new Plane3D(x.Position, x.Item, Side.Top)) 82 .Concat(new[] { new Plane3D(BinShape, Side.Bottom) }) 83 .Select(x => x.Intersect(line)) 84 .Where(x => x != null && x.Y <= sourcePoint.Y) 85 .MaxItems(x => x.Y).First(); 82 var below = ProjectDown(sourcePoint); 86 83 var residualSpace = CalculateResidualSpace(below); 87 var eps = ExtremePoints.Where(x => IsInside(below, x, ResidualSpace[x])); 88 if (!eps.Any(x => ResidualSpace[x].Item1 >= below.X  x.X + residualSpace.Item1 89 && ResidualSpace[x].Item2 >= below.Y  x.Y + residualSpace.Item2 90 && ResidualSpace[x].Item3 >= below.Z  x.Z + residualSpace.Item3)) { 84 if (!IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) { 91 85 // add only if the projected point's residual space is not a subspace 92 86 // of another extreme point's residual space … … 94 88 AddExtremePoint(belowPoint); 95 89 } 96 line = new Line3D(sourcePoint, new Vector3D(0, 0, 1));97 90 // Projecting onto the XYplane 98 var back = itemPlacement.Select(x => new Plane3D(x.Position, x.Item, Side.Front)) 99 .Concat(new[] { new Plane3D(BinShape, Side.Back) }) 100 .Select(x => x.Intersect(line)) 101 .Where(x => x != null && x.Z <= sourcePoint.Z) 102 .MaxItems(x => x.Y).First(); 103 residualSpace = CalculateResidualSpace(below); 104 eps = ExtremePoints.Where(x => IsInside(below, x, ResidualSpace[x])); 105 if (!eps.Any(x => ResidualSpace[x].Item1 >= below.X  x.X + residualSpace.Item1 106 && ResidualSpace[x].Item2 >= below.Y  x.Y + residualSpace.Item2 107 && ResidualSpace[x].Item3 >= below.Z  x.Z + residualSpace.Item3)) { 91 var back = ProjectBackward(sourcePoint); 92 residualSpace = CalculateResidualSpace(back); 93 if (!IsWithinResidualSpaceOfAnotherExtremePoint(back, residualSpace)) { 108 94 // add only if the projected point's residual space is not a subspace 109 95 // of another extreme point's residual space … … 117 103 if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) { 118 104 // Projecting onto the YZplane 119 var line = new Line3D(sourcePoint, new Vector3D(1, 0, 0)); 120 var left = itemPlacement.Select(x => new Plane3D(x.Position, x.Item, Side.Right)) 121 .Concat(new[] { new Plane3D(BinShape, Side.Left) }) 122 .Select(x => x.Intersect(line)) 123 .Where(x => x != null && x.X <= sourcePoint.X) 124 .MaxItems(x => x.Y).First(); 105 var left = ProjectLeft(sourcePoint); 125 106 var residualSpace = CalculateResidualSpace(left); 126 var eps = ExtremePoints.Where(x => IsInside(left, x, ResidualSpace[x])); 127 if (!eps.Any(x => ResidualSpace[x].Item1 >= left.X  x.X + residualSpace.Item1 128 && ResidualSpace[x].Item2 >= left.Y  x.Y + residualSpace.Item2 129 && ResidualSpace[x].Item3 >= left.Z  x.Z + residualSpace.Item3)) { 107 if (!IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) { 130 108 // add only if the projected point's residual space is not a subspace 131 109 // of another extreme point's residual space … … 133 111 AddExtremePoint(leftPoint); 134 112 } 135 line = new Line3D(sourcePoint, new Vector3D(0, 0, 1));136 113 // Projecting onto the XYplane 137 var back = itemPlacement.Select(x => new Plane3D(x.Position, x.Item, Side.Front)) 138 .Concat(new[] { new Plane3D(BinShape, Side.Back) }) 139 .Select(x => x.Intersect(line)) 140 .Where(x => x != null && x.Z <= sourcePoint.Z) 141 .MaxItems(x => x.Y).First(); 142 residualSpace = CalculateResidualSpace(left); 143 eps = ExtremePoints.Where(x => IsInside(left, x, ResidualSpace[x])); 144 if (!eps.Any(x => ResidualSpace[x].Item1 >= left.X  x.X + residualSpace.Item1 145 && ResidualSpace[x].Item2 >= left.Y  x.Y + residualSpace.Item2 146 && ResidualSpace[x].Item3 >= left.Z  x.Z + residualSpace.Item3)) { 114 var back = ProjectBackward(sourcePoint); 115 residualSpace = CalculateResidualSpace(back); 116 if (!IsWithinResidualSpaceOfAnotherExtremePoint(back, residualSpace)) { 147 117 // add only if the projected point's residual space is not a subspace 148 118 // of another extreme point's residual space … … 156 126 if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) { 157 127 // Projecting onto the YZplane 158 var line = new Line3D(sourcePoint, new Vector3D(1, 0, 0)); 159 var left = itemPlacement.Select(x => new Plane3D(x.Position, x.Item, Side.Right)) 160 .Concat(new[] { new Plane3D(BinShape, Side.Left) }) 161 .Select(x => x.Intersect(line)) 162 .Where(x => x != null && x.X <= sourcePoint.X) 163 .MaxItems(x => x.Y).First(); 128 var left = ProjectLeft(sourcePoint); 164 129 var residualSpace = CalculateResidualSpace(left); 165 var eps = ExtremePoints.Where(x => IsInside(left, x, ResidualSpace[x])); 166 if (!eps.Any(x => ResidualSpace[x].Item1 >= left.X  x.X + residualSpace.Item1 167 && ResidualSpace[x].Item2 >= left.Y  x.Y + residualSpace.Item2 168 && ResidualSpace[x].Item3 >= left.Z  x.Z + residualSpace.Item3)) { 130 if (!IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) { 169 131 // add only if the projected point's residual space is not a subspace 170 132 // of another extreme point's residual space … … 173 135 } 174 136 // Projecting onto the XZplane 175 line = new Line3D(sourcePoint, new Vector3D(0, 1, 0)); 176 var below = itemPlacement.Select(x => new Plane3D(x.Position, x.Item, Side.Top)) 177 .Concat(new[] { new Plane3D(BinShape, Side.Bottom) }) 178 .Select(x => x.Intersect(line)) 179 .Where(x => x != null && x.Y <= sourcePoint.Y) 180 .MaxItems(x => x.Y).First(); 137 var below = ProjectDown(sourcePoint); 181 138 residualSpace = CalculateResidualSpace(below); 182 eps = ExtremePoints.Where(x => IsInside(below, x, ResidualSpace[x])); 183 if (!eps.Any(x => ResidualSpace[x].Item1 >= below.X  x.X + residualSpace.Item1 184 && ResidualSpace[x].Item2 >= below.Y  x.Y + residualSpace.Item2 185 && ResidualSpace[x].Item3 >= below.Z  x.Z + residualSpace.Item3)) { 139 if (!IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) { 186 140 // add only if the projected point's residual space is not a subspace 187 141 // of another extreme point's residual space … … 192 146 } 193 147 194 private bool IsBelow(PackingPosition lowerPos, PackingItem lowerItem, Vector3D upper) { 195 return lowerPos.X <= upper.X && lowerPos.X + lowerItem.Width > upper.X 196 && lowerPos.Z <= upper.Z && lowerPos.Z + lowerItem.Depth > upper.Z 197 && lowerPos.Y + lowerItem.Height < upper.Y; 198 } 199 200 private bool IsLeft(PackingPosition leftPos, PackingItem leftItem, Vector3D right) { 201 return leftPos.Y <= right.Y && leftPos.Y + leftItem.Height > right.Y 202 && leftPos.Z <= right.Z && leftPos.Z + leftItem.Depth > right.Z 203 && leftPos.X + leftItem.Width < right.X; 204 } 205 206 private bool IsBack(PackingPosition backPos, PackingItem backItem, Vector3D front) { 207 return backPos.Y <= front.Y && backPos.Y + backItem.Height > front.Y 208 && backPos.X <= front.X && backPos.X + backItem.Width > front.X 209 && backPos.Z + backItem.Depth < front.Z; 210 } 211 212 private bool AddExtremePoint(PackingPosition current) { 213 if (ExtremePoints.Add(current)) { 214 ResidualSpace.Add(current, CalculateResidualSpace(current)); 148 private bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> residualSpace) { 149 var eps = ExtremePoints.Where(x => pos.IsInside(x, ResidualSpace[x])); 150 return eps.Any(x => ResidualSpace[x].Item1 >= pos.X  x.X + residualSpace.Item1 151 && ResidualSpace[x].Item2 >= pos.Y  x.Y + residualSpace.Item2 152 && ResidualSpace[x].Item3 >= pos.Z  x.Z + residualSpace.Item3); 153 } 154 155 private bool AddExtremePoint(PackingPosition pos) { 156 if (ExtremePoints.Add(pos)) { 157 ResidualSpace.Add(pos, Tuple.Create(BinShape.Width  pos.X, BinShape.Height  pos.Y, BinShape.Depth  pos.Z)); 215 158 return true; 216 159 } … … 219 162 220 163 private Tuple<int, int, int> CalculateResidualSpace(Vector3D pos) { 221 return Tuple.Create(BinShape.Width  pos.X, BinShape.Height  pos.Y, BinShape.Depth  pos.Z); 222 } 223 224 private Tuple<int, int, int> CalculateResidualSpace(PackingPosition pos) { 225 return Tuple.Create(BinShape.Width  pos.X, BinShape.Height  pos.Y, BinShape.Depth  pos.Z); 226 } 227 228 private bool IsInside(Vector3D point, PackingPosition pos, PackingItem item) { 229 return point.X >= pos.X && point.X < pos.X + (pos.Rotated ? item.Depth : item.Width) 230 && point.Y >= pos.Y && point.Y < pos.Y + item.Height 231 && point.Z >= pos.Z && point.Z < pos.Z + (pos.Rotated ? item.Width : item.Depth); 232 } 233 234 private bool IsInside(Vector3D point, Vector3D pos, PackingItem item) { 235 return point.X >= pos.X && point.X < pos.X + item.Width 236 && point.Y >= pos.Y && point.Y < pos.Y + item.Height 237 && point.Z >= pos.Z && point.Z < pos.Z + item.Depth; 238 } 239 240 private bool IsInside(Vector3D point, PackingPosition pos, Tuple<int, int, int> rs) { 241 return point.X >= pos.X && point.X < pos.X + rs.Item1 242 && point.Y >= pos.Y && point.Y < pos.Y + rs.Item2 243 && point.Z >= pos.Z && point.Z < pos.Z + rs.Item3; 244 } 245 246 private bool IsInside(Vector3D point, Vector3D pos, Tuple<int, int, int> rs) { 247 return point.X >= pos.X && point.X < pos.X + rs.Item1 248 && point.Y >= pos.Y && point.Y < pos.Y + rs.Item2 249 && point.Z >= pos.Z && point.Z < pos.Z + rs.Item3; 164 var itemPos = Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] }); 165 var rightLimit = ProjectRight(pos); 166 var upLimit = ProjectUp(pos); 167 var forwardLimit = ProjectForward(pos); 168 return Tuple.Create(rightLimit.X  pos.X, upLimit.Y  pos.Y, forwardLimit.Z  pos.Z); 169 } 170 171 private Vector3D ProjectBackward(Vector3D pos) { 172 var line = new Line3D(pos, new Vector3D(0, 0, 1)); 173 return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] }) 174 .Select(x => new Plane3D(x.Position, x.Item, Side.Front)) 175 .Concat(new[] { new Plane3D(BinShape, Side.Back) }) 176 .Select(x => x.Intersect(line)) 177 .Where(x => x != null && x.Z <= pos.Z) 178 .MaxItems(x => x.Z).First(); 179 } 180 181 private Vector3D ProjectLeft(Vector3D pos) { 182 var line = new Line3D(pos, new Vector3D(1, 0, 0)); 183 return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] }) 184 .Select(x => new Plane3D(x.Position, x.Item, Side.Right)) 185 .Concat(new[] { new Plane3D(BinShape, Side.Left) }) 186 .Select(x => x.Intersect(line)) 187 .Where(x => x != null && x.X <= pos.X) 188 .MaxItems(x => x.X).First(); 189 } 190 191 private Vector3D ProjectDown(Vector3D pos) { 192 var line = new Line3D(pos, new Vector3D(0, 1, 0)); 193 return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] }) 194 .Select(x => new Plane3D(x.Position, x.Item, Side.Top)) 195 .Concat(new[] { new Plane3D(BinShape, Side.Bottom) }) 196 .Select(x => x.Intersect(line)) 197 .Where(x => x != null && x.Y <= pos.Y) 198 .MaxItems(x => x.Y).First(); 199 } 200 201 private Vector3D ProjectForward(Vector3D pos) { 202 var line = new Line3D(pos, new Vector3D(0, 0, 1)); 203 return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] }) 204 .Select(x => new Plane3D(x.Position, x.Item, Side.Back)) 205 .Concat(new[] { new Plane3D(BinShape, Side.Front) }) 206 .Select(x => x.Intersect(line)) 207 .Where(x => x != null && x.Z >= pos.Z) 208 .MinItems(x => x.Z).First(); 209 } 210 211 private Vector3D ProjectRight(Vector3D pos) { 212 var line = new Line3D(pos, new Vector3D(1, 0, 0)); 213 return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] }) 214 .Select(x => new Plane3D(x.Position, x.Item, Side.Left)) 215 .Concat(new[] { new Plane3D(BinShape, Side.Right) }) 216 .Select(x => x.Intersect(line)) 217 .Where(x => x != null && x.X >= pos.X) 218 .MinItems(x => x.X).First(); 219 } 220 221 private Vector3D ProjectUp(Vector3D pos) { 222 var line = new Line3D(pos, new Vector3D(0, 1, 0)); 223 return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] }) 224 .Select(x => new Plane3D(x.Position, x.Item, Side.Bottom)) 225 .Concat(new[] { new Plane3D(BinShape, Side.Top) }) 226 .Select(x => x.Intersect(line)) 227 .Where(x => x != null && x.Y >= pos.Y) 228 .MinItems(x => x.Y).First(); 250 229 } 251 230 … … 258 237 259 238 var ep = ExtremePoints.Where(x => IsPositionFeasible(newItem, x, stackingConstraints)) 260 .OrderBy(x => x.X + x.Y + x.Z) // order by manhattan distance to try those closest to origin first261 239 .FirstOrDefault(); 262 240 if (ep != null) { … … 330 308 if (positionFound != null) { 331 309 PackItem(itemID, item, positionFound); 332 if (Items.Count > 1)333 UpdateResidualSpace(item, positionFound);334 310 sequence.Remove(itemID); 335 311 } … … 390 366 } 391 367 392 393 368 public bool IsSupportedByAtLeastOnePoint(PackingItem item, PackingPosition position) { 394 369 if (position.Y == 0) … … 443 418 public void UpdateResidualSpace(PackingItem item, PackingPosition pos) { 444 419 foreach (var ep in ExtremePoints) { 445 if (ep.Z >= pos.Z && ep.Z <= pos.Z + item.Depth) { 446 if (ep.X <= pos.X && ep.Y > pos.Y && ep.Y < pos.Y + item.Height) { 420 var rs = ResidualSpace[ep]; 421 var depth = pos.Rotated ? item.Width : item.Depth; 422 var width = pos.Rotated ? item.Depth : item.Width; 423 if (ep.Z >= pos.Z && ep.Z < pos.Z + depth) { 424 if (ep.X <= pos.X && ep.Y >= pos.Y && ep.Y < pos.Y + item.Height) { 447 425 var diff = pos.X  ep.X; 448 var newRSX = ResidualSpace[ep].Item1 < diff ? ResidualSpace[ep].Item1 : diff;449 ResidualSpace[ep] = Tuple.Create(newRSX, ResidualSpace[ep].Item2, ResidualSpace[ep].Item3);426 var newRSX = Math.Min(rs.Item1, diff); 427 ResidualSpace[ep] = Tuple.Create(newRSX, rs.Item2, rs.Item3); 450 428 } 451 if (ep.Y <= pos.Y && ep.X > pos.X && ep.X < pos.X + item.Width) {429 if (ep.Y <= pos.Y && ep.X >= pos.X && ep.X < pos.X + width) { 452 430 var diff = pos.Y  ep.Y; 453 var newRSY = ResidualSpace[ep].Item2 < diff ? ResidualSpace[ep].Item2 : diff;454 ResidualSpace[ep] = Tuple.Create( ResidualSpace[ep].Item1, newRSY, ResidualSpace[ep].Item3);431 var newRSY = Math.Min(rs.Item2, diff); 432 ResidualSpace[ep] = Tuple.Create(rs.Item1, newRSY, rs.Item3); 455 433 } 456 434 } 457 435 if (ep.Z <= pos.Z && 458 ep.Y > pos.Y && ep.Y < pos.Y + item.Height &&459 ep.X > pos.X && ep.X < pos.X + item.Width) {436 ep.Y >= pos.Y && ep.Y < pos.Y + item.Height && 437 ep.X >= pos.X && ep.X < pos.X + width) { 460 438 var diff = pos.Z  ep.Z; 461 var newRSZ = ResidualSpace[ep].Item3 < diff ? ResidualSpace[ep].Item3 : diff;462 ResidualSpace[ep] = Tuple.Create( ResidualSpace[ep].Item1, ResidualSpace[ep].Item2, newRSZ);439 var newRSZ = Math.Min(rs.Item3, diff); 440 ResidualSpace[ep] = Tuple.Create(rs.Item1, rs.Item2, newRSZ); 463 441 } 464 442 } … … 466 444 } 467 445 446 #region Helper classes for vector math 468 447 private class Vector3D { 469 448 public int X; … … 531 510 ); 532 511 } 512 513 public bool IsInside(PackingPosition pos, Tuple<int, int, int> rs) { 514 return X >= pos.X && X < pos.X + rs.Item1 515 && Y >= pos.Y && Y < pos.Y + rs.Item2 516 && Z >= pos.Z && Z < pos.Z + rs.Item3; 517 } 518 533 519 public static int operator *(Vector3D a, Vector3D b) { 534 520 return a.X * b.X + a.Y * b.Y + a.Z * b.Z; … … 614 600 615 601 public Plane3D(PackingPosition pos, PackingItem item, Side side) { 616 // the directing vectors are chosen such that Normal always points outside the packing item602 // the directing vectors are chosen such that normal always points outside the packing item 617 603 switch (side) { 618 604 case Side.Top: // ZX plane … … 651 637 } 652 638 653 public bool IsElementOf(Vector3D vector) {654 return Normal.X * vector.X + Normal.Y * vector.Y + Normal.Z * vector.Z == rhs;639 public bool IsElementOf(Vector3D point) { 640 return Normal.X * point.X + Normal.Y * point.Y + Normal.Z * point.Z == rhs; 655 641 } 656 642 … … 677 663 678 664 public bool IsWithinDirectionalVectors(Vector3D point) { 679 return point.X >= Point.X && (point.X <= Point.X + Direction1.X  point.X <= Point.X + Direction2.X) 680 && point.Y >= Point.Y && (point.Y <= Point.Y + Direction1.Y  point.Y <= Point.Y + Direction2.Y) 681 && point.Z >= Point.Z && (point.Z <= Point.Z + Direction1.Z  point.Z <= Point.Z + Direction2.Z); 682 } 683 } 665 return point.X >= Point.X && (Direction1.X + Direction2.X == 0  (point.X < Point.X + Direction1.X  point.X < Point.X + Direction2.X)) 666 && point.Y >= Point.Y && (Direction1.Y + Direction2.Y == 0  (point.Y < Point.Y + Direction1.Y  point.Y < Point.Y + Direction2.Y)) 667 && point.Z >= Point.Z && (Direction1.Z + Direction2.Z == 0  (point.Z < Point.Z + Direction1.Z  point.Z < Point.Z + Direction2.Z)); 668 } 669 } 670 #endregion 684 671 } 685 672 }
Note: See TracChangeset
for help on using the changeset viewer.