Changeset 15305
 Timestamp:
 08/04/17 12:37:19 (20 months ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

branches/2817BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs
r15304 r15305 74 74 75 75 var itemPlacement = Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] }).ToList(); 76 // Find ExtremePoints beginning from sourcepointX76 // Find ExtremePoints beginning from sourcepointX 77 77 var sourcePoint = new Vector3D() { X = position.X + newWidth, Y = position.Y, Z = position.Z }; 78 78 if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) { 79 //Traversing down the yaxis 80 var below = itemPlacement.Where(x => IsBelow(x.Position, x.Item, sourcePoint)) 81 .MaxItems(x => x.Position.Y + x.Item.Height).FirstOrDefault(); 82 var projY = false; 83 if (below != null) { 84 var belowPoint = new PackingPosition(position.AssignedBin, sourcePoint.X, below.Position.Y + below.Item.Height, sourcePoint.Z); 85 projY = AddExtremePoint(belowPoint); 86 } 87 //Traversing down the zaxis 88 var back = itemPlacement.Where(x => IsBack(x.Position, x.Item, sourcePoint)) 89 .MaxItems(x => x.Position.Z + x.Item.Depth).FirstOrDefault(); 90 var projZ = false; 91 if (back != null) { 92 var backPoint = new PackingPosition(position.AssignedBin, sourcePoint.X, sourcePoint.Y, back.Position.Z + back.Item.Depth); 93 projZ = AddExtremePoint(backPoint); 94 } 95 96 // only add the source point if both projections added new points 97 // or if neither of the projections added a point 98 // if a projection tried to add a point that already exists, then this 99 // extreme point would be covered by the existing extreme point 100 if ((below == null && back == null)  (below == null  projY) && (back == null  projZ)) 101 AddExtremePoint(new PackingPosition(position.AssignedBin, sourcePoint.X, sourcePoint.Y, sourcePoint.Z)); 79 // 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(); 86 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)) { 91 // add only if the projected point's residual space is not a subspace 92 // of another extreme point's residual space 93 var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z); 94 AddExtremePoint(belowPoint); 95 } 96 line = new Line3D(sourcePoint, new Vector3D(0, 0, 1)); 97 // 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)) { 108 // add only if the projected point's residual space is not a subspace 109 // of another extreme point's residual space 110 var backPoint = new PackingPosition(position.AssignedBin, back.X, back.Y, back.Z); 111 AddExtremePoint(backPoint); 112 } 102 113 } 103 114 … … 105 116 sourcePoint = new Vector3D(position.X, position.Y + newItem.Height, position.Z); 106 117 if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) { 107 //Traversing down the xaxis 108 var left = itemPlacement.Where(x => IsLeft(x.Position, x.Item, sourcePoint)) 109 .MaxItems(x => x.Position.X + x.Item.Width).FirstOrDefault(); 110 var projX = false; 111 if (left != null) { 112 var leftPoint = new PackingPosition(position.AssignedBin, left.Position.X + left.Item.Width, sourcePoint.Y, sourcePoint.Z); 113 projX = AddExtremePoint(leftPoint); 114 } 115 116 //Traversing down the zaxis 117 var back = itemPlacement.Where(x => IsBack(x.Position, x.Item, sourcePoint)) 118 .MaxItems(x => x.Position.Z + x.Item.Depth).FirstOrDefault(); 119 var projZ = false; 120 if (back != null) { 121 var backPoint = new PackingPosition(position.AssignedBin, sourcePoint.X, sourcePoint.Y, back.Position.Z + back.Item.Depth); 122 projZ = AddExtremePoint(backPoint); 123 } 124 125 // only add the source point if both projections added new points 126 // or if neither of the projections added a point 127 // if a projection tried to add a point that already exists, then this 128 // extreme point would be covered by the existing extreme point 129 if ((left == null  projX) && (back == null  projZ)) 130 AddExtremePoint(new PackingPosition(position.AssignedBin, sourcePoint.X, sourcePoint.Y, sourcePoint.Z)); 118 // 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(); 125 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)) { 130 // add only if the projected point's residual space is not a subspace 131 // of another extreme point's residual space 132 var leftPoint = new PackingPosition(position.AssignedBin, left.X, left.Y, left.Z); 133 AddExtremePoint(leftPoint); 134 } 135 line = new Line3D(sourcePoint, new Vector3D(0, 0, 1)); 136 // 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)) { 147 // add only if the projected point's residual space is not a subspace 148 // of another extreme point's residual space 149 var backPoint = new PackingPosition(position.AssignedBin, back.X, back.Y, back.Z); 150 AddExtremePoint(backPoint); 151 } 131 152 } 132 153 … … 134 155 sourcePoint = new Vector3D(position.X, position.Y, position.Z + newDepth); 135 156 if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) { 136 //Traversing down the xaxis 137 var left = itemPlacement.Where(x => IsLeft(x.Position, x.Item, sourcePoint)) 138 .MaxItems(x => x.Position.X + x.Item.Width).FirstOrDefault(); 139 var projX = false; 140 if (left != null) { 141 var leftPoint = new PackingPosition(position.AssignedBin, left.Position.X + left.Item.Width, sourcePoint.Y, sourcePoint.Z); 142 projX = AddExtremePoint(leftPoint); 143 } 144 145 //Traversing down the yaxis 146 var below = itemPlacement.Where(x => IsBelow(x.Position, x.Item, sourcePoint)) 147 .MaxItems(x => x.Position.Y + x.Item.Height).FirstOrDefault(); 148 var projY = false; 149 if (below != null) { 150 var belowPoint = new PackingPosition(position.AssignedBin, sourcePoint.X, below.Position.Y + below.Item.Height, sourcePoint.Z); 151 projY = AddExtremePoint(belowPoint); 152 } 153 154 // only add the source point if both projections added new points 155 // or if neither of the projections added a point 156 // if a projection tried to add a point that already exists, then this 157 // extreme point would be covered by the existing extreme point 158 if ((left == null  projX) && (below == null  projY)) 159 AddExtremePoint(new PackingPosition(position.AssignedBin, sourcePoint.X, sourcePoint.Y, sourcePoint.Z)); 157 // 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(); 164 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)) { 169 // add only if the projected point's residual space is not a subspace 170 // of another extreme point's residual space 171 var leftPoint = new PackingPosition(position.AssignedBin, left.X, left.Y, left.Z); 172 AddExtremePoint(leftPoint); 173 } 174 // 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(); 181 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)) { 186 // add only if the projected point's residual space is not a subspace 187 // of another extreme point's residual space 188 var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z); 189 AddExtremePoint(belowPoint); 190 } 160 191 } 161 192 } … … 181 212 private bool AddExtremePoint(PackingPosition current) { 182 213 if (ExtremePoints.Add(current)) { 183 var tuple = Tuple.Create(BinShape.Width  current.X, BinShape.Height  current.Y, BinShape.Depth  current.Z); 184 ResidualSpace.Add(current, tuple); 214 ResidualSpace.Add(current, CalculateResidualSpace(current)); 185 215 return true; 186 216 } 187 217 return false; 218 } 219 220 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; 188 250 } 189 251 … … 462 524 } 463 525 464 public static bool Intersects(Vector3D p1, Vector3D dir, Vector3D p2, Vector3D dir2, Vector3D dir3) {465 var normal = dir2.Cross(dir3);466 var denom = normal * dir;467 if (denom == 0) {468 // dir is perpendicular to the normal vector of the plane469 // this means they intersect if p1 is element of the plane470 return p1.X * normal.X + p1.Y * normal.Y + p1.Z * normal.Z == p2.X * normal.X + p2.Y * normal.Y + p2.Z * normal.Z471 && IsInPlane(p1, p2, dir2, dir3);472 }473 var intersect = p1 + ((normal * (p2  p1)) / denom) * dir;474 return IsInPlane(intersect, p2, dir2, dir3);475 }476 477 private static bool IsInPlane(Vector3D p1, Vector3D p2, Vector3D dir2, Vector3D dir3) {478 return p1.X >= p2.X && (p1.X <= p2.X + dir2.X  p1.X <= p2.X + dir3.X)479 && p1.Y >= p2.Y && (p1.Y <= p2.Y + dir2.Y  p1.Y <= p2.Y + dir3.Y)480 && p1.Z >= p2.Z && (p1.Z <= p2.Z + dir2.Z  p1.Z <= p2.Z + dir3.Z);481 }482 483 526 public Vector3D Cross(Vector3D b) { 484 527 return new Vector3D( … … 504 547 } 505 548 } 549 550 // A line is given as a point and a directing vector 551 private class Line3D { 552 public Vector3D Point; 553 public Vector3D Direction; 554 555 public Line3D(Vector3D point, Vector3D direction) { 556 Point = point; 557 Direction = direction; 558 } 559 560 public bool Intersects(Plane3D plane) { 561 return plane.Intersects(this); 562 } 563 564 public Vector3D Intersect(Plane3D plane) { 565 return plane.Intersect(this); 566 } 567 } 568 569 private enum Side { Top, Left, Bottom, Right, Front, Back } 570 // A plane is given as a point and two directing vectors 571 private class Plane3D { 572 public Vector3D Point { get; private set; } 573 public Vector3D Direction1 { get; private set; } 574 public Vector3D Direction2 { get; private set; } 575 public Vector3D Normal { get; private set; } 576 private int rhs; 577 578 public Plane3D(PackingShape bin, Side side) { 579 switch (side) { 580 case Side.Top: // ZX plane 581 Point = new Vector3D(0, bin.Height, 0); 582 Direction1 = new Vector3D(0, 0, bin.Depth); 583 Direction2 = new Vector3D(bin.Width, 0, 0); 584 break; 585 case Side.Left: // ZY plane 586 Point = new Vector3D(0, 0, 0); 587 Direction1 = new Vector3D(0, 0, bin.Depth); 588 Direction2 = new Vector3D(0, bin.Height, 0); 589 break; 590 case Side.Bottom: // XZ plane 591 Point = new Vector3D(0, 0, 0); 592 Direction1 = new Vector3D(bin.Width, 0, 0); 593 Direction2 = new Vector3D(0, 0, bin.Depth); 594 break; 595 case Side.Right: // YZ plane 596 Point = new Vector3D(bin.Width, 0, 0); 597 Direction1 = new Vector3D(0, bin.Height, 0); 598 Direction2 = new Vector3D(0, 0, bin.Depth); 599 break; 600 case Side.Front: // XY plane 601 Point = new Vector3D(0, 0, bin.Depth); 602 Direction1 = new Vector3D(bin.Width, 0, 0); 603 Direction2 = new Vector3D(0, bin.Height, 0); 604 break; 605 case Side.Back: // YX plane 606 Point = new Vector3D(0, 0, 0); 607 Direction1 = new Vector3D(0, bin.Height, 0); 608 Direction2 = new Vector3D(bin.Width, 0, 0); 609 break; 610 } 611 Normal = Direction1.Cross(Direction2); 612 rhs = 0; 613 } 614 615 public Plane3D(PackingPosition pos, PackingItem item, Side side) { 616 // the directing vectors are chosen such that Normal always points outside the packing item 617 switch (side) { 618 case Side.Top: // ZX plane 619 Point = new Vector3D(pos.X, pos.Y + item.Height, pos.Z); 620 Direction1 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth); 621 Direction2 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0); 622 break; 623 case Side.Left: // ZY plane 624 Point = new Vector3D(pos.X, pos.Y, pos.Z); 625 Direction1 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth); 626 Direction2 = new Vector3D(0, item.Height, 0); 627 break; 628 case Side.Bottom: // XZ plane 629 Point = new Vector3D(pos.X, pos.Y, pos.Z); 630 Direction1 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0); 631 Direction2 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth); 632 break; 633 case Side.Right: // YZ plane 634 Point = new Vector3D(pos.X + (pos.Rotated ? item.Depth : item.Width), pos.Y, pos.Z); 635 Direction1 = new Vector3D(0, item.Height, 0); 636 Direction2 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth); 637 break; 638 case Side.Front: // XY plane 639 Point = new Vector3D(pos.X, pos.Y, pos.Z + (pos.Rotated ? item.Width : item.Depth)); 640 Direction1 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0); 641 Direction2 = new Vector3D(0, item.Height, 0); 642 break; 643 case Side.Back: // YX plane 644 Point = new Vector3D(pos.X, pos.Y, pos.Z); 645 Direction1 = new Vector3D(0, item.Height, 0); 646 Direction2 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0); 647 break; 648 } 649 Normal = Direction1.Cross(Direction2); 650 rhs = Normal.X * Point.X + Normal.Y * Point.Y + Normal.Z * Point.Z; 651 } 652 653 public bool IsElementOf(Vector3D vector) { 654 return Normal.X * vector.X + Normal.Y * vector.Y + Normal.Z * vector.Z == rhs; 655 } 656 657 public bool Intersects(Line3D line) { 658 return Intersect(line) != null; 659 } 660 661 public Vector3D Intersect(Line3D line) { 662 var denom = Normal * line.Direction; 663 if (denom == 0) { 664 // dir is perpendicular to the normal vector of the plane 665 // this means they intersect if p1 is element of the plane 666 // also the plane does not stretch infinitely, but is bound 667 // to the parallelogram spanned by the point and the two 668 // directing vectors 669 if (IsElementOf(line.Point) && IsWithinDirectionalVectors(line.Point)) 670 return line.Point; 671 else return null; 672 } 673 var intersect = line.Point + ((Normal * (Point  line.Point)) / denom) * line.Direction; 674 if (IsWithinDirectionalVectors(intersect)) return intersect; 675 return null; 676 } 677 678 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 } 506 684 } 507 685 }
Note: See TracChangeset
for help on using the changeset viewer.