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

Last change on this file since 15705 was 15705, checked in by rhanghof, 3 years ago

#2817

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