source: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/LineProjectionBasedEPCreator.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.3 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  /// <summary>
11  /// This extreme point creation class uses the line projection based method for creating extreme points.
12  /// </summary>
13  public class LineProjectionBasedEPCreator : ExtremePointCreator {
14
15
16   
17
18    public override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
19      // Before any extreme point for an item can be created, each residual space must be resized if the new item is in the residual space.
20      // If the residual spaces were not updated, it could be that an extreme point won't be generated because it lies in a residual space which
21      // size isn't correct anymore.
22      RecalculateResidualSpaces(binPacking, item, position);
23
24      GenerateNewExtremePointsForNewItem(binPacking, item, position);
25
26      foreach (var ep in GetEpsOnLeft(binPacking, item, position)) {
27        AddExtremePoint(binPacking, ep);
28      }
29
30      foreach (var ep in GetEpsBelow(binPacking, item, position)) {
31        AddExtremePoint(binPacking, ep);
32      }
33
34      foreach (var ep in GetEpsBehind(binPacking, item, position)) {
35        AddExtremePoint(binPacking, ep);
36      }
37    }
38
39    /// <summary>
40    /// Returns true, if the given poisition and the related residual space is within the residual space of the given extreme point
41    /// </summary>
42    /// <param name="pos">New Position</param>
43    /// <param name="rsPos"></param>
44    /// <param name="ep"></param>
45    /// <param name="rsEp"></param>
46    /// <returns></returns>
47    protected override bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> rsPos, PackingPosition ep, Tuple<int, int, int> rsEp) {
48      bool x = pos.X >= ep.X && rsPos.Item1 + pos.X <= rsEp.Item1 + ep.X;
49      bool y = (pos.Y >= ep.Y && pos.Y == 0 || pos.Y > ep.Y && pos.Y > 0) && rsPos.Item2 + pos.Y <= rsEp.Item2 + ep.Y;
50      bool z = pos.Z >= ep.Z && rsPos.Item3 + pos.Z <= rsEp.Item3 + ep.Z;
51      return x && y && z;
52    }
53
54    public override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
55      foreach (var ep in binPacking.ExtremePoints.ToList()) {
56        var rs = binPacking.ResidualSpace[ep];
57        var depth = position.Rotated ? item.Width : item.Depth;
58        var width = position.Rotated ? item.Depth : item.Width;
59        var changed = false;
60        if (ep.Z >= position.Z && ep.Z < position.Z + depth) {
61          if (ep.X <= position.X && ep.Y >= position.Y && ep.Y < position.Y + item.Height) {
62            var diff = position.X - ep.X;
63            var newRSX = Math.Min(rs.Item1, diff);
64            rs = Tuple.Create(newRSX, rs.Item2, rs.Item3);
65            changed = true;
66          }
67          if (ep.Y <= position.Y && ep.X >= position.X && ep.X < position.X + width) {
68            var diff = position.Y - ep.Y;
69            var newRSY = Math.Min(rs.Item2, diff);
70            rs = Tuple.Create(rs.Item1, newRSY, rs.Item3);
71            changed = true;
72          }
73        }
74
75        if (ep.Z <= position.Z &&
76            ep.Y >= position.Y && ep.Y < position.Y + item.Height &&
77            ep.X >= position.X && ep.X < position.X + width) {
78          var diff = position.Z - ep.Z;
79          var newRSZ = Math.Min(rs.Item3, diff);
80          rs = Tuple.Create(rs.Item1, rs.Item2, newRSZ);
81          changed = true;
82        }
83
84        if (changed) {
85          if (IsNonZero(rs) && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) {
86            binPacking.ResidualSpace[ep] = rs;
87          } else {
88            binPacking.ExtremePoints.Remove(ep);
89            binPacking.ResidualSpace.Remove(ep);
90          }
91        }
92      }
93      return;
94    }
95
96    protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
97      if (binPacking.ExtremePoints.Add(position)) {
98        var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
99        binPacking.ResidualSpace.Add(position, rs);
100        // Check if the existing extreme points are shadowed by the new point
101        // This is, their residual space fit entirely into the residual space of the new point
102        foreach (var ep in binPacking.ExtremePoints.Where(x => x != position && new Vector3D(x).IsInside(position, rs)).ToList()) {
103          if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), binPacking.ResidualSpace[ep], position, rs)) {
104            binPacking.ExtremePoints.Remove(ep);
105            binPacking.ResidualSpace.Remove(ep);
106          }
107        }
108        return true;
109      }
110      return false;
111    }
112
113    /// <summary>
114    /// Returns true if an item is in the residual space of a given extrem point
115    /// </summary>
116    /// <param name="rs">KeyValuePair with the position of the extreme point and the size of the residual space</param>
117    /// <param name="item">Given Item</param>
118    /// <param name="position">Given position</param>
119    /// <returns></returns>
120    private bool ItemIsInRs(KeyValuePair<PackingPosition, Tuple<int, int, int>> rs, PackingItem item, PackingPosition position) {
121      return GetVertices(item, position).Where(pos => pos.IsInside(rs.Key, rs.Value)).Any();
122    }
123
124    /// <summary>
125    /// Recalculates the residual spaces if needed.
126    /// It checks if an item is in an residual space and if so the residual space will be recalculated
127    /// </summary>
128    /// <param name="binPacking"></param>
129    /// <param name="item"></param>
130    /// <param name="position"></param>
131    private void RecalculateResidualSpaces(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
132      var recalculatedSpaces = new Dictionary<PackingPosition, Tuple<int, int, int>>();
133      foreach (var rs in binPacking.ResidualSpace) {
134        int width = rs.Value.Item1;
135        int height = rs.Value.Item2;
136        int depth = rs.Value.Item3;
137
138        if (ItemIsInRs(rs, item, position)) {
139          if (rs.Key.X + rs.Value.Item1 > position.X) {
140            width = position.X - rs.Key.X;
141          } else if (rs.Key.Y + rs.Value.Item2 > position.Y) {
142            height = position.Y - rs.Key.Y;
143          } else if (rs.Key.Z + rs.Value.Item3 > position.Z) {
144            depth = position.Z - rs.Key.Z;
145          }
146        }
147
148        var newRs = new Tuple<int, int, int>(width, height, depth);
149        if (IsNonZero(newRs)) {
150          recalculatedSpaces.Add(rs.Key, newRs);
151        } else {
152          recalculatedSpaces.Add(rs.Key, rs.Value);
153        }
154      }
155      binPacking.ResidualSpace = recalculatedSpaces;
156    }
157
158    /// <summary>
159    /// Returns the extremepoints on the left side of an given item
160    /// </summary>
161    /// <param name="item"></param>
162    /// <param name="position"></param>
163    /// <returns></returns>
164    private IList<PackingPosition> GetEpsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
165      IList<PackingPosition> eps = new List<PackingPosition>();
166      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsOnLeft(binPacking, position);
167      var edges = GetProjectionEdgesOnLeft(item, position);
168
169      foreach (var i in items) {
170        foreach (var edge in edges) {
171          var newEps = IntersectionsForItem(edge, GetEdgesOnRight(i.Item2, i.Item1));
172          foreach (var ep in newEps) {
173            try {
174              if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
175                var point = ProjectLeft(binPacking, ep);
176                var residualSpace = CalculateResidualSpace(binPacking, point);
177                if (IsNonZero(residualSpace)) {
178                  eps.Add(new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
179                }
180              }
181            } catch {
182              var s = ep;
183            }
184          }
185        }
186      }
187      return eps;
188    }
189
190    /// <summary>
191    /// Returns the extremepoints below of an given item
192    /// </summary>
193    /// <param name="item"></param>
194    /// <param name="position"></param>
195    /// <returns></returns>
196    private IList<PackingPosition> GetEpsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
197      IList<PackingPosition> eps = new List<PackingPosition>();
198      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBelow(binPacking, position);
199      var edges = GetProjectionEdgesBelow(item, position);
200
201      foreach (var i in items) {
202        foreach (var edge in edges) {
203          var newEps = IntersectionsForItem(edge, GetEdgesOnTop(i.Item2, i.Item1));
204          foreach (var ep in newEps) {
205            try {
206              var point = ProjectDown(binPacking, ep);
207              var residualSpace = CalculateResidualSpace(binPacking, point);
208              if (IsNonZero(residualSpace)) {
209                eps.Add(new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
210              }
211            } catch {
212              var s = ep;
213            }
214          }
215        }
216      }
217      return eps;
218    }
219
220    /// <summary>
221    /// Returns the extremepoints on the left side of an given item
222    /// </summary>
223    /// <param name="item"></param>
224    /// <param name="position"></param>
225    /// <returns></returns>
226    private IList<PackingPosition> GetEpsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
227      IList<PackingPosition> eps = new List<PackingPosition>();
228      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBehind(binPacking, position);
229      var edges = GetProjectionEdgesBehind(item, position);
230
231      foreach (var i in items) {
232        foreach (var edge in edges) {
233          var newEps = IntersectionsForItem(edge, GetEdgesInFront(i.Item2, i.Item1));
234          foreach (var ep in newEps) {
235            try {
236              var point = ProjectBackward(binPacking, ep);
237              var residualSpace = CalculateResidualSpace(binPacking, point);
238              if (IsNonZero(residualSpace)) {
239                eps.Add(new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
240              }
241            } catch {
242              var s = ep;
243            }
244          }
245        }
246      }
247      return eps;
248    }
249
250    #region Methods for getting the edges for items
251
252    /// <summary>
253    /// Returns an array of packing position which represents the vertices of an item.
254    /// The position of a vertex in the array is mapped to an item as followed:
255    ///      4----------5
256    ///     /|         /|
257    ///    / |        / |
258    ///   /  0-------/--1
259    ///  6--/-------7  /
260    ///  | /        | /
261    ///  |/         |/
262    ///  2----------3
263    /// 
264    ///  0 = (0,0,0)
265    /// </summary>
266    /// <param name="item"></param>
267    /// <param name="position"></param>
268    /// <returns></returns>
269    private Vector3D[] GetVertices(PackingItem item, PackingPosition position) {
270      int width = position.Rotated ? item.Depth : item.Width;
271      int depth = position.Rotated ? item.Width : item.Depth;
272      return new Vector3D[] {
273        new Vector3D(position.X + 0,     position.Y + 0,           position.Z + 0), // (0,0,0)
274        new Vector3D(position.X + width, position.Y + 0,           position.Z + 0), // (x,0,0)
275        new Vector3D(position.X + 0,     position.Y + 0,           position.Z + depth), // (0,0,z)
276        new Vector3D(position.X + width, position.Y + 0,           position.Z + depth), // (x,0,z)
277
278        new Vector3D(position.X + 0,     position.Y + item.Height, position.Z + 0), // (0,y,0)
279        new Vector3D(position.X + width, position.Y + item.Height, position.Z + 0), // (x,y,0)
280        new Vector3D(position.X + 0,     position.Y + item.Height, position.Z + depth), // (0,y,z)
281        new Vector3D(position.X + width, position.Y + item.Height, position.Z + depth), //(x,y,z)
282      };
283    }
284
285    private Edge3D[] GetProjectionEdgesOnLeft(PackingItem item, PackingPosition position) {
286      Vector3D[] points = GetVertices(item, position);
287
288      return new Edge3D[] {
289        new Edge3D(points[2], points[6]),
290        new Edge3D(points[6], points[4])
291      };
292    }
293
294    private Edge3D[] GetProjectionEdgesBelow(PackingItem item, PackingPosition position) {
295      Vector3D[] points = GetVertices(item, position);
296
297      return new Edge3D[] {
298        new Edge3D(points[2], points[3]),
299        new Edge3D(points[3], points[1])
300      };
301    }
302
303    private Edge3D[] GetProjectionEdgesBehind(PackingItem item, PackingPosition position) {
304      Vector3D[] points = GetVertices(item, position);
305
306      return new Edge3D[] {
307        new Edge3D(points[1], points[5]),
308        new Edge3D(points[5], points[4])
309      };
310    }
311
312    /// <summary>
313    /// Returns an array of edges which contains all edges of the rigth side of an given item.
314    /// </summary>
315    /// <param name="item"></param>
316    /// <param name="position"></param>
317    /// <returns></returns>
318    private Edge3D[] GetEdgesOnRight(PackingItem item, PackingPosition position) {
319      Vector3D[] points = GetVertices(item, position);
320
321      return new Edge3D[] {
322        new Edge3D(points[1], points[5]),
323        new Edge3D(points[5], points[7]),
324        new Edge3D(points[7], points[3]),
325        new Edge3D(points[3], points[1])
326      };
327    }
328
329    /// <summary>
330    /// Returns an array of edges which contains all edges on the top of an given item.
331    /// </summary>
332    /// <param name="item"></param>
333    /// <param name="position"></param>
334    /// <returns></returns>
335    private Edge3D[] GetEdgesOnTop(PackingItem item, PackingPosition position) {
336      Vector3D[] points = GetVertices(item, position);
337
338      return new Edge3D[] {
339        new Edge3D(points[4], points[5]),
340        new Edge3D(points[5], points[7]),
341        new Edge3D(points[7], points[6]),
342        new Edge3D(points[6], points[4])
343      };
344    }
345
346    /// <summary>
347    /// Returns an array of edges which contains all edges in front of an given item.
348    /// </summary>
349    /// <param name="item"></param>
350    /// <param name="position"></param>
351    /// <returns></returns>
352    private Edge3D[] GetEdgesInFront(PackingItem item, PackingPosition position) {
353      Vector3D[] points = GetVertices(item, position);
354
355      return new Edge3D[] {
356        new Edge3D(points[2], points[3]),
357        new Edge3D(points[3], points[7]),
358        new Edge3D(points[7], points[6]),
359        new Edge3D(points[6], points[2])
360      };
361    }
362
363    #endregion
364
365
366    #region Intersections
367
368    /// <summary>
369    /// Returns a list of extreme points.
370    /// </summary>
371    /// <param name="item"></param>
372    /// <param name="position"></param>
373    /// <param name="projectedEdge3D"></param>
374    /// <returns></returns>
375    private IEnumerable<Vector3D> IntersectionsForItem(Edge3D projectedEdge, Edge3D[] edges) {
376      IList<Vector3D> eps = new List<Vector3D>();
377      foreach (var edge in edges) {
378        var ep = edge.Intersects(projectedEdge);
379        if (ep != null) {
380          eps.Add(ep);
381        }
382      }
383      return eps as IEnumerable<Vector3D>;
384    }
385
386
387    #endregion
388
389  }
390}
Note: See TracBrowser for help on using the repository browser.