Changeset 15554 for branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/PointProjectionBasedEPCreator.cs
- Timestamp:
- 12/20/17 16:15:38 (6 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/PointProjectionBasedEPCreator.cs
r15520 r15554 31 31 32 32 protected override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) { 33 foreach (var ep in binPacking.ExtremePoints.ToList()) { 34 var rs = binPacking.ResidualSpaces[ep]; 35 var depth = position.Rotated ? item.Width : item.Depth; 36 var width = position.Rotated ? item.Depth : item.Width; 37 var changed = false; 38 if (ep.Z >= position.Z && ep.Z < position.Z + depth) { 39 if (ep.X <= position.X && ep.Y >= position.Y && ep.Y < position.Y + item.Height) { 40 var diff = position.X - ep.X; 41 var newRSX = Math.Min(rs.Width, diff); 42 rs = ResidualSpace.Create(newRSX, rs.Height, rs.Depth); 33 foreach (var extremePoint in binPacking.ExtremePoints.ToList()) { 34 var ep = extremePoint.Key; 35 var residualSpaces = extremePoint.Value as IList<ResidualSpace>; 36 for (int i = 0; i < residualSpaces.Count(); i++) { 37 var rs = residualSpaces[i]; 38 var depth = position.Rotated ? item.Width : item.Depth; 39 var width = position.Rotated ? item.Depth : item.Width; 40 var changed = false; 41 if (ep.Z >= position.Z && ep.Z < position.Z + depth) { 42 if (ep.X <= position.X && ep.Y >= position.Y && ep.Y < position.Y + item.Height) { 43 var diff = position.X - ep.X; 44 var newRSX = Math.Min(rs.Width, diff); 45 rs = ResidualSpace.Create(newRSX, rs.Height, rs.Depth); 46 changed = true; 47 } 48 if (ep.Y <= position.Y && ep.X >= position.X && ep.X < position.X + width) { 49 var diff = position.Y - ep.Y; 50 var newRSY = Math.Min(rs.Height, diff); 51 rs = ResidualSpace.Create(rs.Width, newRSY, rs.Depth); 52 changed = true; 53 } 54 } 55 56 if (ep.Z <= position.Z && 57 ep.Y >= position.Y && ep.Y < position.Y + item.Height && 58 ep.X >= position.X && ep.X < position.X + width) { 59 var diff = position.Z - ep.Z; 60 var newRSZ = Math.Min(rs.Depth, diff); 61 rs = ResidualSpace.Create(rs.Width, rs.Height, newRSZ); 43 62 changed = true; 44 63 } 45 if (ep.Y <= position.Y && ep.X >= position.X && ep.X < position.X + width) { 46 var diff = position.Y - ep.Y; 47 var newRSY = Math.Min(rs.Height, diff); 48 rs = ResidualSpace.Create(rs.Width, newRSY, rs.Depth); 49 changed = true; 64 65 if (changed) { 66 if (!rs.IsZero() && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) { 67 residualSpaces[i] = rs; 68 } else { 69 binPacking.ExtremePoints.Remove(ep); 70 break; 71 } 50 72 } 51 } 52 53 if (ep.Z <= position.Z && 54 ep.Y >= position.Y && ep.Y < position.Y + item.Height && 55 ep.X >= position.X && ep.X < position.X + width) { 56 var diff = position.Z - ep.Z; 57 var newRSZ = Math.Min(rs.Depth, diff); 58 rs = ResidualSpace.Create(rs.Width, rs.Height, newRSZ); 59 changed = true; 60 } 61 62 if (changed) { 63 if (!rs.IsZero() && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) { 64 binPacking.ResidualSpaces[ep] = rs; 65 } else { 66 binPacking.ExtremePoints.Remove(ep); 67 binPacking.ResidualSpaces.Remove(ep); 68 } 69 } 73 } 70 74 } 71 75 return; … … 81 85 /// <returns></returns> 82 86 protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) { 83 if (binPacking.ExtremePoints.Add(position)) { 84 var rs = CalculateResidualSpace(binPacking, new Vector3D(position)); 85 binPacking.ResidualSpaces.Add(position, rs); 86 // Check if the existing extreme points are shadowed by the new point 87 // This is, their residual space fit entirely into the residual space of the new point 88 foreach (var ep in binPacking.ExtremePoints.Where(x => x != position && new Vector3D(x).IsInside(position, rs)).ToList()) { 89 if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), binPacking.ResidualSpaces[ep], position, rs)) { 87 if (binPacking.ExtremePoints.ContainsKey(position)) { 88 return false; 89 } 90 91 var residualSpaces = CalculateResidualSpace(binPacking, new Vector3D(position)); 92 binPacking.ExtremePoints.Add(position, residualSpaces); 93 // Check if the existing extreme points are shadowed by the new point 94 // This is, their residual space fit entirely into the residual space of the new point 95 foreach (var ep in binPacking.ExtremePoints.Where(x => x.Key != position && new Vector3D(x.Key).IsInside(position, residualSpaces)).ToList()) { 96 foreach (var residualSpace in ep.Value) { 97 if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep.Key), residualSpace, position, residualSpaces)) { 90 98 binPacking.ExtremePoints.Remove(ep); 91 b inPacking.ResidualSpaces.Remove(ep);99 break; 92 100 } 101 } 102 } 103 return true; 104 } 105 106 /// <summary> 107 /// Calculates the residual space for a given bin packing and position. 108 /// It returns the residual space as a tuple which contains the dimensions 109 /// </summary> 110 /// <param name="binPacking"></param> 111 /// <param name="pos"></param> 112 /// <returns>A Tuple(width, Height, Depth)</width></returns> 113 protected override IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) { 114 var residualSpaces = new List<ResidualSpace>(); 115 var residualSpace = new ResidualSpace(CalculateResidualSpaceOld(binPacking, pos)); 116 if (!residualSpace.IsZero()) { 117 residualSpaces.Add(residualSpace); 118 } 119 return residualSpaces; 120 } 121 122 protected Tuple<int, int, int> CalculateResidualSpaceOld(BinPacking3D binPacking, Vector3D pos) { 123 124 if (pos == null) { 125 return Tuple.Create(0, 0, 0); 126 } 127 var itemPos = binPacking.Items.Select(x => new { 128 Item = x.Value, 129 Position = binPacking.Positions[x.Key] 130 }); 131 Vector3D limit = new Vector3D() { 132 X = binPacking.BinShape.Width, 133 Y = binPacking.BinShape.Height, 134 Z = binPacking.BinShape.Depth 135 }; 136 137 if (pos.X < limit.X && pos.Y < limit.Y && pos.Z < limit.Z) { 138 var rightLimit = ProjectRight(binPacking, pos); 139 var upLimit = ProjectUp(binPacking, pos); 140 var forwardLimit = ProjectForward(binPacking, pos); 141 if (rightLimit.X > 0) { 142 limit.X = rightLimit.X; 93 143 } 94 return true; 144 if (upLimit.Y > 0) { 145 limit.Y = upLimit.Y; 146 } 147 if (forwardLimit.Z > 0) { 148 limit.Z = forwardLimit.Z; 149 } 95 150 } 96 return false; 151 152 if (limit.X - pos.X <= 0 || limit.Y - pos.Y <= 0 || limit.Z - pos.Z <= 0) { 153 return Tuple.Create(0, 0, 0); 154 } 155 return Tuple.Create(limit.X - pos.X, limit.Y - pos.Y, limit.Z - pos.Z); 97 156 } 98 157 }
Note: See TracChangeset
for help on using the changeset viewer.