Changeset 15554 for branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/LineProjectionBasedEPCreator.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/LineProjectionBasedEPCreator.cs
r15520 r15554 15 15 public class LineProjectionBasedEPCreator : ExtremePointCreator { 16 16 17 18 19 20 17 protected override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) { 21 // After a item has been placed, the residual space has to be recalculated.22 //RecalculateResidualSpaces(binPacking);23 24 //GenerateNewExtremePointsForItem(binPacking, item, position);25 26 18 binPacking.ExtremePoints.Clear(); 27 binPacking.ResidualSpaces.Clear();28 19 29 20 foreach (var i in binPacking.Items) { … … 32 23 GenerateNewExtremePointsForItem(binPacking, it, p); 33 24 } 34 //RecalculateResidualSpaces(binPacking);35 } 36 37 /// <summary>38 /// Adds an new extreme point an the related residual space to a given bin packing.39 /// - The given position has to be valid40 /// - The residual space must not be zero41 /// </summary> 42 /// <param name="binPacking"></param> 43 /// <param name="position"></param> 44 /// <returns> </returns>25 } 26 27 /// <summary> 28 /// Adds a new extreme point an the related residual spaces to a given bin packing. 29 /// - The given position has to be valid. 30 /// - The extreme point does not exist in the bin packing. 31 /// - There must be at minimum one valid residual space. A residual space is invalid if the space is zero. 32 /// </summary> 33 /// <param name="binPacking"></param> 34 /// <param name="position"></param> 35 /// <returns>True = the given point and its related residual spaces were successfully added to the bin packing</returns> 45 36 protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) { 46 37 if (position == null) { … … 48 39 } 49 40 50 if (PointIsIn Item(binPacking, new Vector3D(position))) {41 if (PointIsInAnyItem(binPacking, new Vector3D(position))) { 51 42 return false; 52 43 } 53 44 45 if (binPacking.ExtremePoints.ContainsKey(position)) { 46 return false; 47 } 48 54 49 var rs = CalculateResidualSpace(binPacking, new Vector3D(position)); 55 50 56 if (rs. IsZero()) {51 if (rs.Count() <= 0) { 57 52 return false; 58 53 } 59 54 60 if (!binPacking.ExtremePoints.Add(position)) { 55 // todo 56 /* 57 ist der extrempunkt im residual space eines anderen muss ueberprueft werden: 58 - ist der andere ep in der luft, kann auch dieser hinzugefuegt werden. 59 - hat der andere ep ein item unterhalb, darf dieser nicht hinzugefuegt werden. 60 -> neu methode basierend auf IsWithinResidualSpaceOfAnotherExtremePoint, die den ep oder rs zurueck gibt, der einen anderen rs einschließt. 61 eventuell gehoert diese logik in den ResidualSpaceCreator. 62 if (LiesOnAnyItem(binPacking, position)) { 61 63 return false; 62 } 63 64 binPacking. ResidualSpaces.Add(position, rs);64 }*/ 65 66 binPacking.ExtremePoints.Add(position, rs); 65 67 return true; 68 } 69 70 private bool LiesOnAnyItem(BinPacking3D binPacking, PackingPosition position) { 71 if (position.Y == 0) { 72 return true; 73 } 74 75 var items = binPacking.Items.Where(x => { 76 var itemPosition = binPacking.Positions[x.Key]; 77 var item = x.Value; 78 int width = itemPosition.Rotated ? item.Depth : item.Width; 79 int depth = itemPosition.Rotated ? item.Width : item.Depth; 80 81 return itemPosition.Y + item.Height == position.Y && 82 itemPosition.X <= position.X && position.X < itemPosition.X + width && 83 itemPosition.Z <= position.Z && position.Z < itemPosition.Z + depth; 84 }); 85 86 return items.Count() > 0; 66 87 } 67 88 … … 83 104 /// <summary> 84 105 /// This method creates extreme points by using a point projection based method. 85 /// For each item there will be three points created and each of the pointwill be projected twice.106 /// For each item there will be created three points and each of the points will be projected twice. 86 107 /// The direction of the projection depends on position of the point. 87 108 /// </summary> … … 118 139 if (sourcePoint.X < binPacking.BinShape.Width && sourcePoint.Y < binPacking.BinShape.Height && sourcePoint.Z < binPacking.BinShape.Depth) { 119 140 Vector3D point = projectionMethod?.Invoke(binPacking, sourcePoint); 120 AddExtremePoint(binPacking, new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z)); 141 if (point != null) { 142 AddExtremePoint(binPacking, new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z)); 143 } 121 144 } 122 145 } … … 141 164 142 165 foreach (var ep in GetEpsOnLeft(binPacking, newItem, position)) { 143 AddExtremePoint(binPacking, ep );166 AddExtremePoint(binPacking, ep.Key); 144 167 } 145 168 146 169 foreach (var ep in GetEpsBelow(binPacking, newItem, position)) { 147 AddExtremePoint(binPacking, ep );170 AddExtremePoint(binPacking, ep.Key); 148 171 } 149 172 150 173 foreach (var ep in GetEpsBehind(binPacking, newItem, position)) { 151 AddExtremePoint(binPacking, ep );174 AddExtremePoint(binPacking, ep.Key); 152 175 } 153 176 } 154 177 #endregion 155 178 156 179 /// <summary> 180 /// Updates the residual spaces. 181 /// It removes not needed ones. 182 /// A residual space will be removed if the space is a subspace of another one and 183 /// the current one has no item below or both have an item below. 184 /// </summary> 185 /// <param name="binPacking"></param> 186 /// <param name="item"></param> 187 /// <param name="position"></param> 157 188 protected override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) { 158 return; 159 } 160 161 private bool PointIsInItem(BinPacking3D binPacking, Vector3D point) { 189 } 190 191 /// <summary> 192 /// Returns true if any item in the bin packing encapsulates the given point 193 /// </summary> 194 /// <param name="binPacking"></param> 195 /// <param name="point"></param> 196 /// <returns></returns> 197 private bool PointIsInAnyItem(BinPacking3D binPacking, Vector3D point) { 162 198 foreach (var item in binPacking.Items) { 163 199 PackingPosition position = binPacking.Positions[item.Key]; … … 184 220 } 185 221 186 /// <summary>187 /// Recalculates the residual spaces if needed.188 /// It checks if an item is in an residual space and if so the residual space will be recalculated.189 /// If the residual space has gone to zero, this residual space and its related extreme point will be removed.190 /// </summary>191 /// <param name="binPacking"></param>192 private void RecalculateResidualSpaces(BinPacking3D binPacking) {193 var recalculatedSpaces = new Dictionary<PackingPosition, ResidualSpace>();194 foreach (var ep in binPacking.ExtremePoints.ToList()) {195 var newRs = CalculateResidualSpace(binPacking, new Vector3D(ep));196 if (!newRs.IsZero() && !PointIsInItem(binPacking, new Vector3D(ep))) {197 recalculatedSpaces.Add(ep, newRs);198 } else {199 binPacking.ExtremePoints.Remove(ep);200 }201 }202 binPacking.ResidualSpaces = recalculatedSpaces;203 }204 205 222 protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) { 206 223 return binPacking.Items.Select(x => new { … … 228 245 229 246 /// <summary> 230 /// Returns the extremepoints on the left side of an given item 231 /// </summary> 232 /// <param name="item"></param> 233 /// <param name="position"></param> 234 /// <returns></returns> 235 private IList<PackingPosition> GetEpsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) { 236 IList<PackingPosition> eps = new List<PackingPosition>(); 247 /// Returns the extreme points and its related residual spaces on the left side of an given item. 248 /// This extreme points are being created by intersecting two edges on the left side of the given item 249 /// (left - in front, left - on top) with all edges on the right side of all other items int the bin packing. 250 /// </summary> 251 /// <param name="item"></param> 252 /// <param name="position"></param> 253 /// <returns></returns> 254 private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) { 255 var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>(); 237 256 IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsOnLeft(binPacking, item, position); 238 257 var edges = GetProjectionEdgesOnLeft(item, position); 239 258 240 259 foreach (var otherItem in items) { 260 if (position.Equals(otherItem.Item1)) { 261 continue; 262 } 263 241 264 var otherItemEdges = GetEdgesOnRight(otherItem.Item2, otherItem.Item1); 265 // left - in front 242 266 foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(1, 0, 0))) { 243 267 if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) { 268 // As this edge has a vertical direction, every point of intersection won't have an item below. 269 // So finally it is being projected down. 244 270 var point = ProjectDown(binPacking, ProjectLeft(binPacking, ep)); 245 var residualSpace = CalculateResidualSpace(binPacking, point); 246 if (!residualSpace.IsZero()) { 247 eps.Add(point.ToPackingPosition(position.AssignedBin)); 271 var residualSpaces = CalculateResidualSpace(binPacking, point); 272 var newExtremePoint = point.ToPackingPosition(position.AssignedBin); 273 if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) { 274 eps.Add(newExtremePoint, residualSpaces); 248 275 } 249 276 } 250 277 } 278 279 // left - on top 251 280 foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(1, 0, 0))) { 252 281 if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) { 253 282 var point = ProjectLeft(binPacking, ep); 254 var residualSpace = CalculateResidualSpace(binPacking, point); 255 if (!residualSpace.IsZero()) { 256 eps.Add(point.ToPackingPosition(position.AssignedBin)); 283 var residualSpaces = CalculateResidualSpace(binPacking, point); 284 var newExtremePoint = point.ToPackingPosition(position.AssignedBin); 285 if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) { 286 eps.Add(newExtremePoint, residualSpaces); 257 287 } 258 288 } … … 264 294 265 295 /// <summary> 266 /// Returns the extremepoints below of an given item 267 /// </summary> 268 /// <param name="item"></param> 269 /// <param name="position"></param> 270 /// <returns></returns> 271 private IList<PackingPosition> GetEpsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) { 272 IList<PackingPosition> eps = new List<PackingPosition>(); 296 /// Returns the extreme points and its related residual spaces below of an given item. 297 /// This extreme points are being created by intersecting two edges below of the given item 298 /// (below - in front, below - right) with all edges on top side of all other items int the bin packing. 299 /// </summary> 300 /// <param name="item"></param> 301 /// <param name="position"></param> 302 /// <returns></returns> 303 private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) { 304 var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>(); 273 305 IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBelow(binPacking, position); 274 306 var edges = GetProjectionEdgesBelow(item, position); 275 307 276 308 foreach (var otherItem in items) { 309 if (position.Equals(otherItem.Item1)) { 310 continue; 311 } 312 277 313 var otherItemEdges = GetEdgesOnTop(otherItem.Item2, otherItem.Item1); 314 // below - in front 278 315 foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 1, 0))) { 279 316 if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) { 280 317 var point = ProjectDown(binPacking, ep); 281 var residualSpace = CalculateResidualSpace(binPacking, point); 282 if (!residualSpace.IsZero()) { 283 eps.Add(point.ToPackingPosition(position.AssignedBin)); 318 var residualSpaces = CalculateResidualSpace(binPacking, point); 319 var newExtremePoint = point.ToPackingPosition(position.AssignedBin); 320 if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) { 321 eps.Add(newExtremePoint, residualSpaces); 284 322 } 285 323 } 286 324 } 325 326 // below - right 287 327 foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 1, 0))) { 288 328 if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) { 289 329 var point = ProjectDown(binPacking, ep); 290 var residualSpace = CalculateResidualSpace(binPacking, point); 291 if (!residualSpace.IsZero()) { 292 eps.Add(point.ToPackingPosition(position.AssignedBin)); 330 var residualSpaces = CalculateResidualSpace(binPacking, point); 331 var newExtremePoint = point.ToPackingPosition(position.AssignedBin); 332 if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) { 333 eps.Add(newExtremePoint, residualSpaces); 293 334 } 294 335 } … … 299 340 300 341 /// <summary> 301 /// Returns 302 /// </summary> 303 /// <param name="item"></param> 304 /// <param name="position"></param> 305 /// <returns></returns> 306 private IList<PackingPosition> GetEpsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) { 307 IList<PackingPosition> eps = new List<PackingPosition>(); 342 /// Returns the extreme points and its related residual spaces below of an given item. 343 /// This extreme points are being created by intersecting two edges below of the given item 344 /// (right - behind, on top - behind) with all edges on top side of all other items int the bin packing. 345 /// </summary> 346 /// <param name="item"></param> 347 /// <param name="position"></param> 348 /// <returns></returns> 349 private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) { 350 var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>(); 308 351 IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBehind(binPacking, position); 309 352 var edges = GetProjectionEdgesBehind(item, position); 310 353 311 354 foreach (var otherItem in items) { 355 if (position.Equals(otherItem.Item1)) { 356 continue; 357 } 358 312 359 var otherItemEdges = GetEdgesInFront(otherItem.Item2, otherItem.Item1); 360 // right - behind 313 361 foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 0, 1))) { 314 362 if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) { 363 // As this edge has a vertical direction, every point of intersection won't have an item below. 364 // So finally it is being projected down. 315 365 var point = ProjectDown(binPacking, ProjectBackward(binPacking, ep)); 316 var residualSpace = CalculateResidualSpace(binPacking, point); 317 if (!residualSpace.IsZero()) { 318 eps.Add(point.ToPackingPosition(position.AssignedBin)); 366 var residualSpaces = CalculateResidualSpace(binPacking, point); 367 var newExtremePoint = point.ToPackingPosition(position.AssignedBin); 368 if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) { 369 eps.Add(newExtremePoint, residualSpaces); 319 370 } 320 371 } 321 372 } 373 374 // on top - behind 322 375 foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 0, 1))) { 323 376 if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) { 324 377 var point = ProjectBackward(binPacking, ep); 325 var residualSpace = CalculateResidualSpace(binPacking, point); 326 if (!residualSpace.IsZero()) { 327 eps.Add(point.ToPackingPosition(position.AssignedBin)); 378 var residualSpaces = CalculateResidualSpace(binPacking, point); 379 var newExtremePoint = point.ToPackingPosition(position.AssignedBin); 380 if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) { 381 eps.Add(newExtremePoint, residualSpaces); 328 382 } 329 383 } … … 452 506 453 507 /// <summary> 454 /// 508 /// Returns a collection of points where a given edge (projectedEdge) intersects with other edges. 509 /// The given edge (projectedEdge) will be projected by using the given vector direction 510 /// and a edge of the given edge collection. 511 /// The returned collecten can be empty. 455 512 /// </summary> 456 513 /// <param name="projectedEdge"></param> 457 514 /// <param name="edges"></param> 515 /// <param name="direction"></param> 458 516 /// <returns></returns> 459 517 private IEnumerable<Vector3D> IntersectionsForItem(Edge3D projectedEdge, Edge3D[] edges, Vector3D direction = null) { … … 486 544 #endregion 487 545 488 489 protected override ResidualSpace CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) { 490 return ResidualSpaceCalculatorFactory.CreateCalculator().CalculateResidualSpaces(binPacking, pos).First(); 546 /// <summary> 547 /// Calculates the residual spaces for an extreme point. 548 /// </summary> 549 /// <param name="binPacking"></param> 550 /// <param name="pos"></param> 551 /// <returns></returns> 552 protected override IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) { 553 return ResidualSpaceCalculatorFactory.CreateCalculator().CalculateResidualSpaces(binPacking, pos); 491 554 } 492 555 } 493 556 494 557 495 558 }
Note: See TracChangeset
for help on using the changeset viewer.