source: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/LineProjectionBasedEPCreator.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: 25.6 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    protected override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
18      binPacking.ExtremePoints.Clear();
19
20      foreach (var i in binPacking.Items) {
21        PackingItem it = i.Value;
22        PackingPosition p = binPacking.Positions[i.Key];
23        GenerateNewExtremePointsForItem(binPacking, it, p);
24      }
25     
26      // remove not needed extreme points.
27      foreach (var extremePoint in binPacking.ExtremePoints.ToList()) {
28        // check if a residual space can be removed
29        foreach (var rs in extremePoint.Value.ToList()) {
30          if (ResidualSpaceCanBeRemoved(binPacking, extremePoint.Key, rs)) {
31            ((IList<ResidualSpace>)extremePoint.Value).Remove(rs);
32          }
33        }
34        // if the current extreme point has no more residual spaces, it can be removed.
35        if (((IList<ResidualSpace>)extremePoint.Value).Count <= 0) {
36          binPacking.ExtremePoints.Remove(extremePoint);
37        }
38      }
39    }
40   
41    /// <summary>
42    /// Returns true if a given residual space can be removed.
43    /// The given residual space can be removed if it is within another residual space and
44    /// - neither the position of the other residual space and the current extreme point have an item below or
45    /// - the current extreme point has an item below.
46    /// </summary>
47    /// <param name="binPacking"></param>
48    /// <param name="position"></param>
49    /// <param name="rs"></param>
50    /// <returns></returns>
51    private bool ResidualSpaceCanBeRemoved(BinPacking3D binPacking, PackingPosition position, ResidualSpace rs) {
52      foreach (var extremePoint in binPacking.ExtremePoints) {
53        if (position.Equals(extremePoint.Key)) {
54          continue;
55        }
56        if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(position), rs, extremePoint.Key, extremePoint.Value)) {
57          var itemBelowEp = LiesOnAnyItem(binPacking, extremePoint.Key);
58          var itemBelowPos = LiesOnAnyItem(binPacking, position);
59
60          if (itemBelowEp || !itemBelowEp && !itemBelowPos) {
61            return true;
62          }         
63        }
64      }
65      return false;
66    }
67   
68    /// <summary>
69    /// Returns true if the given position lies on an item or an the ground.
70    /// </summary>
71    /// <param name="binPacking"></param>
72    /// <param name="position"></param>
73    /// <returns></returns>
74    private bool LiesOnAnyItem(BinPacking3D binPacking, PackingPosition position) {
75      if (position.Y == 0) {
76        return true;
77      }
78
79      var items = binPacking.Items.Where(x => {
80        var itemPosition = binPacking.Positions[x.Key];
81        var item = x.Value;
82        int width = itemPosition.Rotated ? item.Depth : item.Width;
83        int depth = itemPosition.Rotated ? item.Width : item.Depth;
84
85        return itemPosition.Y + item.Height == position.Y &&
86               itemPosition.X <= position.X && position.X < itemPosition.X + width &&
87               itemPosition.Z <= position.Z && position.Z < itemPosition.Z + depth;
88      });
89
90      return items.Count() > 0;
91    }
92
93
94    /// <summary>
95    /// Adds a new extreme point an the related residual spaces to a given bin packing.
96    /// - The given position has to be valid.
97    /// - The extreme point does not exist in the bin packing.
98    /// - There must be at minimum one valid residual space. A residual space is invalid if the space is zero.
99    /// </summary>
100    /// <param name="binPacking"></param>
101    /// <param name="position"></param>
102    /// <returns>True = the given point and its related residual spaces were successfully added to the bin packing</returns>
103    protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
104      if (position == null) {
105        return false;
106      }
107
108      if (PointIsInAnyItem(binPacking, new Vector3D(position))) {
109        return false;
110      }
111
112      if (binPacking.ExtremePoints.ContainsKey(position)) {
113        return false;
114      }
115
116      var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
117
118      if (rs.Count() <= 0) {
119        return false;
120      }
121
122      binPacking.ExtremePoints.Add(position, rs);
123      return true;
124    }
125
126    /// <summary>
127    /// Getnerates the extreme points for a given item.
128    /// It creates extreme points by using a point projection based method and
129    /// creates points by using an edge projection based method.
130    /// </summary>
131    /// <param name="binPacking"></param>
132    /// <param name="newItem"></param>
133    /// <param name="position"></param>
134    protected override void GenerateNewExtremePointsForItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
135      PointProjectionForNewItem(binPacking, newItem, position);
136      EdgeProjectionForNewItem(binPacking, newItem, position);
137    }
138
139    #region Extreme point creation by using a point projection based method
140
141    /// <summary>
142    /// This method creates extreme points by using a point projection based method.
143    /// For each item there will be created three points and each of the points will be projected twice.
144    /// The direction of the projection depends on position of the point.
145    /// </summary>
146    /// <param name="binPacking"></param>
147    /// <param name="newItem"></param>
148    /// <param name="position"></param>
149    private void PointProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
150      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
151      int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
152      var binShape = binPacking.BinShape;
153      var sourcePoint = new PackingPosition(position.AssignedBin, position.X + newWidth, position.Y, position.Z);
154      PointProjection(binPacking, sourcePoint, ProjectDown);
155      PointProjection(binPacking, sourcePoint, ProjectBackward);
156
157      sourcePoint = new PackingPosition(position.AssignedBin, position.X, position.Y + newItem.Height, position.Z);
158      PointProjection(binPacking, sourcePoint, ProjectLeft);
159      PointProjection(binPacking, sourcePoint, ProjectBackward);
160
161      sourcePoint = new PackingPosition(position.AssignedBin, position.X, position.Y, position.Z + newDepth);
162      PointProjection(binPacking, sourcePoint, ProjectDown);
163      PointProjection(binPacking, sourcePoint, ProjectLeft);
164    }
165
166
167    /// <summary>
168    /// Projects a given point by using the given projection method to the neares item.
169    /// The given projection method returns a point which lies on a side of the nearest item in the direction.
170    /// </summary>
171    /// <param name="binPacking"></param>
172    /// <param name="position"></param>
173    /// <param name="projectionMethod"></param>
174    private void PointProjection(BinPacking3D binPacking, PackingPosition position, Func<BinPacking3D, Vector3D, Vector3D> projectionMethod) {
175      Vector3D sourcePoint = new Vector3D(position);
176      if (sourcePoint.X < binPacking.BinShape.Width && sourcePoint.Y < binPacking.BinShape.Height && sourcePoint.Z < binPacking.BinShape.Depth) {
177        Vector3D point = projectionMethod?.Invoke(binPacking, sourcePoint);
178        if (point != null) {
179          AddExtremePoint(binPacking, new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
180        }
181      }
182    }
183    #endregion
184
185    #region Extreme point creation by using an edge projection based method
186
187    /// <summary>
188    /// This method creates extreme points be projecting the edges of a given item
189    ///   - left
190    ///   - back
191    ///   - down.
192    /// A extreme point will be created, if an edge instersects with an edge of another item.
193    /// </summary>
194    /// <param name="binPacking"></param>
195    /// <param name="newItem"></param>
196    /// <param name="position"></param>
197    private void EdgeProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
198      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
199      int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
200      var binShape = binPacking.BinShape;
201
202      foreach (var ep in GetEpsOnLeft(binPacking, newItem, position)) {
203        AddExtremePoint(binPacking, ep.Key);
204      }
205
206      foreach (var ep in GetEpsBelow(binPacking, newItem, position)) {
207        AddExtremePoint(binPacking, ep.Key);
208      }
209
210      foreach (var ep in GetEpsBehind(binPacking, newItem, position)) {
211        AddExtremePoint(binPacking, ep.Key);
212      }
213    }
214    #endregion
215
216    /// <summary>
217    /// Updates the residual spaces.
218    /// It removes not needed ones.
219    /// A residual space will be removed if the space is a subspace of another one and
220    /// the current one has no item below or both have an item below.
221    /// </summary>
222    /// <param name="binPacking"></param>
223    /// <param name="item"></param>
224    /// <param name="position"></param>
225    protected override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
226    }
227
228    /// <summary>
229    /// Returns true if any item in the bin packing encapsulates the given point
230    /// </summary>
231    /// <param name="binPacking"></param>
232    /// <param name="point"></param>
233    /// <returns></returns>
234    private bool PointIsInAnyItem(BinPacking3D binPacking, Vector3D point) {
235      foreach (var item in binPacking.Items) {
236        PackingPosition position = binPacking.Positions[item.Key];
237        var depth = position.Rotated ? item.Value.Width : item.Value.Depth;
238        var width = position.Rotated ? item.Value.Depth : item.Value.Width;
239        if (position.X <= point.X && point.X < position.X + width &&
240            position.Y <= point.Y && point.Y < position.Y + item.Value.Height &&
241            position.Z <= point.Z && point.Z < position.Z + depth) {
242          return true;
243        }
244      }
245      return false;
246    }
247
248    /// <summary>
249    /// Returns true if an item is in the residual space of a given extrem point
250    /// </summary>
251    /// <param name="rs">KeyValuePair with the position of the extreme point and the size of the residual space</param>
252    /// <param name="item">Given Item</param>
253    /// <param name="position">Given position</param>
254    /// <returns></returns>
255    private bool ItemIsInRs(KeyValuePair<PackingPosition, ResidualSpace> rs, PackingItem item, PackingPosition position) {
256      return GetVertices(item, position).Where(pos => pos.IsInside(rs.Key, rs.Value)).Any();
257    }
258
259    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
260      return binPacking.Items.Select(x => new {
261        Item = x.Value,
262        Position = binPacking.Positions[x.Key]
263      }).Where(x => x.Position.Y < position.Y)
264          .Select(x => Tuple.Create(x.Position, x.Item));
265    }
266
267    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
268      return binPacking.Items.Select(x => new {
269        Item = x.Value,
270        Position = binPacking.Positions[x.Key]
271      }).Where(x => x.Position.Z < position.Z)
272          .Select(x => Tuple.Create(x.Position, x.Item));
273    }
274
275    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
276      return binPacking.Items.Select(x => new {
277        Item = x.Value,
278        Position = binPacking.Positions[x.Key]
279      }).Where(x => x.Position.X < position.X)
280          .Select(x => Tuple.Create(x.Position, x.Item));
281    }
282
283    /// <summary>
284    /// Returns the extreme points and its related residual spaces on the left side of an given item.
285    /// This extreme points are being created by intersecting two edges on the left side of the given item
286    /// (left - in front, left - on top) with all edges on the right side of all other items int the bin packing.
287    /// </summary>
288    /// <param name="item"></param>
289    /// <param name="position"></param>
290    /// <returns></returns>
291    private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
292      var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
293      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsOnLeft(binPacking, item, position);
294      var edges = GetProjectionEdgesOnLeft(item, position);
295
296      foreach (var otherItem in items) {
297        if (position.Equals(otherItem.Item1)) {
298          continue;
299        }
300
301        var otherItemEdges = GetEdgesOnRight(otherItem.Item2, otherItem.Item1);
302        // left - in front
303        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(1, 0, 0))) {
304          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
305            // As this edge has a vertical direction, every point of intersection won't have an item below.
306            // So finally it is being projected down.
307            var point = ProjectDown(binPacking, ProjectLeft(binPacking, ep));
308            var residualSpaces = CalculateResidualSpace(binPacking, point);
309            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
310            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
311              eps.Add(newExtremePoint, residualSpaces);
312            }
313          }
314        }
315
316        // left - on top
317        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(1, 0, 0))) {
318          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
319            var point = ProjectLeft(binPacking, ep);
320            var residualSpaces = CalculateResidualSpace(binPacking, point);
321            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
322            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
323              eps.Add(newExtremePoint, residualSpaces);
324            }
325          }
326        }
327      }
328      return eps;
329    }
330
331
332    /// <summary>
333    /// Returns the extreme points and its related residual spaces below of an given item.
334    /// This extreme points are being created by intersecting two edges below of the given item
335    /// (below - in front, below - right) with all edges on top side of all other items int the bin packing.
336    /// </summary>
337    /// <param name="item"></param>
338    /// <param name="position"></param>
339    /// <returns></returns>
340    private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
341      var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
342      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBelow(binPacking, position);
343      var edges = GetProjectionEdgesBelow(item, position);
344
345      foreach (var otherItem in items) {
346        if (position.Equals(otherItem.Item1)) {
347          continue;
348        }
349
350        var otherItemEdges = GetEdgesOnTop(otherItem.Item2, otherItem.Item1);
351        // below - in front
352        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 1, 0))) {
353          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
354            var point = ProjectDown(binPacking, ep);
355            var residualSpaces = CalculateResidualSpace(binPacking, point);
356            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
357            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
358              eps.Add(newExtremePoint, residualSpaces);
359            }
360          }
361        }
362
363        // below - right
364        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 1, 0))) {
365          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
366            var point = ProjectDown(binPacking, ep);
367            var residualSpaces = CalculateResidualSpace(binPacking, point);
368            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
369            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
370              eps.Add(newExtremePoint, residualSpaces);
371            }
372          }
373        }
374      }
375      return eps;
376    }
377
378    /// <summary>
379    /// Returns the extreme points and its related residual spaces below of an given item.
380    /// This extreme points are being created by intersecting two edges below of the given item
381    /// (right - behind, on top - behind) with all edges on top side of all other items int the bin packing.
382    /// </summary>
383    /// <param name="item"></param>
384    /// <param name="position"></param>
385    /// <returns></returns>
386    private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
387      var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
388      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBehind(binPacking, position);
389      var edges = GetProjectionEdgesBehind(item, position);
390
391      foreach (var otherItem in items) {
392        if (position.Equals(otherItem.Item1)) {
393          continue;
394        }
395
396        var otherItemEdges = GetEdgesInFront(otherItem.Item2, otherItem.Item1);
397        // right - behind
398        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 0, 1))) {
399          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
400            // As this edge has a vertical direction, every point of intersection won't have an item below.
401            // So finally it is being projected down.
402            var point = ProjectDown(binPacking, ProjectBackward(binPacking, ep));
403            var residualSpaces = CalculateResidualSpace(binPacking, point);
404            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
405            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
406              eps.Add(newExtremePoint, residualSpaces);
407            }
408          }
409        }
410
411        // on top - behind
412        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 0, 1))) {
413          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
414            var point = ProjectBackward(binPacking, ep);
415            var residualSpaces = CalculateResidualSpace(binPacking, point);
416            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
417            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
418              eps.Add(newExtremePoint, residualSpaces);
419            }
420          }
421        }
422      }
423      return eps;
424    }
425
426    #region Methods for getting the edges for items
427
428    /// <summary>
429    /// Returns an array of packing position which represents the vertices of an item.
430    /// The position of a vertex in the array is mapped to an item as followed:
431    ///      4----------5
432    ///     /|         /|
433    ///    / |        / |
434    ///   /  0-------/--1
435    ///  6--/-------7  /
436    ///  | /        | /
437    ///  |/         |/
438    ///  2----------3
439    /// 
440    ///  0 = (0,0,0)
441    /// </summary>
442    /// <param name="item"></param>
443    /// <param name="position"></param>
444    /// <returns></returns>
445    private Vector3D[] GetVertices(PackingItem item, PackingPosition position) {
446      int width = position.Rotated ? item.Depth : item.Width;
447      int depth = position.Rotated ? item.Width : item.Depth;
448      return new Vector3D[] {
449        new Vector3D(position.X + 0,     position.Y + 0,           position.Z + 0), // (0,0,0)
450        new Vector3D(position.X + width, position.Y + 0,           position.Z + 0), // (x,0,0)
451        new Vector3D(position.X + 0,     position.Y + 0,           position.Z + depth), // (0,0,z)
452        new Vector3D(position.X + width, position.Y + 0,           position.Z + depth), // (x,0,z)
453
454        new Vector3D(position.X + 0,     position.Y + item.Height, position.Z + 0), // (0,y,0)
455        new Vector3D(position.X + width, position.Y + item.Height, position.Z + 0), // (x,y,0)
456        new Vector3D(position.X + 0,     position.Y + item.Height, position.Z + depth), // (0,y,z)
457        new Vector3D(position.X + width, position.Y + item.Height, position.Z + depth), //(x,y,z)
458      };
459    }
460
461    private Edge3D[] GetProjectionEdgesOnLeft(PackingItem item, PackingPosition position) {
462      Vector3D[] points = GetVertices(item, position);
463
464      return new Edge3D[] {
465        new Edge3D(points[2], points[6]),
466        new Edge3D(points[6], points[4])
467      };
468    }
469
470    private Edge3D[] GetProjectionEdgesBelow(PackingItem item, PackingPosition position) {
471      Vector3D[] points = GetVertices(item, position);
472
473      return new Edge3D[] {
474        new Edge3D(points[2], points[3]),
475        new Edge3D(points[3], points[1])
476      };
477    }
478
479    private Edge3D[] GetProjectionEdgesBehind(PackingItem item, PackingPosition position) {
480      Vector3D[] points = GetVertices(item, position);
481
482      return new Edge3D[] {
483        new Edge3D(points[1], points[5]),
484        new Edge3D(points[5], points[4])
485      };
486    }
487
488    /// <summary>
489    /// Returns an array of edges which contains all edges of the rigth side of an given item.
490    /// </summary>
491    /// <param name="item"></param>
492    /// <param name="position"></param>
493    /// <returns></returns>
494    private Edge3D[] GetEdgesOnRight(PackingItem item, PackingPosition position) {
495      Vector3D[] points = GetVertices(item, position);
496
497      return new Edge3D[] {
498        new Edge3D(points[1], points[5]),
499        new Edge3D(points[5], points[7]),
500        new Edge3D(points[7], points[3]),
501        new Edge3D(points[3], points[1])
502      };
503    }
504
505    /// <summary>
506    /// Returns an array of edges which contains all edges on the top of an given item.
507    /// </summary>
508    /// <param name="item"></param>
509    /// <param name="position"></param>
510    /// <returns></returns>
511    private Edge3D[] GetEdgesOnTop(PackingItem item, PackingPosition position) {
512      Vector3D[] points = GetVertices(item, position);
513
514      return new Edge3D[] {
515        new Edge3D(points[4], points[5]),
516        new Edge3D(points[5], points[7]),
517        new Edge3D(points[7], points[6]),
518        new Edge3D(points[6], points[4])
519      };
520    }
521
522    /// <summary>
523    /// Returns an array of edges which contains all edges in front of an given item.
524    /// </summary>
525    /// <param name="item"></param>
526    /// <param name="position"></param>
527    /// <returns></returns>
528    private Edge3D[] GetEdgesInFront(PackingItem item, PackingPosition position) {
529      Vector3D[] points = GetVertices(item, position);
530
531      return new Edge3D[] {
532        new Edge3D(points[2], points[3]),
533        new Edge3D(points[3], points[7]),
534        new Edge3D(points[7], points[6]),
535        new Edge3D(points[6], points[2])
536      };
537    }
538
539    #endregion
540
541
542    #region Intersections
543
544    /// <summary>
545    /// Returns a collection of points where a given edge (projectedEdge) intersects with other edges.
546    /// The given edge (projectedEdge) will be projected by using the given vector direction
547    /// and a edge of the given edge collection.
548    /// The returned collecten can be empty.
549    /// </summary>
550    /// <param name="projectedEdge"></param>
551    /// <param name="edges"></param>
552    /// <param name="direction"></param>
553    /// <returns></returns>
554    private IEnumerable<Vector3D> IntersectionsForItem(Edge3D projectedEdge, Edge3D[] edges, Vector3D direction = null) {
555      IList<Vector3D> eps = new List<Vector3D>();
556      foreach (var edge in edges) {
557        Edge3D e = projectedEdge;
558        if (direction != null) {
559          if (direction.X != 0) {
560            e.Start.X = edge.Start.X;
561            e.End.X = edge.End.X;
562          } else if (direction.Y != 0) {
563            e.Start.Y = edge.Start.Y;
564            e.End.Y = edge.End.Y;
565          } else if (direction.Z != 0) {
566            e.Start.Z = edge.Start.Z;
567            e.End.Z = edge.End.Z;
568          }
569        }
570
571        var ep = edge.Intersects(e);
572        if (ep != null) {
573          eps.Add(ep);
574        }
575      }
576      return eps as IEnumerable<Vector3D>;
577    }
578
579
580
581    #endregion
582
583    /// <summary>
584    /// Calculates the residual spaces for an extreme point.
585    /// </summary>
586    /// <param name="binPacking"></param>
587    /// <param name="pos"></param>
588    /// <returns></returns>
589    protected override IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
590      return ResidualSpaceCalculatorFactory.CreateCalculator().CalculateResidualSpaces(binPacking, pos);
591    }
592  }
593
594
595}
Note: See TracBrowser for help on using the repository browser.