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

Last change on this file since 15520 was 15520, checked in by rhanghof, 22 months 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: 20.4 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  /// <summary>
12  /// This extreme point creation class uses the line projection based method for creating extreme points.
13  /// This projection method enhances the point based projection method by creating extra extreme points on the intersection points of two items.
14  /// </summary>
15  public class LineProjectionBasedEPCreator : ExtremePointCreator {
16
17
18
19
20    protected override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
21      // After a item has been placed, the residual space has to be recalculated.
22      //RecalculateResidualSpaces(binPacking);
23
24      //GenerateNewExtremePointsForItem(binPacking, item, position);
25
26      binPacking.ExtremePoints.Clear();
27      binPacking.ResidualSpaces.Clear();
28
29      foreach (var i in binPacking.Items) {
30        PackingItem it = i.Value;
31        PackingPosition p = binPacking.Positions[i.Key];
32        GenerateNewExtremePointsForItem(binPacking, it, p);
33      }
34      //RecalculateResidualSpaces(binPacking);
35    }
36
37    /// <summary>
38    /// Adds an new extreme point an the related residual space to a given bin packing.
39    /// - The given position has to be valid
40    /// - The residual space must not be zero
41    /// </summary>
42    /// <param name="binPacking"></param>
43    /// <param name="position"></param>
44    /// <returns></returns>
45    protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
46      if (position == null) {
47        return false;
48      }
49
50      if (PointIsInItem(binPacking, new Vector3D(position))) {
51        return false;
52      }
53
54      var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
55
56      if (rs.IsZero()) {
57        return false;
58      }
59
60      if (!binPacking.ExtremePoints.Add(position)) {
61        return false;
62      }
63
64      binPacking.ResidualSpaces.Add(position, rs);
65      return true;
66    }
67
68    /// <summary>
69    /// Getnerates the extreme points for a given item.
70    /// It creates extreme points by using a point projection based method and
71    /// creates points by using an edge projection based method.
72    /// </summary>
73    /// <param name="binPacking"></param>
74    /// <param name="newItem"></param>
75    /// <param name="position"></param>
76    protected override void GenerateNewExtremePointsForItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
77      PointProjectionForNewItem(binPacking, newItem, position);
78      EdgeProjectionForNewItem(binPacking, newItem, position);
79    }
80
81    #region Extreme point creation by using a point projection based method
82
83    /// <summary>
84    /// This method creates extreme points by using a point projection based method.
85    /// For each item there will be three points created and each of the point will be projected twice.
86    /// The direction of the projection depends on position of the point.
87    /// </summary>
88    /// <param name="binPacking"></param>
89    /// <param name="newItem"></param>
90    /// <param name="position"></param>
91    private void PointProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
92      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
93      int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
94      var binShape = binPacking.BinShape;
95      var sourcePoint = new PackingPosition(position.AssignedBin, position.X + newWidth, position.Y, position.Z);
96      PointProjection(binPacking, sourcePoint, ProjectDown);
97      PointProjection(binPacking, sourcePoint, ProjectBackward);
98
99      sourcePoint = new PackingPosition(position.AssignedBin, position.X, position.Y + newItem.Height, position.Z);
100      PointProjection(binPacking, sourcePoint, ProjectLeft);
101      PointProjection(binPacking, sourcePoint, ProjectBackward);
102
103      sourcePoint = new PackingPosition(position.AssignedBin, position.X, position.Y, position.Z + newDepth);
104      PointProjection(binPacking, sourcePoint, ProjectDown);
105      PointProjection(binPacking, sourcePoint, ProjectLeft);
106    }
107
108
109    /// <summary>
110    /// Projects a given point by using the given projection method to the neares item.
111    /// The given projection method returns a point which lies on a side of the nearest item in the direction.
112    /// </summary>
113    /// <param name="binPacking"></param>
114    /// <param name="position"></param>
115    /// <param name="projectionMethod"></param>
116    private void PointProjection(BinPacking3D binPacking, PackingPosition position, Func<BinPacking3D, Vector3D, Vector3D> projectionMethod) {
117      Vector3D sourcePoint = new Vector3D(position);
118      if (sourcePoint.X < binPacking.BinShape.Width && sourcePoint.Y < binPacking.BinShape.Height && sourcePoint.Z < binPacking.BinShape.Depth) {
119        Vector3D point = projectionMethod?.Invoke(binPacking, sourcePoint);
120        AddExtremePoint(binPacking, new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
121      }
122    }
123    #endregion
124
125    #region Extreme point creation by using an edge projection based method
126
127    /// <summary>
128    /// This method creates extreme points be projecting the edges of a given item
129    ///   - left
130    ///   - back
131    ///   - down.
132    /// A extreme point will be created, if an edge instersects with an edge of another item.
133    /// </summary>
134    /// <param name="binPacking"></param>
135    /// <param name="newItem"></param>
136    /// <param name="position"></param>
137    private void EdgeProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
138      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
139      int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
140      var binShape = binPacking.BinShape;
141
142      foreach (var ep in GetEpsOnLeft(binPacking, newItem, position)) {
143        AddExtremePoint(binPacking, ep);
144      }
145
146      foreach (var ep in GetEpsBelow(binPacking, newItem, position)) {
147        AddExtremePoint(binPacking, ep);
148      }
149
150      foreach (var ep in GetEpsBehind(binPacking, newItem, position)) {
151        AddExtremePoint(binPacking, ep);
152      }
153    }
154    #endregion
155
156
157    protected override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
158      return;
159    }
160
161    private bool PointIsInItem(BinPacking3D binPacking, Vector3D point) {
162      foreach (var item in binPacking.Items) {
163        PackingPosition position = binPacking.Positions[item.Key];
164        var depth = position.Rotated ? item.Value.Width : item.Value.Depth;
165        var width = position.Rotated ? item.Value.Depth : item.Value.Width;
166        if (position.X <= point.X && point.X < position.X + width &&
167            position.Y <= point.Y && point.Y < position.Y + item.Value.Height &&
168            position.Z <= point.Z && point.Z < position.Z + depth) {
169          return true;
170        }
171      }
172      return false;
173    }
174
175    /// <summary>
176    /// Returns true if an item is in the residual space of a given extrem point
177    /// </summary>
178    /// <param name="rs">KeyValuePair with the position of the extreme point and the size of the residual space</param>
179    /// <param name="item">Given Item</param>
180    /// <param name="position">Given position</param>
181    /// <returns></returns>
182    private bool ItemIsInRs(KeyValuePair<PackingPosition, ResidualSpace> rs, PackingItem item, PackingPosition position) {
183      return GetVertices(item, position).Where(pos => pos.IsInside(rs.Key, rs.Value)).Any();
184    }
185
186    /// <summary>
187    /// Recalculates the residual spaces if needed.
188    /// It checks if an item is in an residual space and if so the residual space will be recalculated.
189    /// If the residual space has gone to zero, this residual space and its related extreme point will be removed.
190    /// </summary>
191    /// <param name="binPacking"></param>
192    private void RecalculateResidualSpaces(BinPacking3D binPacking) {
193      var recalculatedSpaces = new Dictionary<PackingPosition, ResidualSpace>();
194      foreach (var ep in binPacking.ExtremePoints.ToList()) {
195        var newRs = CalculateResidualSpace(binPacking, new Vector3D(ep));
196        if (!newRs.IsZero() && !PointIsInItem(binPacking, new Vector3D(ep))) {
197          recalculatedSpaces.Add(ep, newRs);
198        } else {
199          binPacking.ExtremePoints.Remove(ep);
200        }
201      }
202      binPacking.ResidualSpaces = recalculatedSpaces;
203    }
204
205    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
206      return binPacking.Items.Select(x => new {
207        Item = x.Value,
208        Position = binPacking.Positions[x.Key]
209      }).Where(x => x.Position.Y < position.Y)
210          .Select(x => Tuple.Create(x.Position, x.Item));
211    }
212
213    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
214      return binPacking.Items.Select(x => new {
215        Item = x.Value,
216        Position = binPacking.Positions[x.Key]
217      }).Where(x => x.Position.Z < position.Z)
218          .Select(x => Tuple.Create(x.Position, x.Item));
219    }
220
221    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
222      return binPacking.Items.Select(x => new {
223        Item = x.Value,
224        Position = binPacking.Positions[x.Key]
225      }).Where(x => x.Position.X < position.X)
226          .Select(x => Tuple.Create(x.Position, x.Item));
227    }
228
229    /// <summary>
230    /// Returns the extremepoints on the left side of an given item
231    /// </summary>
232    /// <param name="item"></param>
233    /// <param name="position"></param>
234    /// <returns></returns>
235    private IList<PackingPosition> GetEpsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
236      IList<PackingPosition> eps = new List<PackingPosition>();
237      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsOnLeft(binPacking, item, position);
238      var edges = GetProjectionEdgesOnLeft(item, position);
239
240      foreach (var otherItem in items) {
241        var otherItemEdges = GetEdgesOnRight(otherItem.Item2, otherItem.Item1);
242        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(1, 0, 0))) {
243          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
244            var point = ProjectDown(binPacking, ProjectLeft(binPacking, ep));
245            var residualSpace = CalculateResidualSpace(binPacking, point);
246            if (!residualSpace.IsZero()) {
247              eps.Add(point.ToPackingPosition(position.AssignedBin));
248            }
249          }
250        }
251        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(1, 0, 0))) {
252          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
253            var point = ProjectLeft(binPacking, ep);
254            var residualSpace = CalculateResidualSpace(binPacking, point);
255            if (!residualSpace.IsZero()) {
256              eps.Add(point.ToPackingPosition(position.AssignedBin));
257            }
258          }
259        }
260      }
261      return eps;
262    }
263
264
265    /// <summary>
266    /// Returns the extremepoints below of an given item
267    /// </summary>
268    /// <param name="item"></param>
269    /// <param name="position"></param>
270    /// <returns></returns>
271    private IList<PackingPosition> GetEpsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
272      IList<PackingPosition> eps = new List<PackingPosition>();
273      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBelow(binPacking, position);
274      var edges = GetProjectionEdgesBelow(item, position);
275
276      foreach (var otherItem in items) {
277        var otherItemEdges = GetEdgesOnTop(otherItem.Item2, otherItem.Item1);
278        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 1, 0))) {
279          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
280            var point = ProjectDown(binPacking, ep);
281            var residualSpace = CalculateResidualSpace(binPacking, point);
282            if (!residualSpace.IsZero()) {
283              eps.Add(point.ToPackingPosition(position.AssignedBin));
284            }
285          }
286        }
287        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 1, 0))) {
288          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
289            var point = ProjectDown(binPacking, ep);
290            var residualSpace = CalculateResidualSpace(binPacking, point);
291            if (!residualSpace.IsZero()) {
292              eps.Add(point.ToPackingPosition(position.AssignedBin));
293            }
294          }
295        }
296      }
297      return eps;
298    }
299
300    /// <summary>
301    /// Returns
302    /// </summary>
303    /// <param name="item"></param>
304    /// <param name="position"></param>
305    /// <returns></returns>
306    private IList<PackingPosition> GetEpsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
307      IList<PackingPosition> eps = new List<PackingPosition>();
308      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBehind(binPacking, position);
309      var edges = GetProjectionEdgesBehind(item, position);
310
311      foreach (var otherItem in items) {
312        var otherItemEdges = GetEdgesInFront(otherItem.Item2, otherItem.Item1);
313        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 0, 1))) {
314          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
315            var point = ProjectDown(binPacking, ProjectBackward(binPacking, ep));
316            var residualSpace = CalculateResidualSpace(binPacking, point);
317            if (!residualSpace.IsZero()) {
318              eps.Add(point.ToPackingPosition(position.AssignedBin));
319            }
320          }
321        }
322        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 0, 1))) {
323          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
324            var point = ProjectBackward(binPacking, ep);
325            var residualSpace = CalculateResidualSpace(binPacking, point);
326            if (!residualSpace.IsZero()) {
327              eps.Add(point.ToPackingPosition(position.AssignedBin));
328            }
329          }
330        }
331      }
332      return eps;
333    }
334
335    #region Methods for getting the edges for items
336
337    /// <summary>
338    /// Returns an array of packing position which represents the vertices of an item.
339    /// The position of a vertex in the array is mapped to an item as followed:
340    ///      4----------5
341    ///     /|         /|
342    ///    / |        / |
343    ///   /  0-------/--1
344    ///  6--/-------7  /
345    ///  | /        | /
346    ///  |/         |/
347    ///  2----------3
348    /// 
349    ///  0 = (0,0,0)
350    /// </summary>
351    /// <param name="item"></param>
352    /// <param name="position"></param>
353    /// <returns></returns>
354    private Vector3D[] GetVertices(PackingItem item, PackingPosition position) {
355      int width = position.Rotated ? item.Depth : item.Width;
356      int depth = position.Rotated ? item.Width : item.Depth;
357      return new Vector3D[] {
358        new Vector3D(position.X + 0,     position.Y + 0,           position.Z + 0), // (0,0,0)
359        new Vector3D(position.X + width, position.Y + 0,           position.Z + 0), // (x,0,0)
360        new Vector3D(position.X + 0,     position.Y + 0,           position.Z + depth), // (0,0,z)
361        new Vector3D(position.X + width, position.Y + 0,           position.Z + depth), // (x,0,z)
362
363        new Vector3D(position.X + 0,     position.Y + item.Height, position.Z + 0), // (0,y,0)
364        new Vector3D(position.X + width, position.Y + item.Height, position.Z + 0), // (x,y,0)
365        new Vector3D(position.X + 0,     position.Y + item.Height, position.Z + depth), // (0,y,z)
366        new Vector3D(position.X + width, position.Y + item.Height, position.Z + depth), //(x,y,z)
367      };
368    }
369
370    private Edge3D[] GetProjectionEdgesOnLeft(PackingItem item, PackingPosition position) {
371      Vector3D[] points = GetVertices(item, position);
372
373      return new Edge3D[] {
374        new Edge3D(points[2], points[6]),
375        new Edge3D(points[6], points[4])
376      };
377    }
378
379    private Edge3D[] GetProjectionEdgesBelow(PackingItem item, PackingPosition position) {
380      Vector3D[] points = GetVertices(item, position);
381
382      return new Edge3D[] {
383        new Edge3D(points[2], points[3]),
384        new Edge3D(points[3], points[1])
385      };
386    }
387
388    private Edge3D[] GetProjectionEdgesBehind(PackingItem item, PackingPosition position) {
389      Vector3D[] points = GetVertices(item, position);
390
391      return new Edge3D[] {
392        new Edge3D(points[1], points[5]),
393        new Edge3D(points[5], points[4])
394      };
395    }
396
397    /// <summary>
398    /// Returns an array of edges which contains all edges of the rigth side of an given item.
399    /// </summary>
400    /// <param name="item"></param>
401    /// <param name="position"></param>
402    /// <returns></returns>
403    private Edge3D[] GetEdgesOnRight(PackingItem item, PackingPosition position) {
404      Vector3D[] points = GetVertices(item, position);
405
406      return new Edge3D[] {
407        new Edge3D(points[1], points[5]),
408        new Edge3D(points[5], points[7]),
409        new Edge3D(points[7], points[3]),
410        new Edge3D(points[3], points[1])
411      };
412    }
413
414    /// <summary>
415    /// Returns an array of edges which contains all edges on the top of an given item.
416    /// </summary>
417    /// <param name="item"></param>
418    /// <param name="position"></param>
419    /// <returns></returns>
420    private Edge3D[] GetEdgesOnTop(PackingItem item, PackingPosition position) {
421      Vector3D[] points = GetVertices(item, position);
422
423      return new Edge3D[] {
424        new Edge3D(points[4], points[5]),
425        new Edge3D(points[5], points[7]),
426        new Edge3D(points[7], points[6]),
427        new Edge3D(points[6], points[4])
428      };
429    }
430
431    /// <summary>
432    /// Returns an array of edges which contains all edges in front of an given item.
433    /// </summary>
434    /// <param name="item"></param>
435    /// <param name="position"></param>
436    /// <returns></returns>
437    private Edge3D[] GetEdgesInFront(PackingItem item, PackingPosition position) {
438      Vector3D[] points = GetVertices(item, position);
439
440      return new Edge3D[] {
441        new Edge3D(points[2], points[3]),
442        new Edge3D(points[3], points[7]),
443        new Edge3D(points[7], points[6]),
444        new Edge3D(points[6], points[2])
445      };
446    }
447
448    #endregion
449
450
451    #region Intersections
452
453    /// <summary>
454    ///
455    /// </summary>
456    /// <param name="projectedEdge"></param>
457    /// <param name="edges"></param>
458    /// <returns></returns>
459    private IEnumerable<Vector3D> IntersectionsForItem(Edge3D projectedEdge, Edge3D[] edges, Vector3D direction = null) {
460      IList<Vector3D> eps = new List<Vector3D>();
461      foreach (var edge in edges) {
462        Edge3D e = projectedEdge;
463        if (direction != null) {
464          if (direction.X != 0) {
465            e.Start.X = edge.Start.X;
466            e.End.X = edge.End.X;
467          } else if (direction.Y != 0) {
468            e.Start.Y = edge.Start.Y;
469            e.End.Y = edge.End.Y;
470          } else if (direction.Z != 0) {
471            e.Start.Z = edge.Start.Z;
472            e.End.Z = edge.End.Z;
473          }
474        }
475
476        var ep = edge.Intersects(e);
477        if (ep != null) {
478          eps.Add(ep);
479        }
480      }
481      return eps as IEnumerable<Vector3D>;
482    }
483
484
485
486    #endregion
487
488   
489    protected override ResidualSpace CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
490      return ResidualSpaceCalculatorFactory.CreateCalculator().CalculateResidualSpaces(binPacking, pos).First();
491    }
492  }
493
494 
495}
Note: See TracBrowser for help on using the repository browser.