Changeset 15554 for branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/ExtremePointCreator.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/ExtremePointCreator.cs
r15520 r15554 46 46 // Projecting onto the XZ-plane 47 47 var below = ProjectDown(binPacking, sourcePoint); 48 var residualSpace = CalculateResidualSpace(binPacking, below);49 if ( !residualSpace.IsZero()50 && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpace )) {48 var residualSpaces = CalculateResidualSpace(binPacking, below); 49 if (residualSpaces.Count() > 0 50 && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpaces)) { 51 51 // add only if the projected point's residual space is not a sub-space 52 52 // of another extreme point's residual space … … 56 56 // Projecting onto the XY-plane 57 57 var back = ProjectBackward(binPacking, sourcePoint); 58 residualSpace = CalculateResidualSpace(binPacking, back);59 if ( !residualSpace.IsZero()60 && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpace )) {58 residualSpaces = CalculateResidualSpace(binPacking, back); 59 if (residualSpaces.Count() > 0 60 && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpaces)) { 61 61 // add only if the projected point's residual space is not a sub-space 62 62 // of another extreme point's residual space … … 71 71 // Projecting onto the YZ-plane 72 72 var left = ProjectLeft(binPacking, sourcePoint); 73 var residualSpace = CalculateResidualSpace(binPacking, left);74 if ( !residualSpace.IsZero()75 && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpace )) {73 var residualSpaces = CalculateResidualSpace(binPacking, left); 74 if (residualSpaces.Count() > 0 75 && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpaces)) { 76 76 // add only if the projected point's residual space is not a sub-space 77 77 // of another extreme point's residual space … … 81 81 // Projecting onto the XY-plane 82 82 var back = ProjectBackward(binPacking, sourcePoint); 83 residualSpace = CalculateResidualSpace(binPacking, back);84 if ( !residualSpace.IsZero()85 && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpace )) {83 residualSpaces = CalculateResidualSpace(binPacking, back); 84 if (residualSpaces.Count() > 0 85 && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpaces)) { 86 86 // add only if the projected point's residual space is not a sub-space 87 87 // of another extreme point's residual space … … 96 96 // Projecting onto the XZ-plane 97 97 var below = ProjectDown(binPacking, sourcePoint); 98 var residualSpace = CalculateResidualSpace(binPacking, below);99 if ( !residualSpace.IsZero()100 && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpace )) {98 var residualSpaces = CalculateResidualSpace(binPacking, below); 99 if (residualSpaces.Count() > 0 100 && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpaces)) { 101 101 // add only if the projected point's residual space is not a sub-space 102 102 // of another extreme point's residual space … … 106 106 // Projecting onto the YZ-plane 107 107 var left = ProjectLeft(binPacking, sourcePoint); 108 residualSpace = CalculateResidualSpace(binPacking, left);109 if ( !residualSpace.IsZero()110 && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpace )) {108 residualSpaces = CalculateResidualSpace(binPacking, left); 109 if (residualSpaces.Count() > 0 110 && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpaces)) { 111 111 // add only if the projected point's residual space is not a sub-space 112 112 // of another extreme point's residual space … … 191 191 /// <param name="residualSpace"></param> 192 192 /// <returns></returns> 193 protected virtual bool IsWithinResidualSpaceOfAnotherExtremePoint(BinPacking3D binPacking, Vector3D pos, ResidualSpace residualSpace) { 194 var eps = binPacking.ExtremePoints.Where(x => !pos.Equals(x) && pos.IsInside(x, binPacking.ResidualSpaces[x])); 195 return eps.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, residualSpace, x, binPacking.ResidualSpaces[x])); 193 protected bool IsWithinResidualSpaceOfAnotherExtremePoint(BinPacking3D binPacking, Vector3D pos, ResidualSpace residualSpace) { 194 var eps = binPacking.ExtremePoints.Where(x => !pos.Equals(x.Key) && pos.IsInside(x.Key, x.Value)); 195 return eps.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, residualSpace, x.Key, x.Value)); 196 } 197 198 /// <summary> 199 /// 200 /// </summary> 201 /// <param name="binPacking"></param> 202 /// <param name="pos"></param> 203 /// <param name="residualSpaces"></param> 204 /// <returns></returns> 205 protected bool IsWithinResidualSpaceOfAnotherExtremePoint(BinPacking3D binPacking, Vector3D pos, IEnumerable<ResidualSpace> residualSpaces) { 206 foreach (var residualSpace in residualSpaces) { 207 if (IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, pos, residualSpace)) { 208 return true; 209 } 210 } 211 return false; 212 } 213 214 215 /// <summary> 216 /// Returns true, if the given poisition and the related residual space is within the residual space of the given extreme point 217 /// </summary> 218 /// <param name="pos"></param> 219 /// <param name="rsPos"></param> 220 /// <param name="ep"></param> 221 /// <param name="rsEp"></param> 222 /// <returns></returns> 223 protected bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, ResidualSpace rsPos, PackingPosition ep, IEnumerable<ResidualSpace> rsEp) { 224 return rsEp.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, rsPos, ep, x)); 196 225 } 197 226 … … 211 240 212 241 /// <summary> 213 /// Calculates the residual space for a given bin packing and position. 214 /// It returns the residual space as a tuple which contains the dimensions 215 /// </summary> 216 /// <param name="binPacking"></param> 217 /// <param name="pos"></param> 218 /// <returns>A Tuple(width, Height, Depth)</width></returns> 219 protected virtual ResidualSpace CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) { 220 //return ResidualSpaceCalculator.Create().CalculateResidualSpace(binPacking, pos).First(); 221 return new ResidualSpace(CalculateResidualSpaceOld(binPacking, pos)); 222 } 223 224 protected virtual Tuple<int, int, int> CalculateResidualSpaceOld(BinPacking3D binPacking, Vector3D pos) { 225 226 if (pos == null) { 227 return Tuple.Create(0, 0, 0); 228 } 229 var itemPos = binPacking.Items.Select(x => new { 230 Item = x.Value, 231 Position = binPacking.Positions[x.Key] 232 }); 233 Vector3D limit = new Vector3D() { 234 X = binPacking.BinShape.Width, 235 Y = binPacking.BinShape.Height, 236 Z = binPacking.BinShape.Depth 237 }; 238 239 if (pos.X < limit.X && pos.Y < limit.Y && pos.Z < limit.Z) { 240 var rightLimit = ProjectRight(binPacking, pos); 241 var upLimit = ProjectUp(binPacking, pos); 242 var forwardLimit = ProjectForward(binPacking, pos); 243 if (rightLimit.X > 0) { 244 limit.X = rightLimit.X; 245 } 246 if (upLimit.Y > 0) { 247 limit.Y = upLimit.Y; 248 } 249 if (forwardLimit.Z > 0) { 250 limit.Z = forwardLimit.Z; 251 } 252 } 253 254 if (limit.X - pos.X <= 0 || limit.Y - pos.Y <= 0 || limit.Z - pos.Z <= 0) { 255 return Tuple.Create(0, 0, 0); 256 } 257 return Tuple.Create(limit.X - pos.X, limit.Y - pos.Y, limit.Z - pos.Z); 258 } 259 242 /// Calculates the residual spaces for a given bin packing and position. 243 /// It returns a collection of residual spaces 244 /// </summary> 245 /// <param name="binPacking"></param> 246 /// <param name="pos"></param> 247 /// <returns></returns> 248 protected abstract IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos); 249 260 250 #endregion 261 251
Note: See TracChangeset
for help on using the changeset viewer.