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

Last change on this file since 15488 was 15488, checked in by rhanghof, 22 months ago

#2817:

  • Added line projection based bin packing
  • Added residual spaces to the view
File size: 15.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  public abstract class ExtremePointCreator : IExtremePointCreator {
11
12
13    public abstract void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position);
14
15    public abstract void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position);
16    protected abstract bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position);
17
18    /// <summary>
19    /// Generates new extreme points for a given item and its position.
20    /// It also recalcualtes the residual space and removes the extreme points which are not needed any more.
21    /// </summary>
22    /// <param name="binPacking"></param>
23    /// <param name="newItem"></param>
24    /// <param name="position"></param>
25    protected virtual void GenerateNewExtremePointsForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
26      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
27      int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
28      var binShape = binPacking.BinShape;
29
30      var itemPlacement = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] }).ToList();
31      // Find ExtremePoints beginning from sourcepointX
32      var sourcePoint = new Vector3D() { X = position.X + newWidth, Y = position.Y, Z = position.Z };
33      if (sourcePoint.X < binShape.Width && sourcePoint.Y < binShape.Height && sourcePoint.Z < binShape.Depth) {
34        // Projecting onto the XZ-plane
35        var below = ProjectDown(binPacking, sourcePoint);
36        var residualSpace = CalculateResidualSpace(binPacking, below);
37        if (IsNonZero(residualSpace)
38          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpace)) {
39          // add only if the projected point's residual space is not a sub-space
40          // of another extreme point's residual space
41          var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z);
42          AddExtremePoint(binPacking, belowPoint);
43        }
44        // Projecting onto the XY-plane
45        var back = ProjectBackward(binPacking, sourcePoint);
46        residualSpace = CalculateResidualSpace(binPacking, back);
47        if (IsNonZero(residualSpace)
48          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpace)) {
49          // add only if the projected point's residual space is not a sub-space
50          // of another extreme point's residual space
51          var backPoint = new PackingPosition(position.AssignedBin, back.X, back.Y, back.Z);
52          AddExtremePoint(binPacking, backPoint);
53        }
54      }
55
56      //Find ExtremePoints beginning from sourcepointY
57      sourcePoint = new Vector3D(position.X, position.Y + newItem.Height, position.Z);
58      if (sourcePoint.X < binShape.Width && sourcePoint.Y < binShape.Height && sourcePoint.Z < binShape.Depth) {
59        // Projecting onto the YZ-plane
60        var left = ProjectLeft(binPacking, sourcePoint);
61        var residualSpace = CalculateResidualSpace(binPacking, left);
62        if (IsNonZero(residualSpace)
63          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpace)) {
64          // add only if the projected point's residual space is not a sub-space
65          // of another extreme point's residual space
66          var leftPoint = new PackingPosition(position.AssignedBin, left.X, left.Y, left.Z);
67          AddExtremePoint(binPacking, leftPoint);
68        }
69        // Projecting onto the XY-plane
70        var back = ProjectBackward(binPacking, sourcePoint);
71        residualSpace = CalculateResidualSpace(binPacking, back);
72        if (IsNonZero(residualSpace)
73          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpace)) {
74          // add only if the projected point's residual space is not a sub-space
75          // of another extreme point's residual space
76          var backPoint = new PackingPosition(position.AssignedBin, back.X, back.Y, back.Z);
77          AddExtremePoint(binPacking, backPoint);
78        }
79      }
80
81      //Find ExtremePoints beginning from sourcepointZ
82      sourcePoint = new Vector3D(position.X, position.Y, position.Z + newDepth);
83      if (sourcePoint.X < binShape.Width && sourcePoint.Y < binShape.Height && sourcePoint.Z < binShape.Depth) {
84        // Projecting onto the XZ-plane
85        var below = ProjectDown(binPacking, sourcePoint);
86        var residualSpace = CalculateResidualSpace(binPacking, below);
87        if (IsNonZero(residualSpace)
88          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpace)) {
89          // add only if the projected point's residual space is not a sub-space
90          // of another extreme point's residual space
91          var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z);
92          AddExtremePoint(binPacking, belowPoint);
93        }
94        // Projecting onto the YZ-plane
95        var left = ProjectLeft(binPacking, sourcePoint);
96        residualSpace = CalculateResidualSpace(binPacking, left);
97        if (IsNonZero(residualSpace)
98          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpace)) {
99          // add only if the projected point's residual space is not a sub-space
100          // of another extreme point's residual space
101          var leftPoint = new PackingPosition(position.AssignedBin, left.X, left.Y, left.Z);
102          AddExtremePoint(binPacking, leftPoint);
103        }
104      }
105    }
106
107    #region Get items
108
109    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsAbove(BinPacking3D binPacking, PackingPosition pos) {
110      var line = new Line3D(pos, new Vector3D(0, 1, 0));
111      return binPacking.Items.Select(x => new {
112        Item = x.Value,
113        Position = binPacking.Positions[x.Key],
114        Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Bottom))
115      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
116        .Select(x => Tuple.Create(x.Position, x.Item));
117    }
118
119    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsInfront(BinPacking3D binPacking, PackingPosition pos) {
120      var line = new Line3D(pos, new Vector3D(0, 0, 1));
121      return binPacking.Items.Select(x => new {
122        Item = x.Value,
123        Position = binPacking.Positions[x.Key],
124        Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Back))
125      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
126        .Select(x => Tuple.Create(x.Position, x.Item));
127    }
128
129    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnRight(BinPacking3D binPacking, PackingPosition pos) {
130      var line = new Line3D(pos, new Vector3D(1, 0, 0));
131      return binPacking.Items.Select(x => new {
132        Item = x.Value,
133        Position = binPacking.Positions[x.Key],
134        Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Left))
135      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
136        .Select(x => Tuple.Create(x.Position, x.Item));
137    }
138
139    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(BinPacking3D binPacking, PackingPosition pos) {
140      var line = new Line3D(pos, new Vector3D(0, 1, 0));
141      return binPacking.Items.Select(x => new {
142        Item = x.Value,
143        Position = binPacking.Positions[x.Key],
144        Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Top))
145      }).Where(x => x.Intersection != null && x.Intersection.Y <= pos.Y)
146        .Select(x => Tuple.Create(x.Position, x.Item));
147    }
148
149    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBehind(BinPacking3D binPacking, PackingPosition pos) {
150      var line = new Line3D(pos, new Vector3D(0, 0, 1));
151      return binPacking.Items.Select(x => new {
152        Item = x.Value,
153        Position = binPacking.Positions[x.Key],
154        Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Front))
155      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
156        .Select(x => Tuple.Create(x.Position, x.Item));
157    }
158
159    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnLeft(BinPacking3D binPacking, PackingPosition pos) {
160      var line = new Line3D(pos, new Vector3D(1, 0, 0));
161      return binPacking.Items.Select(x => new {
162        Item = x.Value,
163        Position = binPacking.Positions[x.Key],
164        Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Right))
165      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
166        .Select(x => Tuple.Create(x.Position, x.Item));
167    }
168
169    #endregion
170
171    #region Residual space
172
173
174
175    protected virtual bool IsNonZero(Tuple<int, int, int> space) {
176      return space.Item1 > 0 && space.Item2 > 0 && space.Item3 > 0;
177    }
178
179    /// <summary>
180    ///
181    /// </summary>
182    /// <param name="binPacking"></param>
183    /// <param name="pos"></param>
184    /// <param name="residualSpace"></param>
185    /// <returns></returns>
186    protected virtual bool IsWithinResidualSpaceOfAnotherExtremePoint(BinPacking3D binPacking, Vector3D pos, Tuple<int, int, int> residualSpace) {
187      var eps = binPacking.ExtremePoints.Where(x => !pos.Equals(x) && pos.IsInside(x, binPacking.ResidualSpace[x]));
188      return eps.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, residualSpace, x, binPacking.ResidualSpace[x]));
189    }
190
191    /// <summary>
192    ///
193    /// </summary>
194    /// <param name="pos"></param>
195    /// <param name="rsPos"></param>
196    /// <param name="ep"></param>
197    /// <param name="rsEp"></param>
198    /// <returns></returns>
199    protected virtual bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> rsPos, PackingPosition ep, Tuple<int, int, int> rsEp) {
200      return rsEp.Item1 >= pos.X - ep.X + rsPos.Item1
201          && rsEp.Item2 >= pos.Y - ep.Y + rsPos.Item2
202          && rsEp.Item3 >= pos.Z - ep.Z + rsPos.Item3;
203    }
204
205    /// <summary>
206    /// Calculates the residual space for a given bin packing and position.
207    /// It returns the residual space as a tuple which contains the dimensions
208    /// </summary>
209    /// <param name="binPacking"></param>
210    /// <param name="pos"></param>
211    /// <returns>A Tuple(width, Height, Depth)</width></returns>
212    protected Tuple<int, int, int> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
213      if (pos == null) {
214        return Tuple.Create(0, 0, 0);
215      }
216      var itemPos = binPacking.Items.Select(x => new {
217        Item = x.Value,
218        Position = binPacking.Positions[x.Key]
219      });
220      Vector3D limit = new Vector3D() {
221        X = binPacking.BinShape.Width,
222        Y = binPacking.BinShape.Height,
223        Z = binPacking.BinShape.Depth
224      };
225
226      if (pos.X < limit.X && pos.Y < limit.Y && pos.Z < limit.Z) {
227        var rightLimit = ProjectRight(binPacking, pos);
228        var upLimit = ProjectUp(binPacking, pos);
229        var forwardLimit = ProjectForward(binPacking, pos);
230        if (rightLimit.X > 0) {
231          limit.X = rightLimit.X;
232        }
233        if (upLimit.Y > 0) {
234          limit.Y = upLimit.Y;
235        }
236        if (forwardLimit.Z > 0) {
237          limit.Z = forwardLimit.Z;
238        }
239      }
240
241      if (limit.X - pos.X <= 0 || limit.Y - pos.Y <= 0 || limit.Z - pos.Z <= 0) {
242        return Tuple.Create(0, 0, 0);
243      }
244      return Tuple.Create(limit.X - pos.X, limit.Y - pos.Y, limit.Z - pos.Z);
245    }
246
247    #endregion
248
249    #region Projections
250
251    protected Vector3D ProjectBackward(BinPacking3D binPacking, Vector3D pos) {
252      var line = new Line3D(pos, new Vector3D(0, 0, -1));
253      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
254                             .Select(x => new Plane3D(x.Position, x.Item, Side.Front))
255                             .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Back) })
256                             .Select(x => x.Intersect(line))
257                             .Where(x => x != null && x.Z <= pos.Z);
258      if (m.Where(x => x != null).Any()) {
259        return m.MaxItems(x => x.Y).First();
260      }
261      return null;
262    }
263
264    protected Vector3D ProjectLeft(BinPacking3D binPacking, Vector3D pos) {
265      var line = new Line3D(pos, new Vector3D(-1, 0, 0));
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.Right))
268                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Left) })
269                  .Select(x => x.Intersect(line))
270                  .Where(x => x != null && x.X <= pos.X);
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 ProjectDown(BinPacking3D binPacking, Vector3D pos) {
278      var line = new Line3D(pos, new Vector3D(0, -1, 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.Top))
281                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Bottom) })
282                  .Select(x => x.Intersect(line))
283                  .Where(x => x != null && x.Y <= pos.Y);
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 ProjectForward(BinPacking3D binPacking, Vector3D pos) {
291      var line = new Line3D(pos, new Vector3D(0, 0, 1));
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.Back))
294                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Front) })
295                  .Select(x => x.Intersect(line))
296                  .Where(x => x != null && x.Z >= pos.Z);
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 ProjectRight(BinPacking3D binPacking, Vector3D pos) {
304      var line = new Line3D(pos, new Vector3D(1, 0, 0));
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.Left))
307                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Right) })
308                  .Select(x => x.Intersect(line))
309                  .Where(x => x != null && x.X >= pos.X);
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 ProjectUp(BinPacking3D binPacking, Vector3D pos) {
317      var line = new Line3D(pos, new Vector3D(0, 1, 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.Bottom))
320                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Top) })
321                  .Select(x => x.Intersect(line))
322                  .Where(x => x != null && x.Y >= pos.Y);
323      if (m.Where(x => x != null).Any()) {
324        return m.MaxItems(x => x.Y).First();
325      }
326      return null;
327    }
328    #endregion
329  }
330}
Note: See TracBrowser for help on using the repository browser.