source: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/PointProjectionBasedEPCreator.cs @ 15520

Last change on this file since 15520 was 15520, checked in by rhanghof, 2 years ago

#2817:

  • Changed the calculation algorithm for creating extreme points by using line based projection
  • Changed the calculation of the residual spaces for line based projection
File size: 4.5 KB
Line 
1using HeuristicLab.Common;
2using HeuristicLab.Problems.BinPacking3D.Geometry;
3using System;
4using System.Collections.Generic;
5using System.Linq;
6using System.Text;
7using System.Threading.Tasks;
8
9namespace HeuristicLab.Problems.BinPacking3D.ExtremePointCreation {
10
11  /// <summary>
12  /// This extreme point creation class uses the point projection based method by Crainic, T. G., Perboli, G., & Tadei, R. for creating extreme points.
13  /// Each extreme point of an item is being projectet backwards, downwards and to the left.
14  /// A new extreme point will be created where this projections instersects with another item or the bin boundins.
15  /// </summary>
16  public class PointProjectionBasedEPCreator : ExtremePointCreator {
17    protected override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
18      GenerateNewExtremePointsForItem(binPacking, item, position);
19
20      // if an item is fit in below, before, or left of another its extreme points have to be regenerated
21      foreach (var above in GetItemsAbove(binPacking, position)) {
22        GenerateNewExtremePointsForItem(binPacking, above.Item2, above.Item1);
23      }
24      foreach (var front in GetItemsInfront(binPacking, position)) {
25        GenerateNewExtremePointsForItem(binPacking, front.Item2, front.Item1);
26      }
27      foreach (var right in GetItemsOnRight(binPacking, position)) {
28        GenerateNewExtremePointsForItem(binPacking, right.Item2, right.Item1);
29      }
30    }
31   
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);
43            changed = true;
44          }
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;
50          }
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        }
70      }
71      return;
72    }
73   
74    /// <summary>
75    /// Adds an extreme point to a given bin packing.
76    /// It also adds the residual space for the new extreme point
77    /// and removes the extreme point and the related residual space for the given position which are not needed anymore.
78    /// </summary>
79    /// <param name="binPacking"></param>
80    /// <param name="position"></param>
81    /// <returns></returns>
82    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)) {
90            binPacking.ExtremePoints.Remove(ep);
91            binPacking.ResidualSpaces.Remove(ep);
92          }
93        }
94        return true;
95      }
96      return false;
97    }
98  }
99}
Note: See TracBrowser for help on using the repository browser.