Changeset 15705 for branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/PointProjectionBasedEPCreator.cs
- Timestamp:
- 02/01/18 12:21:34 (6 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/PointProjectionBasedEPCreator.cs
r15617 r15705 22 22 using HeuristicLab.Common; 23 23 using HeuristicLab.Problems.BinPacking3D.Geometry; 24 using HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation; 24 25 using System; 25 26 using System.Collections.Generic; … … 36 37 /// </summary> 37 38 public class PointProjectionBasedEPCreator : ExtremePointCreator { 39 /// <summary> 40 /// This lock object is needed because of creating the extreme points in an parallel for loop. 41 /// </summary> 42 object _lockAddExtremePoint = new object(); 43 38 44 protected override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) { 39 GenerateNewExtremePointsForItem(binPacking, item, position); 40 41 // if an item is fit in below, before, or left of another its extreme points have to be regenerated 42 foreach (var above in GetItemsAbove(binPacking, position)) { 43 GenerateNewExtremePointsForItem(binPacking, above.Item2, above.Item1); 44 } 45 foreach (var front in GetItemsInfront(binPacking, position)) { 46 GenerateNewExtremePointsForItem(binPacking, front.Item2, front.Item1); 47 } 48 foreach (var right in GetItemsOnRight(binPacking, position)) { 49 GenerateNewExtremePointsForItem(binPacking, right.Item2, right.Item1); 50 } 51 } 52 45 binPacking.ExtremePoints.Clear(); 46 47 // generate all new extreme points parallel. This speeds up the creator. 48 Parallel.ForEach(binPacking.Items, i => { 49 PackingItem it = i.Value; 50 PackingPosition p = binPacking.Positions[i.Key]; 51 GenerateNewExtremePointsForItem(binPacking, it, p); 52 }); 53 54 // remove not needed extreme points. 55 foreach (var extremePoint in binPacking.ExtremePoints.ToList()) { 56 // check if a residual space can be removed 57 foreach (var rs in extremePoint.Value.ToList()) { 58 if (ResidualSpaceCanBeRemoved(binPacking, extremePoint.Key, rs)) { 59 ((IList<ResidualSpace>)extremePoint.Value).Remove(rs); 60 } 61 } 62 // if the current extreme point has no more residual spaces, it can be removed. 63 if (((IList<ResidualSpace>)extremePoint.Value).Count <= 0) { 64 binPacking.ExtremePoints.Remove(extremePoint); 65 } 66 } 67 68 } 69 70 /// <summary> 71 /// Returns true if a given residual space can be removed. 72 /// The given residual space can be removed if it is within another residual space and 73 /// - neither the position of the other residual space and the current extreme point have an item below or 74 /// - the current extreme point has an item below. 75 /// </summary> 76 /// <param name="binPacking"></param> 77 /// <param name="position"></param> 78 /// <param name="rs"></param> 79 /// <returns></returns> 80 private bool ResidualSpaceCanBeRemoved(BinPacking3D binPacking, PackingPosition position, ResidualSpace rs) { 81 foreach (var extremePoint in binPacking.ExtremePoints) { 82 if (position.Equals(extremePoint.Key)) { 83 continue; 84 } 85 if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(position), rs, extremePoint.Key, extremePoint.Value)) { 86 var itemBelowEp = LiesOnAnyItem(binPacking, extremePoint.Key); 87 var itemBelowPos = LiesOnAnyItem(binPacking, position); 88 89 if (itemBelowEp || !itemBelowEp && !itemBelowPos) { 90 return true; 91 } 92 } 93 } 94 return false; 95 } 96 97 /// <summary> 98 /// Returns true if the given position lies on an item or an the ground. 99 /// </summary> 100 /// <param name="binPacking"></param> 101 /// <param name="position"></param> 102 /// <returns></returns> 103 private bool LiesOnAnyItem(BinPacking3D binPacking, PackingPosition position) { 104 if (position.Y == 0) { 105 return true; 106 } 107 108 var items = binPacking.Items.Where(x => { 109 var itemPosition = binPacking.Positions[x.Key]; 110 var item = x.Value; 111 int width = item.Width; 112 int depth = item.Depth; 113 114 return itemPosition.Y + item.Height == position.Y && 115 itemPosition.X <= position.X && position.X < itemPosition.X + width && 116 itemPosition.Z <= position.Z && position.Z < itemPosition.Z + depth; 117 }); 118 119 return items.Count() > 0; 120 } 121 122 123 /// <summary> 124 /// Adds a new extreme point an the related residual spaces to a given bin packing. 125 /// - The given position has to be valid. 126 /// - The extreme point does not exist in the bin packing. 127 /// - There must be at minimum one valid residual space. A residual space is invalid if the space is zero. 128 /// </summary> 129 /// <param name="binPacking"></param> 130 /// <param name="position"></param> 131 /// <returns>True = the given point and its related residual spaces were successfully added to the bin packing</returns> 132 protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) { 133 if (position == null) { 134 return false; 135 } 136 137 if (PointIsInAnyItem(binPacking, new Vector3D(position))) { 138 return false; 139 } 140 141 // this is necessary if the extreme points are being created in a parallel loop. 142 lock (_lockAddExtremePoint) { 143 if (binPacking.ExtremePoints.ContainsKey(position)) { 144 return false; 145 } 146 147 var rs = CalculateResidualSpace(binPacking, new Vector3D(position)); 148 149 if (rs.Count() <= 0) { 150 return false; 151 } 152 153 binPacking.ExtremePoints.Add(position, rs); 154 return true; 155 } 156 } 157 158 /// <summary> 159 /// Getnerates the extreme points for a given item. 160 /// It creates extreme points by using a point projection based method and 161 /// creates points by using an edge projection based method. 162 /// </summary> 163 /// <param name="binPacking"></param> 164 /// <param name="newItem"></param> 165 /// <param name="position"></param> 166 protected override void GenerateNewExtremePointsForItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) { 167 PointProjectionForNewItem(binPacking, newItem, position); 168 } 169 170 #region Extreme point creation by using a point projection based method 171 172 /// <summary> 173 /// This method creates extreme points by using a point projection based method. 174 /// For each item there will be created three points and each of the points will be projected twice. 175 /// The direction of the projection depends on position of the point. 176 /// </summary> 177 /// <param name="binPacking"></param> 178 /// <param name="newItem"></param> 179 /// <param name="position"></param> 180 private void PointProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) { 181 int newWidth = newItem.Width; 182 int newDepth = newItem.Depth; 183 var binShape = binPacking.BinShape; 184 var sourcePoint = new PackingPosition(position.AssignedBin, position.X + newWidth, position.Y, position.Z); 185 PointProjection(binPacking, sourcePoint, ProjectDown); 186 PointProjection(binPacking, sourcePoint, ProjectBackward); 187 188 sourcePoint = new PackingPosition(position.AssignedBin, position.X, position.Y + newItem.Height, position.Z); 189 PointProjection(binPacking, sourcePoint, ProjectLeft); 190 PointProjection(binPacking, sourcePoint, ProjectBackward); 191 192 sourcePoint = new PackingPosition(position.AssignedBin, position.X, position.Y, position.Z + newDepth); 193 PointProjection(binPacking, sourcePoint, ProjectDown); 194 PointProjection(binPacking, sourcePoint, ProjectLeft); 195 } 196 197 198 /// <summary> 199 /// Projects a given point by using the given projection method to the neares item. 200 /// The given projection method returns a point which lies on a side of the nearest item in the direction. 201 /// </summary> 202 /// <param name="binPacking"></param> 203 /// <param name="position"></param> 204 /// <param name="projectionMethod"></param> 205 private void PointProjection(BinPacking3D binPacking, PackingPosition position, Func<BinPacking3D, Vector3D, Vector3D> projectionMethod) { 206 Vector3D sourcePoint = new Vector3D(position); 207 if (sourcePoint.X < binPacking.BinShape.Width && sourcePoint.Y < binPacking.BinShape.Height && sourcePoint.Z < binPacking.BinShape.Depth) { 208 Vector3D point = projectionMethod?.Invoke(binPacking, sourcePoint); 209 if (point != null) { 210 AddExtremePoint(binPacking, new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z)); 211 } 212 } 213 } 214 #endregion 215 216 #region Extreme point creation by using an edge projection based method 217 218 /// <summary> 219 /// This method creates extreme points be projecting the edges of a given item 220 /// - left 221 /// - back 222 /// - down. 223 /// A extreme point will be created, if an edge instersects with an edge of another item. 224 /// </summary> 225 /// <param name="binPacking"></param> 226 /// <param name="newItem"></param> 227 /// <param name="position"></param> 228 private void EdgeProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) { 229 int newWidth = newItem.Width; 230 int newDepth = newItem.Depth; 231 var binShape = binPacking.BinShape; 232 233 foreach (var ep in GetEpsOnLeft(binPacking, newItem, position)) { 234 AddExtremePoint(binPacking, ep.Key); 235 } 236 237 foreach (var ep in GetEpsBelow(binPacking, newItem, position)) { 238 AddExtremePoint(binPacking, ep.Key); 239 } 240 241 foreach (var ep in GetEpsBehind(binPacking, newItem, position)) { 242 AddExtremePoint(binPacking, ep.Key); 243 } 244 } 245 #endregion 246 247 /// <summary> 248 /// Updates the residual spaces. 249 /// It removes not needed ones. 250 /// A residual space will be removed if the space is a subspace of another one and 251 /// the current one has no item below or both have an item below. 252 /// </summary> 253 /// <param name="binPacking"></param> 254 /// <param name="item"></param> 255 /// <param name="position"></param> 53 256 protected override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) { 54 foreach (var extremePoint in binPacking.ExtremePoints.ToList()) { 55 var ep = extremePoint.Key; 56 var residualSpaces = extremePoint.Value as IList<ResidualSpace>; 57 for (int i = 0; i < residualSpaces.Count(); i++) { 58 var rs = residualSpaces[i]; 59 var depth = item.Depth; 60 var width = item.Width; 61 var changed = false; 62 if (ep.Z >= position.Z && ep.Z < position.Z + depth) { 63 if (ep.X <= position.X && ep.Y >= position.Y && ep.Y < position.Y + item.Height) { 64 var diff = position.X - ep.X; 65 var newRSX = Math.Min(rs.Width, diff); 66 rs = ResidualSpace.Create(newRSX, rs.Height, rs.Depth); 67 changed = true; 68 } 69 if (ep.Y <= position.Y && ep.X >= position.X && ep.X < position.X + width) { 70 var diff = position.Y - ep.Y; 71 var newRSY = Math.Min(rs.Height, diff); 72 rs = ResidualSpace.Create(rs.Width, newRSY, rs.Depth); 73 changed = true; 74 } 75 } 76 77 if (ep.Z <= position.Z && 78 ep.Y >= position.Y && ep.Y < position.Y + item.Height && 79 ep.X >= position.X && ep.X < position.X + width) { 80 var diff = position.Z - ep.Z; 81 var newRSZ = Math.Min(rs.Depth, diff); 82 rs = ResidualSpace.Create(rs.Width, rs.Height, newRSZ); 83 changed = true; 84 } 85 86 if (changed) { 87 if (!rs.IsZero() && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) { 88 residualSpaces[i] = rs; 89 } else { 90 binPacking.ExtremePoints.Remove(ep); 91 break; 92 } 93 } 94 } 95 } 96 return; 97 } 98 99 /// <summary> 100 /// Adds an extreme point to a given bin packing. 101 /// It also adds the residual space for the new extreme point 102 /// and removes the extreme point and the related residual space for the given position which are not needed anymore. 103 /// </summary> 104 /// <param name="binPacking"></param> 105 /// <param name="position"></param> 106 /// <returns></returns> 107 protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) { 108 if (binPacking.ExtremePoints.ContainsKey(position)) { 109 return false; 110 } 111 112 var residualSpaces = CalculateResidualSpace(binPacking, new Vector3D(position)); 113 binPacking.ExtremePoints.Add(position, residualSpaces); 114 // Check if the existing extreme points are shadowed by the new point 115 // This is, their residual space fit entirely into the residual space of the new point 116 foreach (var ep in binPacking.ExtremePoints.Where(x => x.Key != position && new Vector3D(x.Key).IsInside(position, residualSpaces)).ToList()) { 117 foreach (var residualSpace in ep.Value) { 118 if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep.Key), residualSpace, position, residualSpaces)) { 119 binPacking.ExtremePoints.Remove(ep); 120 break; 121 } 122 } 123 } 124 return true; 125 } 126 127 /// <summary> 128 /// Calculates the residual space for a given bin packing and position. 129 /// It returns the residual space as a tuple which contains the dimensions 130 /// </summary> 131 /// <param name="binPacking"></param> 132 /// <param name="pos"></param> 133 /// <returns>A Tuple(width, Height, Depth)</width></returns> 134 protected override IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) { 135 var residualSpaces = new List<ResidualSpace>(); 136 var residualSpace = new ResidualSpace(CalculateResidualSpaceOld(binPacking, pos)); 137 if (!residualSpace.IsZero()) { 138 residualSpaces.Add(residualSpace); 139 } 140 return residualSpaces; 141 } 142 143 protected Tuple<int, int, int> CalculateResidualSpaceOld(BinPacking3D binPacking, Vector3D pos) { 144 145 if (pos == null) { 146 return Tuple.Create(0, 0, 0); 147 } 148 var itemPos = binPacking.Items.Select(x => new { 257 } 258 259 /// <summary> 260 /// Returns true if any item in the bin packing encapsulates the given point 261 /// </summary> 262 /// <param name="binPacking"></param> 263 /// <param name="point"></param> 264 /// <returns></returns> 265 private bool PointIsInAnyItem(BinPacking3D binPacking, Vector3D point) { 266 foreach (var item in binPacking.Items) { 267 PackingPosition position = binPacking.Positions[item.Key]; 268 var depth = item.Value.Depth; 269 var width = item.Value.Width; 270 if (position.X <= point.X && point.X < position.X + width && 271 position.Y <= point.Y && point.Y < position.Y + item.Value.Height && 272 position.Z <= point.Z && point.Z < position.Z + depth) { 273 return true; 274 } 275 } 276 return false; 277 } 278 279 /// <summary> 280 /// Returns true if an item is in the residual space of a given extrem point 281 /// </summary> 282 /// <param name="rs">KeyValuePair with the position of the extreme point and the size of the residual space</param> 283 /// <param name="item">Given Item</param> 284 /// <param name="position">Given position</param> 285 /// <returns></returns> 286 private bool ItemIsInRs(KeyValuePair<PackingPosition, ResidualSpace> rs, PackingItem item, PackingPosition position) { 287 return GetVertices(item, position).Where(pos => pos.IsInside(rs.Key, rs.Value)).Any(); 288 } 289 290 protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) { 291 return binPacking.Items.Select(x => new { 149 292 Item = x.Value, 150 293 Position = binPacking.Positions[x.Key] 151 }); 152 Vector3D limit = new Vector3D() { 153 X = binPacking.BinShape.Width, 154 Y = binPacking.BinShape.Height, 155 Z = binPacking.BinShape.Depth 294 }).Where(x => x.Position.Y < position.Y) 295 .Select(x => Tuple.Create(x.Position, x.Item)); 296 } 297 298 protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) { 299 return binPacking.Items.Select(x => new { 300 Item = x.Value, 301 Position = binPacking.Positions[x.Key] 302 }).Where(x => x.Position.Z < position.Z) 303 .Select(x => Tuple.Create(x.Position, x.Item)); 304 } 305 306 protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) { 307 return binPacking.Items.Select(x => new { 308 Item = x.Value, 309 Position = binPacking.Positions[x.Key] 310 }).Where(x => x.Position.X < position.X) 311 .Select(x => Tuple.Create(x.Position, x.Item)); 312 } 313 314 /// <summary> 315 /// Returns the extreme points and its related residual spaces on the left side of an given item. 316 /// This extreme points are being created by intersecting two edges on the left side of the given item 317 /// (left - in front, left - on top) with all edges on the right side of all other items int the bin packing. 318 /// </summary> 319 /// <param name="item"></param> 320 /// <param name="position"></param> 321 /// <returns></returns> 322 private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) { 323 var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>(); 324 IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsOnLeft(binPacking, item, position); 325 var edges = GetProjectionEdgesOnLeft(item, position); 326 327 foreach (var otherItem in items) { 328 if (position.Equals(otherItem.Item1)) { 329 continue; 330 } 331 332 var otherItemEdges = GetEdgesOnRight(otherItem.Item2, otherItem.Item1); 333 // left - in front 334 foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(1, 0, 0))) { 335 if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) { 336 // As this edge has a vertical direction, every point of intersection won't have an item below. 337 // So finally it is being projected down. 338 var point = ProjectDown(binPacking, ProjectLeft(binPacking, ep)); 339 var residualSpaces = CalculateResidualSpace(binPacking, point); 340 var newExtremePoint = point.ToPackingPosition(position.AssignedBin); 341 if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) { 342 eps.Add(newExtremePoint, residualSpaces); 343 } 344 } 345 } 346 347 // left - on top 348 foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(1, 0, 0))) { 349 if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) { 350 var point = ProjectLeft(binPacking, ep); 351 var residualSpaces = CalculateResidualSpace(binPacking, point); 352 var newExtremePoint = point.ToPackingPosition(position.AssignedBin); 353 if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) { 354 eps.Add(newExtremePoint, residualSpaces); 355 } 356 } 357 } 358 } 359 return eps; 360 } 361 362 363 /// <summary> 364 /// Returns the extreme points and its related residual spaces below of an given item. 365 /// This extreme points are being created by intersecting two edges below of the given item 366 /// (below - in front, below - right) with all edges on top side of all other items int the bin packing. 367 /// </summary> 368 /// <param name="item"></param> 369 /// <param name="position"></param> 370 /// <returns></returns> 371 private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) { 372 var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>(); 373 IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBelow(binPacking, position); 374 var edges = GetProjectionEdgesBelow(item, position); 375 376 foreach (var otherItem in items) { 377 if (position.Equals(otherItem.Item1)) { 378 continue; 379 } 380 381 var otherItemEdges = GetEdgesOnTop(otherItem.Item2, otherItem.Item1); 382 // below - in front 383 foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 1, 0))) { 384 if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) { 385 var point = ProjectDown(binPacking, ep); 386 var residualSpaces = CalculateResidualSpace(binPacking, point); 387 var newExtremePoint = point.ToPackingPosition(position.AssignedBin); 388 if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) { 389 eps.Add(newExtremePoint, residualSpaces); 390 } 391 } 392 } 393 394 // below - right 395 foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 1, 0))) { 396 if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) { 397 var point = ProjectDown(binPacking, ep); 398 var residualSpaces = CalculateResidualSpace(binPacking, point); 399 var newExtremePoint = point.ToPackingPosition(position.AssignedBin); 400 if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) { 401 eps.Add(newExtremePoint, residualSpaces); 402 } 403 } 404 } 405 } 406 return eps; 407 } 408 409 /// <summary> 410 /// Returns the extreme points and its related residual spaces below of an given item. 411 /// This extreme points are being created by intersecting two edges below of the given item 412 /// (right - behind, on top - behind) with all edges on top side of all other items int the bin packing. 413 /// </summary> 414 /// <param name="item"></param> 415 /// <param name="position"></param> 416 /// <returns></returns> 417 private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) { 418 var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>(); 419 IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBehind(binPacking, position); 420 var edges = GetProjectionEdgesBehind(item, position); 421 422 foreach (var otherItem in items) { 423 if (position.Equals(otherItem.Item1)) { 424 continue; 425 } 426 427 var otherItemEdges = GetEdgesInFront(otherItem.Item2, otherItem.Item1); 428 // right - behind 429 foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 0, 1))) { 430 if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) { 431 // As this edge has a vertical direction, every point of intersection won't have an item below. 432 // So finally it is being projected down. 433 var point = ProjectDown(binPacking, ProjectBackward(binPacking, ep)); 434 var residualSpaces = CalculateResidualSpace(binPacking, point); 435 var newExtremePoint = point.ToPackingPosition(position.AssignedBin); 436 if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) { 437 eps.Add(newExtremePoint, residualSpaces); 438 } 439 } 440 } 441 442 // on top - behind 443 foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 0, 1))) { 444 if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) { 445 var point = ProjectBackward(binPacking, ep); 446 var residualSpaces = CalculateResidualSpace(binPacking, point); 447 var newExtremePoint = point.ToPackingPosition(position.AssignedBin); 448 if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) { 449 eps.Add(newExtremePoint, residualSpaces); 450 } 451 } 452 } 453 } 454 return eps; 455 } 456 457 #region Methods for getting the edges for items 458 459 /// <summary> 460 /// Returns an array of packing position which represents the vertices of an item. 461 /// The position of a vertex in the array is mapped to an item as followed: 462 /// 4----------5 463 /// /| /| 464 /// / | / | 465 /// / 0-------/--1 466 /// 6--/-------7 / 467 /// | / | / 468 /// |/ |/ 469 /// 2----------3 470 /// 471 /// 0 = (0,0,0) 472 /// </summary> 473 /// <param name="item"></param> 474 /// <param name="position"></param> 475 /// <returns></returns> 476 private Vector3D[] GetVertices(PackingItem item, PackingPosition position) { 477 int width = item.Width; 478 int depth = item.Depth; 479 return new Vector3D[] { 480 new Vector3D(position.X + 0, position.Y + 0, position.Z + 0), // (0,0,0) 481 new Vector3D(position.X + width, position.Y + 0, position.Z + 0), // (x,0,0) 482 new Vector3D(position.X + 0, position.Y + 0, position.Z + depth), // (0,0,z) 483 new Vector3D(position.X + width, position.Y + 0, position.Z + depth), // (x,0,z) 484 485 new Vector3D(position.X + 0, position.Y + item.Height, position.Z + 0), // (0,y,0) 486 new Vector3D(position.X + width, position.Y + item.Height, position.Z + 0), // (x,y,0) 487 new Vector3D(position.X + 0, position.Y + item.Height, position.Z + depth), // (0,y,z) 488 new Vector3D(position.X + width, position.Y + item.Height, position.Z + depth), //(x,y,z) 156 489 }; 157 158 if (pos.X < limit.X && pos.Y < limit.Y && pos.Z < limit.Z) { 159 var rightLimit = ProjectRight(binPacking, pos); 160 var upLimit = ProjectUp(binPacking, pos); 161 var forwardLimit = ProjectForward(binPacking, pos); 162 if (rightLimit.X > 0) { 163 limit.X = rightLimit.X; 164 } 165 if (upLimit.Y > 0) { 166 limit.Y = upLimit.Y; 167 } 168 if (forwardLimit.Z > 0) { 169 limit.Z = forwardLimit.Z; 170 } 171 } 172 173 if (limit.X - pos.X <= 0 || limit.Y - pos.Y <= 0 || limit.Z - pos.Z <= 0) { 174 return Tuple.Create(0, 0, 0); 175 } 176 return Tuple.Create(limit.X - pos.X, limit.Y - pos.Y, limit.Z - pos.Z); 490 } 491 492 private Edge3D[] GetProjectionEdgesOnLeft(PackingItem item, PackingPosition position) { 493 Vector3D[] points = GetVertices(item, position); 494 495 return new Edge3D[] { 496 new Edge3D(points[2], points[6]), 497 new Edge3D(points[6], points[4]) 498 }; 499 } 500 501 private Edge3D[] GetProjectionEdgesBelow(PackingItem item, PackingPosition position) { 502 Vector3D[] points = GetVertices(item, position); 503 504 return new Edge3D[] { 505 new Edge3D(points[2], points[3]), 506 new Edge3D(points[3], points[1]) 507 }; 508 } 509 510 private Edge3D[] GetProjectionEdgesBehind(PackingItem item, PackingPosition position) { 511 Vector3D[] points = GetVertices(item, position); 512 513 return new Edge3D[] { 514 new Edge3D(points[1], points[5]), 515 new Edge3D(points[5], points[4]) 516 }; 517 } 518 519 /// <summary> 520 /// Returns an array of edges which contains all edges of the rigth side of an given item. 521 /// </summary> 522 /// <param name="item"></param> 523 /// <param name="position"></param> 524 /// <returns></returns> 525 private Edge3D[] GetEdgesOnRight(PackingItem item, PackingPosition position) { 526 Vector3D[] points = GetVertices(item, position); 527 528 return new Edge3D[] { 529 new Edge3D(points[1], points[5]), 530 new Edge3D(points[5], points[7]), 531 new Edge3D(points[7], points[3]), 532 new Edge3D(points[3], points[1]) 533 }; 534 } 535 536 /// <summary> 537 /// Returns an array of edges which contains all edges on the top of an given item. 538 /// </summary> 539 /// <param name="item"></param> 540 /// <param name="position"></param> 541 /// <returns></returns> 542 private Edge3D[] GetEdgesOnTop(PackingItem item, PackingPosition position) { 543 Vector3D[] points = GetVertices(item, position); 544 545 return new Edge3D[] { 546 new Edge3D(points[4], points[5]), 547 new Edge3D(points[5], points[7]), 548 new Edge3D(points[7], points[6]), 549 new Edge3D(points[6], points[4]) 550 }; 551 } 552 553 /// <summary> 554 /// Returns an array of edges which contains all edges in front of an given item. 555 /// </summary> 556 /// <param name="item"></param> 557 /// <param name="position"></param> 558 /// <returns></returns> 559 private Edge3D[] GetEdgesInFront(PackingItem item, PackingPosition position) { 560 Vector3D[] points = GetVertices(item, position); 561 562 return new Edge3D[] { 563 new Edge3D(points[2], points[3]), 564 new Edge3D(points[3], points[7]), 565 new Edge3D(points[7], points[6]), 566 new Edge3D(points[6], points[2]) 567 }; 568 } 569 570 #endregion 571 572 573 #region Intersections 574 575 /// <summary> 576 /// Returns a collection of points where a given edge (projectedEdge) intersects with other edges. 577 /// The given edge (projectedEdge) will be projected by using the given vector direction 578 /// and a edge of the given edge collection. 579 /// The returned collecten can be empty. 580 /// </summary> 581 /// <param name="projectedEdge"></param> 582 /// <param name="edges"></param> 583 /// <param name="direction"></param> 584 /// <returns></returns> 585 private IEnumerable<Vector3D> IntersectionsForItem(Edge3D projectedEdge, Edge3D[] edges, Vector3D direction = null) { 586 IList<Vector3D> eps = new List<Vector3D>(); 587 foreach (var edge in edges) { 588 Edge3D e = projectedEdge; 589 if (direction != null) { 590 if (direction.X != 0) { 591 e.Start.X = edge.Start.X; 592 e.End.X = edge.End.X; 593 } else if (direction.Y != 0) { 594 e.Start.Y = edge.Start.Y; 595 e.End.Y = edge.End.Y; 596 } else if (direction.Z != 0) { 597 e.Start.Z = edge.Start.Z; 598 e.End.Z = edge.End.Z; 599 } 600 } 601 602 var ep = edge.Intersects(e); 603 if (ep != null) { 604 eps.Add(ep); 605 } 606 } 607 608 return eps as IEnumerable<Vector3D>; 609 } 610 611 612 613 #endregion 614 615 /// <summary> 616 /// Calculates the residual spaces for an extreme point. 617 /// </summary> 618 /// <param name="binPacking"></param> 619 /// <param name="pos"></param> 620 /// <returns></returns> 621 protected override IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) { 622 return ResidualSpaceCalculatorFactory.CreateCalculator().CalculateResidualSpaces(binPacking, pos); 177 623 } 178 624 }
Note: See TracChangeset
for help on using the changeset viewer.