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

Last change on this file since 15554 was 15554, checked in by rhanghof, 21 months ago

#2817:

  • Unittests
  • Bugfixes on the line projection based extreme point creation method
File size: 6.7 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 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);
62            changed = true;
63          }
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            }
72          }
73        }       
74      }
75      return;
76    }
77   
78    /// <summary>
79    /// Adds an extreme point to a given bin packing.
80    /// It also adds the residual space for the new extreme point
81    /// and removes the extreme point and the related residual space for the given position which are not needed anymore.
82    /// </summary>
83    /// <param name="binPacking"></param>
84    /// <param name="position"></param>
85    /// <returns></returns>
86    protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
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)) {
98            binPacking.ExtremePoints.Remove(ep);
99            break;
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;
143        }
144        if (upLimit.Y > 0) {
145          limit.Y = upLimit.Y;
146        }
147        if (forwardLimit.Z > 0) {
148          limit.Z = forwardLimit.Z;
149        }
150      }
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);
156    }
157  }
158}
Note: See TracBrowser for help on using the repository browser.