source: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/ExtremePointCreator.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: 16.4 KB
RevLine 
[15488]1using HeuristicLab.Common;
2using HeuristicLab.Problems.BinPacking3D.Geometry;
[15520]3using HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation;
[15488]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
[15520]14    public void UpdateBinPacking(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
15      UpdateExtremePoints(binPacking, item, position);
16      UpdateResidualSpace(binPacking, item, position);
17    }
[15488]18
[15520]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);
[15488]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>
[15520]37    protected virtual void GenerateNewExtremePointsForItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
[15488]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 residualSpace = CalculateResidualSpace(binPacking, below);
[15520]49        if (!residualSpace.IsZero()
[15488]50          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpace)) {
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        residualSpace = CalculateResidualSpace(binPacking, back);
[15520]59        if (!residualSpace.IsZero()
[15488]60          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpace)) {
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 residualSpace = CalculateResidualSpace(binPacking, left);
[15520]74        if (!residualSpace.IsZero()
[15488]75          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpace)) {
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        residualSpace = CalculateResidualSpace(binPacking, back);
[15520]84        if (!residualSpace.IsZero()
[15488]85          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpace)) {
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 residualSpace = CalculateResidualSpace(binPacking, below);
[15520]99        if (!residualSpace.IsZero()
[15488]100          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpace)) {
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        residualSpace = CalculateResidualSpace(binPacking, left);
[15520]109        if (!residualSpace.IsZero()
[15488]110          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpace)) {
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>
[15520]193    protected virtual bool IsWithinResidualSpaceOfAnotherExtremePoint(BinPacking3D binPacking, Vector3D pos, ResidualSpace residualSpace) {
194      var eps = binPacking.ExtremePoints.Where(x => !pos.Equals(x) && pos.IsInside(x, binPacking.ResidualSpaces[x]));
195      return eps.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, residualSpace, x, binPacking.ResidualSpaces[x]));
[15488]196    }
197
198    /// <summary>
[15520]199    /// Returns true, if the given poisition and the related residual space is within the residual space of the given extreme point
[15488]200    /// </summary>
201    /// <param name="pos"></param>
202    /// <param name="rsPos"></param>
203    /// <param name="ep"></param>
204    /// <param name="rsEp"></param>
205    /// <returns></returns>
[15520]206    protected virtual bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, ResidualSpace rsPos, PackingPosition ep, ResidualSpace rsEp) {
207      return rsEp.Width >= pos.X - ep.X + rsPos.Width
208          && rsEp.Height >= pos.Y - ep.Y + rsPos.Height
209          && rsEp.Depth >= pos.Z - ep.Z + rsPos.Depth;
[15488]210    }
211
212    /// <summary>
213    /// Calculates the residual space for a given bin packing and position.
214    /// It returns the residual space as a tuple which contains the dimensions
215    /// </summary>
216    /// <param name="binPacking"></param>
217    /// <param name="pos"></param>
218    /// <returns>A Tuple(width, Height, Depth)</width></returns>
[15520]219    protected virtual ResidualSpace CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
220      //return ResidualSpaceCalculator.Create().CalculateResidualSpace(binPacking, pos).First();
221      return new ResidualSpace(CalculateResidualSpaceOld(binPacking, pos));
222    }
223
224    protected virtual Tuple<int, int, int> CalculateResidualSpaceOld(BinPacking3D binPacking, Vector3D pos) {
225
[15488]226      if (pos == null) {
227        return Tuple.Create(0, 0, 0);
228      }
229      var itemPos = binPacking.Items.Select(x => new {
230        Item = x.Value,
231        Position = binPacking.Positions[x.Key]
232      });
233      Vector3D limit = new Vector3D() {
234        X = binPacking.BinShape.Width,
235        Y = binPacking.BinShape.Height,
236        Z = binPacking.BinShape.Depth
237      };
238
239      if (pos.X < limit.X && pos.Y < limit.Y && pos.Z < limit.Z) {
240        var rightLimit = ProjectRight(binPacking, pos);
241        var upLimit = ProjectUp(binPacking, pos);
242        var forwardLimit = ProjectForward(binPacking, pos);
243        if (rightLimit.X > 0) {
244          limit.X = rightLimit.X;
245        }
246        if (upLimit.Y > 0) {
247          limit.Y = upLimit.Y;
248        }
249        if (forwardLimit.Z > 0) {
250          limit.Z = forwardLimit.Z;
251        }
252      }
253
254      if (limit.X - pos.X <= 0 || limit.Y - pos.Y <= 0 || limit.Z - pos.Z <= 0) {
255        return Tuple.Create(0, 0, 0);
256      }
257      return Tuple.Create(limit.X - pos.X, limit.Y - pos.Y, limit.Z - pos.Z);
258    }
259
260    #endregion
261
262    #region Projections
263
264    protected Vector3D ProjectBackward(BinPacking3D binPacking, Vector3D pos) {
265      var line = new Line3D(pos, new Vector3D(0, 0, -1));
266      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
267                             .Select(x => new Plane3D(x.Position, x.Item, Side.Front))
268                             .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Back) })
269                             .Select(x => x.Intersect(line))
270                             .Where(x => x != null && x.Z <= pos.Z);
271      if (m.Where(x => x != null).Any()) {
272        return m.MaxItems(x => x.Y).First();
273      }
274      return null;
275    }
276
277    protected Vector3D ProjectLeft(BinPacking3D binPacking, Vector3D pos) {
278      var line = new Line3D(pos, new Vector3D(-1, 0, 0));
279      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
280                  .Select(x => new Plane3D(x.Position, x.Item, Side.Right))
281                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Left) })
282                  .Select(x => x.Intersect(line))
283                  .Where(x => x != null && x.X <= pos.X);
284      if (m.Where(x => x != null).Any()) {
285        return m.MaxItems(x => x.Y).First();
286      }
287      return null;
288    }
289
290    protected Vector3D ProjectDown(BinPacking3D binPacking, Vector3D pos) {
291      var line = new Line3D(pos, new Vector3D(0, -1, 0));
292      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
293                  .Select(x => new Plane3D(x.Position, x.Item, Side.Top))
294                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Bottom) })
295                  .Select(x => x.Intersect(line))
296                  .Where(x => x != null && x.Y <= pos.Y);
297      if (m.Where(x => x != null).Any()) {
298        return m.MaxItems(x => x.Y).First();
299      }
300      return null;
301    }
302
303    protected Vector3D ProjectForward(BinPacking3D binPacking, Vector3D pos) {
304      var line = new Line3D(pos, new Vector3D(0, 0, 1));
305      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
306                  .Select(x => new Plane3D(x.Position, x.Item, Side.Back))
307                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Front) })
308                  .Select(x => x.Intersect(line))
309                  .Where(x => x != null && x.Z >= pos.Z);
310      if (m.Where(x => x != null).Any()) {
311        return m.MaxItems(x => x.Y).First();
312      }
313      return null;
314    }
315
316    protected Vector3D ProjectRight(BinPacking3D binPacking, Vector3D pos) {
317      var line = new Line3D(pos, new Vector3D(1, 0, 0));
318      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
319                  .Select(x => new Plane3D(x.Position, x.Item, Side.Left))
320                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Right) })
321                  .Select(x => x.Intersect(line))
322                  .Where(x => x != null && x.X >= pos.X);
323      if (m.Where(x => x != null).Any()) {
324        return m.MaxItems(x => x.Y).First();
325      }
326      return null;
327    }
328
329    protected Vector3D ProjectUp(BinPacking3D binPacking, Vector3D pos) {
330      var line = new Line3D(pos, new Vector3D(0, 1, 0));
331      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
332                  .Select(x => new Plane3D(x.Position, x.Item, Side.Bottom))
333                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Top) })
334                  .Select(x => x.Intersect(line))
335                  .Where(x => x != null && x.Y >= pos.Y);
336      if (m.Where(x => x != null).Any()) {
337        return m.MaxItems(x => x.Y).First();
338      }
339      return null;
340    }
341    #endregion
342  }
343}
Note: See TracBrowser for help on using the repository browser.