source: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/ExtremePointCreator.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: 16.2 KB
Line 
1using HeuristicLab.Common;
2using HeuristicLab.Problems.BinPacking3D.Geometry;
3using HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation;
4using System;
5using System.Collections.Generic;
6using System.Linq;
7using System.Text;
8using System.Threading.Tasks;
9
10namespace HeuristicLab.Problems.BinPacking3D.ExtremePointCreation {
11  public abstract class ExtremePointCreator : IExtremePointCreator {
12
13
14    public void UpdateBinPacking(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
15      UpdateExtremePoints(binPacking, item, position);
16      UpdateResidualSpace(binPacking, item, position);
17    }
18
19    protected abstract void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position);
20
21    /// <summary>
22    /// Updates the residual space for a given bin packing
23    /// </summary>
24    /// <param name="binPacking"></param>
25    /// <param name="item"></param>
26    /// <param name="position"></param>
27    protected abstract void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position);
28    protected abstract bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position);
29
30    /// <summary>
31    /// Generates new extreme points for a given item and its position.
32    /// It also recalcualtes the residual space and removes the extreme points which are not needed any more.
33    /// </summary>
34    /// <param name="binPacking"></param>
35    /// <param name="newItem"></param>
36    /// <param name="position"></param>
37    protected virtual void GenerateNewExtremePointsForItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
38      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
39      int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
40      var binShape = binPacking.BinShape;
41
42      var itemPlacement = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] }).ToList();
43      // Find ExtremePoints beginning from sourcepointX
44      var sourcePoint = new Vector3D() { X = position.X + newWidth, Y = position.Y, Z = position.Z };
45      if (sourcePoint.X < binShape.Width && sourcePoint.Y < binShape.Height && sourcePoint.Z < binShape.Depth) {
46        // Projecting onto the XZ-plane
47        var below = ProjectDown(binPacking, sourcePoint);
48        var residualSpaces = CalculateResidualSpace(binPacking, below);
49        if (residualSpaces.Count() > 0
50          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpaces)) {
51          // add only if the projected point's residual space is not a sub-space
52          // of another extreme point's residual space
53          var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z);
54          AddExtremePoint(binPacking, belowPoint);
55        }
56        // Projecting onto the XY-plane
57        var back = ProjectBackward(binPacking, sourcePoint);
58        residualSpaces = CalculateResidualSpace(binPacking, back);
59        if (residualSpaces.Count() > 0
60          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpaces)) {
61          // add only if the projected point's residual space is not a sub-space
62          // of another extreme point's residual space
63          var backPoint = new PackingPosition(position.AssignedBin, back.X, back.Y, back.Z);
64          AddExtremePoint(binPacking, backPoint);
65        }
66      }
67
68      //Find ExtremePoints beginning from sourcepointY
69      sourcePoint = new Vector3D(position.X, position.Y + newItem.Height, position.Z);
70      if (sourcePoint.X < binShape.Width && sourcePoint.Y < binShape.Height && sourcePoint.Z < binShape.Depth) {
71        // Projecting onto the YZ-plane
72        var left = ProjectLeft(binPacking, sourcePoint);
73        var residualSpaces = CalculateResidualSpace(binPacking, left);
74        if (residualSpaces.Count() > 0
75          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpaces)) {
76          // add only if the projected point's residual space is not a sub-space
77          // of another extreme point's residual space
78          var leftPoint = new PackingPosition(position.AssignedBin, left.X, left.Y, left.Z);
79          AddExtremePoint(binPacking, leftPoint);
80        }
81        // Projecting onto the XY-plane
82        var back = ProjectBackward(binPacking, sourcePoint);
83        residualSpaces = CalculateResidualSpace(binPacking, back);
84        if (residualSpaces.Count() > 0
85          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpaces)) {
86          // add only if the projected point's residual space is not a sub-space
87          // of another extreme point's residual space
88          var backPoint = new PackingPosition(position.AssignedBin, back.X, back.Y, back.Z);
89          AddExtremePoint(binPacking, backPoint);
90        }
91      }
92
93      //Find ExtremePoints beginning from sourcepointZ
94      sourcePoint = new Vector3D(position.X, position.Y, position.Z + newDepth);
95      if (sourcePoint.X < binShape.Width && sourcePoint.Y < binShape.Height && sourcePoint.Z < binShape.Depth) {
96        // Projecting onto the XZ-plane
97        var below = ProjectDown(binPacking, sourcePoint);
98        var residualSpaces = CalculateResidualSpace(binPacking, below);
99        if (residualSpaces.Count() > 0
100          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpaces)) {
101          // add only if the projected point's residual space is not a sub-space
102          // of another extreme point's residual space
103          var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z);
104          AddExtremePoint(binPacking, belowPoint);
105        }
106        // Projecting onto the YZ-plane
107        var left = ProjectLeft(binPacking, sourcePoint);
108        residualSpaces = CalculateResidualSpace(binPacking, left);
109        if (residualSpaces.Count() > 0
110          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpaces)) {
111          // add only if the projected point's residual space is not a sub-space
112          // of another extreme point's residual space
113          var leftPoint = new PackingPosition(position.AssignedBin, left.X, left.Y, left.Z);
114          AddExtremePoint(binPacking, leftPoint);
115        }
116      }
117    }
118
119    #region Get items
120
121    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsAbove(BinPacking3D binPacking, PackingPosition pos) {
122      var line = new Line3D(pos, new Vector3D(0, 1, 0));
123      return binPacking.Items.Select(x => new {
124        Item = x.Value,
125        Position = binPacking.Positions[x.Key],
126        Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Bottom))
127      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
128        .Select(x => Tuple.Create(x.Position, x.Item));
129    }
130
131    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsInfront(BinPacking3D binPacking, PackingPosition pos) {
132      var line = new Line3D(pos, new Vector3D(0, 0, 1));
133      return binPacking.Items.Select(x => new {
134        Item = x.Value,
135        Position = binPacking.Positions[x.Key],
136        Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Back))
137      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
138        .Select(x => Tuple.Create(x.Position, x.Item));
139    }
140
141    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnRight(BinPacking3D binPacking, PackingPosition pos) {
142      var line = new Line3D(pos, new Vector3D(1, 0, 0));
143      return binPacking.Items.Select(x => new {
144        Item = x.Value,
145        Position = binPacking.Positions[x.Key],
146        Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Left))
147      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
148        .Select(x => Tuple.Create(x.Position, x.Item));
149    }
150
151    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(BinPacking3D binPacking, PackingPosition pos) {
152      var line = new Line3D(pos, new Vector3D(0, 1, 0));
153      return binPacking.Items.Select(x => new {
154        Item = x.Value,
155        Position = binPacking.Positions[x.Key],
156        Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Top))
157      }).Where(x => x.Intersection != null && x.Intersection.Y <= pos.Y)
158        .Select(x => Tuple.Create(x.Position, x.Item));
159    }
160
161    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBehind(BinPacking3D binPacking, PackingPosition pos) {
162      var line = new Line3D(pos, new Vector3D(0, 0, 1));
163      return binPacking.Items.Select(x => new {
164        Item = x.Value,
165        Position = binPacking.Positions[x.Key],
166        Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Front))
167      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
168        .Select(x => Tuple.Create(x.Position, x.Item));
169    }
170
171    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnLeft(BinPacking3D binPacking, PackingPosition pos) {
172      var line = new Line3D(pos, new Vector3D(1, 0, 0));
173      return binPacking.Items.Select(x => new {
174        Item = x.Value,
175        Position = binPacking.Positions[x.Key],
176        Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Right))
177      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
178        .Select(x => Tuple.Create(x.Position, x.Item));
179    }
180
181    #endregion
182
183    #region Residual space
184
185
186    /// <summary>
187    ///
188    /// </summary>
189    /// <param name="binPacking"></param>
190    /// <param name="pos"></param>
191    /// <param name="residualSpace"></param>
192    /// <returns></returns>
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));
225    }
226
227    /// <summary>
228    /// Returns true, if the given poisition and the related residual space is within the residual space of the given extreme point
229    /// </summary>
230    /// <param name="pos"></param>
231    /// <param name="rsPos"></param>
232    /// <param name="ep"></param>
233    /// <param name="rsEp"></param>
234    /// <returns></returns>
235    protected virtual bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, ResidualSpace rsPos, PackingPosition ep, ResidualSpace rsEp) {
236      return rsEp.Width >= pos.X - ep.X + rsPos.Width
237          && rsEp.Height >= pos.Y - ep.Y + rsPos.Height
238          && rsEp.Depth >= pos.Z - ep.Z + rsPos.Depth;
239    }
240
241    /// <summary>
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   
250    #endregion
251
252    #region Projections
253
254    protected Vector3D ProjectBackward(BinPacking3D binPacking, Vector3D pos) {
255      var line = new Line3D(pos, new Vector3D(0, 0, -1));
256      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
257                             .Select(x => new Plane3D(x.Position, x.Item, Side.Front))
258                             .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Back) })
259                             .Select(x => x.Intersect(line))
260                             .Where(x => x != null && x.Z <= pos.Z);
261      if (m.Where(x => x != null).Any()) {
262        return m.MaxItems(x => x.Y).First();
263      }
264      return null;
265    }
266
267    protected Vector3D ProjectLeft(BinPacking3D binPacking, Vector3D pos) {
268      var line = new Line3D(pos, new Vector3D(-1, 0, 0));
269      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
270                  .Select(x => new Plane3D(x.Position, x.Item, Side.Right))
271                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Left) })
272                  .Select(x => x.Intersect(line))
273                  .Where(x => x != null && x.X <= pos.X);
274      if (m.Where(x => x != null).Any()) {
275        return m.MaxItems(x => x.Y).First();
276      }
277      return null;
278    }
279
280    protected Vector3D ProjectDown(BinPacking3D binPacking, Vector3D pos) {
281      var line = new Line3D(pos, new Vector3D(0, -1, 0));
282      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
283                  .Select(x => new Plane3D(x.Position, x.Item, Side.Top))
284                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Bottom) })
285                  .Select(x => x.Intersect(line))
286                  .Where(x => x != null && x.Y <= pos.Y);
287      if (m.Where(x => x != null).Any()) {
288        return m.MaxItems(x => x.Y).First();
289      }
290      return null;
291    }
292
293    protected Vector3D ProjectForward(BinPacking3D binPacking, Vector3D pos) {
294      var line = new Line3D(pos, new Vector3D(0, 0, 1));
295      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
296                  .Select(x => new Plane3D(x.Position, x.Item, Side.Back))
297                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Front) })
298                  .Select(x => x.Intersect(line))
299                  .Where(x => x != null && x.Z >= pos.Z);
300      if (m.Where(x => x != null).Any()) {
301        return m.MaxItems(x => x.Y).First();
302      }
303      return null;
304    }
305
306    protected Vector3D ProjectRight(BinPacking3D binPacking, Vector3D pos) {
307      var line = new Line3D(pos, new Vector3D(1, 0, 0));
308      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
309                  .Select(x => new Plane3D(x.Position, x.Item, Side.Left))
310                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Right) })
311                  .Select(x => x.Intersect(line))
312                  .Where(x => x != null && x.X >= pos.X);
313      if (m.Where(x => x != null).Any()) {
314        return m.MaxItems(x => x.Y).First();
315      }
316      return null;
317    }
318
319    protected Vector3D ProjectUp(BinPacking3D binPacking, Vector3D pos) {
320      var line = new Line3D(pos, new Vector3D(0, 1, 0));
321      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
322                  .Select(x => new Plane3D(x.Position, x.Item, Side.Bottom))
323                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Top) })
324                  .Select(x => x.Intersect(line))
325                  .Where(x => x != null && x.Y >= pos.Y);
326      if (m.Where(x => x != null).Any()) {
327        return m.MaxItems(x => x.Y).First();
328      }
329      return null;
330    }
331    #endregion
332  }
333}
Note: See TracBrowser for help on using the repository browser.