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

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

#2817:

  • Bugfixes for the line projection based extreme point creation
  • Bugfixes for the tests
File size: 16.8 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
29    /// <summary>
30    /// Adds an extreme point to the bin packing.
31    /// </summary>
32    /// <param name="binPacking"></param>
33    /// <param name="position"></param>
34    /// <returns></returns>
35    protected abstract bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position);
36
37    /// <summary>
38    /// Generates new extreme points for a given item and its position.
39    /// It also recalcualtes the residual space and removes the extreme points which are not needed any more.
40    /// </summary>
41    /// <param name="binPacking"></param>
42    /// <param name="newItem"></param>
43    /// <param name="position"></param>
44    protected virtual void GenerateNewExtremePointsForItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
45      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
46      int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
47      var binShape = binPacking.BinShape;
48
49      var itemPlacement = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] }).ToList();
50      // Find ExtremePoints beginning from sourcepointX
51      var sourcePoint = new Vector3D() { X = position.X + newWidth, Y = position.Y, Z = position.Z };
52      if (sourcePoint.X < binShape.Width && sourcePoint.Y < binShape.Height && sourcePoint.Z < binShape.Depth) {
53        // Projecting onto the XZ-plane
54        var below = ProjectDown(binPacking, sourcePoint);
55        var residualSpaces = CalculateResidualSpace(binPacking, below);
56        if (residualSpaces.Count() > 0
57          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpaces)) {
58          // add only if the projected point's residual space is not a sub-space
59          // of another extreme point's residual space
60          var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z);
61          AddExtremePoint(binPacking, belowPoint);
62        }
63        // Projecting onto the XY-plane
64        var back = ProjectBackward(binPacking, sourcePoint);
65        residualSpaces = CalculateResidualSpace(binPacking, back);
66        if (residualSpaces.Count() > 0
67          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpaces)) {
68          // add only if the projected point's residual space is not a sub-space
69          // of another extreme point's residual space
70          var backPoint = new PackingPosition(position.AssignedBin, back.X, back.Y, back.Z);
71          AddExtremePoint(binPacking, backPoint);
72        }
73      }
74
75      //Find ExtremePoints beginning from sourcepointY
76      sourcePoint = new Vector3D(position.X, position.Y + newItem.Height, position.Z);
77      if (sourcePoint.X < binShape.Width && sourcePoint.Y < binShape.Height && sourcePoint.Z < binShape.Depth) {
78        // Projecting onto the YZ-plane
79        var left = ProjectLeft(binPacking, sourcePoint);
80        var residualSpaces = CalculateResidualSpace(binPacking, left);
81        if (residualSpaces.Count() > 0
82          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpaces)) {
83          // add only if the projected point's residual space is not a sub-space
84          // of another extreme point's residual space
85          var leftPoint = new PackingPosition(position.AssignedBin, left.X, left.Y, left.Z);
86          AddExtremePoint(binPacking, leftPoint);
87        }
88        // Projecting onto the XY-plane
89        var back = ProjectBackward(binPacking, sourcePoint);
90        residualSpaces = CalculateResidualSpace(binPacking, back);
91        if (residualSpaces.Count() > 0
92          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpaces)) {
93          // add only if the projected point's residual space is not a sub-space
94          // of another extreme point's residual space
95          var backPoint = new PackingPosition(position.AssignedBin, back.X, back.Y, back.Z);
96          AddExtremePoint(binPacking, backPoint);
97        }
98      }
99
100      //Find ExtremePoints beginning from sourcepointZ
101      sourcePoint = new Vector3D(position.X, position.Y, position.Z + newDepth);
102      if (sourcePoint.X < binShape.Width && sourcePoint.Y < binShape.Height && sourcePoint.Z < binShape.Depth) {
103        // Projecting onto the XZ-plane
104        var below = ProjectDown(binPacking, sourcePoint);
105        var residualSpaces = CalculateResidualSpace(binPacking, below);
106        if (residualSpaces.Count() > 0
107          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpaces)) {
108          // add only if the projected point's residual space is not a sub-space
109          // of another extreme point's residual space
110          var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z);
111          AddExtremePoint(binPacking, belowPoint);
112        }
113        // Projecting onto the YZ-plane
114        var left = ProjectLeft(binPacking, sourcePoint);
115        residualSpaces = CalculateResidualSpace(binPacking, left);
116        if (residualSpaces.Count() > 0
117          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpaces)) {
118          // add only if the projected point's residual space is not a sub-space
119          // of another extreme point's residual space
120          var leftPoint = new PackingPosition(position.AssignedBin, left.X, left.Y, left.Z);
121          AddExtremePoint(binPacking, leftPoint);
122        }
123      }
124    }
125
126    #region Get items
127
128    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsAbove(BinPacking3D binPacking, PackingPosition pos) {
129      var line = new Line3D(pos, new Vector3D(0, 1, 0));
130      return binPacking.Items.Select(x => new {
131        Item = x.Value,
132        Position = binPacking.Positions[x.Key],
133        Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Bottom))
134      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
135        .Select(x => Tuple.Create(x.Position, x.Item));
136    }
137
138    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsInfront(BinPacking3D binPacking, PackingPosition pos) {
139      var line = new Line3D(pos, new Vector3D(0, 0, 1));
140      return binPacking.Items.Select(x => new {
141        Item = x.Value,
142        Position = binPacking.Positions[x.Key],
143        Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Back))
144      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
145        .Select(x => Tuple.Create(x.Position, x.Item));
146    }
147
148    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnRight(BinPacking3D binPacking, PackingPosition pos) {
149      var line = new Line3D(pos, new Vector3D(1, 0, 0));
150      return binPacking.Items.Select(x => new {
151        Item = x.Value,
152        Position = binPacking.Positions[x.Key],
153        Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Left))
154      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
155        .Select(x => Tuple.Create(x.Position, x.Item));
156    }
157
158    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(BinPacking3D binPacking, PackingPosition pos) {
159      var line = new Line3D(pos, new Vector3D(0, 1, 0));
160      return binPacking.Items.Select(x => new {
161        Item = x.Value,
162        Position = binPacking.Positions[x.Key],
163        Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Top))
164      }).Where(x => x.Intersection != null && x.Intersection.Y <= pos.Y)
165        .Select(x => Tuple.Create(x.Position, x.Item));
166    }
167
168    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBehind(BinPacking3D binPacking, PackingPosition pos) {
169      var line = new Line3D(pos, new Vector3D(0, 0, 1));
170      return binPacking.Items.Select(x => new {
171        Item = x.Value,
172        Position = binPacking.Positions[x.Key],
173        Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Front))
174      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
175        .Select(x => Tuple.Create(x.Position, x.Item));
176    }
177
178    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnLeft(BinPacking3D binPacking, PackingPosition pos) {
179      var line = new Line3D(pos, new Vector3D(1, 0, 0));
180      return binPacking.Items.Select(x => new {
181        Item = x.Value,
182        Position = binPacking.Positions[x.Key],
183        Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Right))
184      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
185        .Select(x => Tuple.Create(x.Position, x.Item));
186    }
187
188    #endregion
189
190    #region Residual space
191
192
193    /// <summary>
194    ///
195    /// </summary>
196    /// <param name="binPacking"></param>
197    /// <param name="pos"></param>
198    /// <param name="residualSpace"></param>
199    /// <returns></returns>
200    protected bool IsWithinResidualSpaceOfAnotherExtremePoint(BinPacking3D binPacking, Vector3D pos, ResidualSpace residualSpace) {
201      var eps = binPacking.ExtremePoints.Where(x => !pos.Equals(x.Key) && pos.IsInside(x.Key, x.Value));
202      return eps.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, residualSpace, x.Key, x.Value));
203    }
204
205    /// <summary>
206    ///
207    /// </summary>
208    /// <param name="binPacking"></param>
209    /// <param name="pos"></param>
210    /// <param name="residualSpaces"></param>
211    /// <returns></returns>
212    protected bool IsWithinResidualSpaceOfAnotherExtremePoint(BinPacking3D binPacking, Vector3D pos, IEnumerable<ResidualSpace> residualSpaces) {
213      foreach (var residualSpace in residualSpaces) {
214        if (IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, pos, residualSpace)) {
215          return true;
216        }
217      }
218      return false;
219    }
220
221
222    /// <summary>
223    /// Returns true, if the given poisition (pos) and the related residual space is within any residual space of the given extreme point (ep).
224    /// </summary>
225    /// <param name="pos">Given poisition</param>
226    /// <param name="rsPos"></param>
227    /// <param name="ep">Given extreme point</param>
228    /// <param name="rsEp"></param>
229    /// <returns></returns>
230    protected bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, ResidualSpace rsPos, PackingPosition ep, IEnumerable<ResidualSpace> rsEp) {
231      return rsEp.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, rsPos, ep, x));
232    }
233
234    /// <summary>
235    /// Returns true, if the given poisition (pos) and the related residual space is within the residual space of the given extreme point (ep).
236    /// </summary>
237    /// <param name="pos">Given poisition</param>
238    /// <param name="rsPos"></param>
239    /// <param name="ep">Given extreme point</param>
240    /// <param name="rsEp"></param>
241    /// <returns></returns>
242    protected virtual bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, ResidualSpace rsPos, PackingPosition ep, ResidualSpace rsEp) {
243      /*old implementation
244      return rsEp.Width >= pos.X - ep.X + rsPos.Width
245          && rsEp.Height >= pos.Y - ep.Y + rsPos.Height
246          && rsEp.Depth >= pos.Z - ep.Z + rsPos.Depth;*/
247
248      var x = pos.X >= ep.X && pos.X + rsPos.Width <= ep.X + rsEp.Width;
249      var y = pos.Y >= ep.Y && pos.Y + rsPos.Height <= ep.Y + rsEp.Height;
250      var z = pos.Z >= ep.Z && pos.Z + rsPos.Depth <= ep.Z + rsEp.Depth;
251
252      return x && y && z;
253    }
254
255    /// <summary>
256    /// Calculates the residual spaces for a given bin packing and position.
257    /// It returns a collection of residual spaces
258    /// </summary>
259    /// <param name="binPacking"></param>
260    /// <param name="pos"></param>
261    /// <returns></returns>
262    protected abstract IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos);
263   
264    #endregion
265
266    #region Projections
267
268    protected Vector3D ProjectBackward(BinPacking3D binPacking, Vector3D pos) {
269      var line = new Line3D(pos, new Vector3D(0, 0, -1));
270      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
271                             .Select(x => new Plane3D(x.Position, x.Item, Side.Front))
272                             .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Back) })
273                             .Select(x => x.Intersect(line))
274                             .Where(x => x != null && x.Z <= pos.Z);
275      if (m.Where(x => x != null).Any()) {
276        return m.MaxItems(x => x.Y).First();
277      }
278      return null;
279    }
280
281    protected Vector3D ProjectLeft(BinPacking3D binPacking, Vector3D pos) {
282      var line = new Line3D(pos, new Vector3D(-1, 0, 0));
283      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
284                  .Select(x => new Plane3D(x.Position, x.Item, Side.Right))
285                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Left) })
286                  .Select(x => x.Intersect(line))
287                  .Where(x => x != null && x.X <= pos.X);
288      if (m.Where(x => x != null).Any()) {
289        return m.MaxItems(x => x.Y).First();
290      }
291      return null;
292    }
293
294    protected Vector3D ProjectDown(BinPacking3D binPacking, Vector3D pos) {
295      var line = new Line3D(pos, new Vector3D(0, -1, 0));
296      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
297                  .Select(x => new Plane3D(x.Position, x.Item, Side.Top))
298                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Bottom) })
299                  .Select(x => x.Intersect(line))
300                  .Where(x => x != null && x.Y <= pos.Y);
301      if (m.Where(x => x != null).Any()) {
302        return m.MaxItems(x => x.Y).First();
303      }
304      return null;
305    }
306
307    protected Vector3D ProjectForward(BinPacking3D binPacking, Vector3D pos) {
308      var line = new Line3D(pos, new Vector3D(0, 0, 1));
309      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
310                  .Select(x => new Plane3D(x.Position, x.Item, Side.Back))
311                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Front) })
312                  .Select(x => x.Intersect(line))
313                  .Where(x => x != null && x.Z >= pos.Z);
314      if (m.Where(x => x != null).Any()) {
315        return m.MaxItems(x => x.Y).First();
316      }
317      return null;
318    }
319
320    protected Vector3D ProjectRight(BinPacking3D binPacking, Vector3D pos) {
321      var line = new Line3D(pos, new Vector3D(1, 0, 0));
322      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
323                  .Select(x => new Plane3D(x.Position, x.Item, Side.Left))
324                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Right) })
325                  .Select(x => x.Intersect(line))
326                  .Where(x => x != null && x.X >= pos.X);
327      if (m.Where(x => x != null).Any()) {
328        return m.MaxItems(x => x.Y).First();
329      }
330      return null;
331    }
332
333    protected Vector3D ProjectUp(BinPacking3D binPacking, Vector3D pos) {
334      var line = new Line3D(pos, new Vector3D(0, 1, 0));
335      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
336                  .Select(x => new Plane3D(x.Position, x.Item, Side.Bottom))
337                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Top) })
338                  .Select(x => x.Intersect(line))
339                  .Where(x => x != null && x.Y >= pos.Y);
340      if (m.Where(x => x != null).Any()) {
341        return m.MaxItems(x => x.Y).First();
342      }
343      return null;
344    }
345    #endregion
346  }
347}
Note: See TracBrowser for help on using the repository browser.