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

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

#2817:

  • The items can be rotated and tilted now.
  • Added pruning of extreme points in packed bins.
  • Added new packer which packs items by positioning them on the point with the minimum of wasted space. He uses rotating and tilting of items.
  • Added classes for sorting given items.
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;
30using System.Collections.Concurrent;
31
32namespace HeuristicLab.Problems.BinPacking3D.ExtremePointCreation {
33  /// <summary>
34  /// This extreme point creation class uses the line projection based method for creating extreme points.
35  /// This projection method enhances the point based projection method by creating extra extreme points on the intersection points of two items.
36  /// </summary>
37  public class LineProjectionBasedEPCreator : ExtremePointCreator {
38
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      EdgeProjectionForNewItem(binPacking, newItem, position);
169    }
170
171    #region Extreme point creation by using a point projection based method
172
173    /// <summary>
174    /// This method creates extreme points by using a point projection based method.
175    /// For each item there will be created three points and each of the points will be projected twice.
176    /// The direction of the projection depends on position of the point.
177    /// </summary>
178    /// <param name="binPacking"></param>
179    /// <param name="newItem"></param>
180    /// <param name="position"></param>
181    private void PointProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
182      int newWidth = newItem.Width;
183      int newDepth = newItem.Depth;
184      var binShape = binPacking.BinShape;
185      var sourcePoint = new PackingPosition(position.AssignedBin, position.X + newWidth, position.Y, position.Z);
186      PointProjection(binPacking, sourcePoint, ProjectDown);
187      PointProjection(binPacking, sourcePoint, ProjectBackward);
188
189      sourcePoint = new PackingPosition(position.AssignedBin, position.X, position.Y + newItem.Height, position.Z);
190      PointProjection(binPacking, sourcePoint, ProjectLeft);
191      PointProjection(binPacking, sourcePoint, ProjectBackward);
192
193      sourcePoint = new PackingPosition(position.AssignedBin, position.X, position.Y, position.Z + newDepth);
194      PointProjection(binPacking, sourcePoint, ProjectDown);
195      PointProjection(binPacking, sourcePoint, ProjectLeft);
196    }
197
198
199    /// <summary>
200    /// Projects a given point by using the given projection method to the neares item.
201    /// The given projection method returns a point which lies on a side of the nearest item in the direction.
202    /// </summary>
203    /// <param name="binPacking"></param>
204    /// <param name="position"></param>
205    /// <param name="projectionMethod"></param>
206    private void PointProjection(BinPacking3D binPacking, PackingPosition position, Func<BinPacking3D, Vector3D, Vector3D> projectionMethod) {
207      Vector3D sourcePoint = new Vector3D(position);
208      if (sourcePoint.X < binPacking.BinShape.Width && sourcePoint.Y < binPacking.BinShape.Height && sourcePoint.Z < binPacking.BinShape.Depth) {
209        Vector3D point = projectionMethod?.Invoke(binPacking, sourcePoint);
210        if (point != null) {
211          AddExtremePoint(binPacking, new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
212        }
213      }
214    }
215    #endregion
216
217    #region Extreme point creation by using an edge projection based method
218
219    /// <summary>
220    /// This method creates extreme points be projecting the edges of a given item
221    ///   - left
222    ///   - back
223    ///   - down.
224    /// A extreme point will be created, if an edge instersects with an edge of another item.
225    /// </summary>
226    /// <param name="binPacking"></param>
227    /// <param name="newItem"></param>
228    /// <param name="position"></param>
229    private void EdgeProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
230      int newWidth = newItem.Width;
231      int newDepth = newItem.Depth;
232      var binShape = binPacking.BinShape;
233
234      foreach (var ep in GetEpsOnLeft(binPacking, newItem, position)) {
235        AddExtremePoint(binPacking, ep.Key);
236      }
237
238      foreach (var ep in GetEpsBelow(binPacking, newItem, position)) {
239        AddExtremePoint(binPacking, ep.Key);
240      }
241
242      foreach (var ep in GetEpsBehind(binPacking, newItem, position)) {
243        AddExtremePoint(binPacking, ep.Key);
244      }
245    }
246    #endregion
247
248    /// <summary>
249    /// Updates the residual spaces.
250    /// It removes not needed ones.
251    /// A residual space will be removed if the space is a subspace of another one and
252    /// the current one has no item below or both have an item below.
253    /// </summary>
254    /// <param name="binPacking"></param>
255    /// <param name="item"></param>
256    /// <param name="position"></param>
257    protected override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
258    }
259
260    /// <summary>
261    /// Returns true if any item in the bin packing encapsulates the given point
262    /// </summary>
263    /// <param name="binPacking"></param>
264    /// <param name="point"></param>
265    /// <returns></returns>
266    private bool PointIsInAnyItem(BinPacking3D binPacking, Vector3D point) {
267      foreach (var item in binPacking.Items) {
268        PackingPosition position = binPacking.Positions[item.Key];
269        var depth = item.Value.Depth;
270        var width = item.Value.Width;
271        if (position.X <= point.X && point.X < position.X + width &&
272            position.Y <= point.Y && point.Y < position.Y + item.Value.Height &&
273            position.Z <= point.Z && point.Z < position.Z + depth) {
274          return true;
275        }
276      }
277      return false;
278    }
279
280    /// <summary>
281    /// Returns true if an item is in the residual space of a given extrem point
282    /// </summary>
283    /// <param name="rs">KeyValuePair with the position of the extreme point and the size of the residual space</param>
284    /// <param name="item">Given Item</param>
285    /// <param name="position">Given position</param>
286    /// <returns></returns>
287    private bool ItemIsInRs(KeyValuePair<PackingPosition, ResidualSpace> rs, PackingItem item, PackingPosition position) {
288      return GetVertices(item, position).Where(pos => pos.IsInside(rs.Key, rs.Value)).Any();
289    }
290
291    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
292      return binPacking.Items.Select(x => new {
293        Item = x.Value,
294        Position = binPacking.Positions[x.Key]
295      }).Where(x => x.Position.Y < position.Y)
296          .Select(x => Tuple.Create(x.Position, x.Item));
297    }
298
299    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
300      return binPacking.Items.Select(x => new {
301        Item = x.Value,
302        Position = binPacking.Positions[x.Key]
303      }).Where(x => x.Position.Z < position.Z)
304          .Select(x => Tuple.Create(x.Position, x.Item));
305    }
306
307    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
308      return binPacking.Items.Select(x => new {
309        Item = x.Value,
310        Position = binPacking.Positions[x.Key]
311      }).Where(x => x.Position.X < position.X)
312          .Select(x => Tuple.Create(x.Position, x.Item));
313    }
314
315    /// <summary>
316    /// Returns the extreme points and its related residual spaces on the left side of an given item.
317    /// This extreme points are being created by intersecting two edges on the left side of the given item
318    /// (left - in front, left - on top) with all edges on the right side of all other items int the bin packing.
319    /// </summary>
320    /// <param name="item"></param>
321    /// <param name="position"></param>
322    /// <returns></returns>
323    private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
324      var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
325      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsOnLeft(binPacking, item, position);
326      var edges = GetProjectionEdgesOnLeft(item, position);
327
328      foreach (var otherItem in items) {
329        if (position.Equals(otherItem.Item1)) {
330          continue;
331        }
332
333        var otherItemEdges = GetEdgesOnRight(otherItem.Item2, otherItem.Item1);
334        // left - in front
335        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(1, 0, 0))) {
336          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
337            // As this edge has a vertical direction, every point of intersection won't have an item below.
338            // So finally it is being projected down.
339            var point = ProjectDown(binPacking, ProjectLeft(binPacking, ep));
340            var residualSpaces = CalculateResidualSpace(binPacking, point);
341            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
342            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
343              eps.Add(newExtremePoint, residualSpaces);
344            }
345          }
346        }
347
348        // left - on top
349        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(1, 0, 0))) {
350          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
351            var point = ProjectLeft(binPacking, ep);
352            var residualSpaces = CalculateResidualSpace(binPacking, point);
353            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
354            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
355              eps.Add(newExtremePoint, residualSpaces);
356            }
357          }
358        }
359      }
360      return eps;
361    }
362
363
364    /// <summary>
365    /// Returns the extreme points and its related residual spaces below of an given item.
366    /// This extreme points are being created by intersecting two edges below of the given item
367    /// (below - in front, below - right) with all edges on top side of all other items int the bin packing.
368    /// </summary>
369    /// <param name="item"></param>
370    /// <param name="position"></param>
371    /// <returns></returns>
372    private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
373      var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
374      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBelow(binPacking, position);
375      var edges = GetProjectionEdgesBelow(item, position);
376
377      foreach (var otherItem in items) {
378        if (position.Equals(otherItem.Item1)) {
379          continue;
380        }
381
382        var otherItemEdges = GetEdgesOnTop(otherItem.Item2, otherItem.Item1);
383        // below - in front
384        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 1, 0))) {
385          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
386            var point = ProjectDown(binPacking, ep);
387            var residualSpaces = CalculateResidualSpace(binPacking, point);
388            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
389            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
390              eps.Add(newExtremePoint, residualSpaces);
391            }
392          }
393        }
394
395        // below - right
396        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 1, 0))) {
397          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
398            var point = ProjectDown(binPacking, ep);
399            var residualSpaces = CalculateResidualSpace(binPacking, point);
400            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
401            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
402              eps.Add(newExtremePoint, residualSpaces);
403            }
404          }
405        }
406      }
407      return eps;
408    }
409
410    /// <summary>
411    /// Returns the extreme points and its related residual spaces below of an given item.
412    /// This extreme points are being created by intersecting two edges below of the given item
413    /// (right - behind, on top - behind) with all edges on top side of all other items int the bin packing.
414    /// </summary>
415    /// <param name="item"></param>
416    /// <param name="position"></param>
417    /// <returns></returns>
418    private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
419      var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
420      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBehind(binPacking, position);
421      var edges = GetProjectionEdgesBehind(item, position);
422
423      foreach (var otherItem in items) {
424        if (position.Equals(otherItem.Item1)) {
425          continue;
426        }
427
428        var otherItemEdges = GetEdgesInFront(otherItem.Item2, otherItem.Item1);
429        // right - behind
430        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 0, 1))) {
431          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
432            // As this edge has a vertical direction, every point of intersection won't have an item below.
433            // So finally it is being projected down.
434            var point = ProjectDown(binPacking, ProjectBackward(binPacking, ep));
435            var residualSpaces = CalculateResidualSpace(binPacking, point);
436            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
437            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
438              eps.Add(newExtremePoint, residualSpaces);
439            }
440          }
441        }
442
443        // on top - behind
444        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 0, 1))) {
445          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
446            var point = ProjectBackward(binPacking, ep);
447            var residualSpaces = CalculateResidualSpace(binPacking, point);
448            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
449            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
450              eps.Add(newExtremePoint, residualSpaces);
451            }
452          }
453        }
454      }
455      return eps;
456    }
457
458    #region Methods for getting the edges for items
459
460    /// <summary>
461    /// Returns an array of packing position which represents the vertices of an item.
462    /// The position of a vertex in the array is mapped to an item as followed:
463    ///      4----------5
464    ///     /|         /|
465    ///    / |        / |
466    ///   /  0-------/--1
467    ///  6--/-------7  /
468    ///  | /        | /
469    ///  |/         |/
470    ///  2----------3
471    /// 
472    ///  0 = (0,0,0)
473    /// </summary>
474    /// <param name="item"></param>
475    /// <param name="position"></param>
476    /// <returns></returns>
477    private Vector3D[] GetVertices(PackingItem item, PackingPosition position) {
478      int width = item.Width;
479      int depth = item.Depth;
480      return new Vector3D[] {
481        new Vector3D(position.X + 0,     position.Y + 0,           position.Z + 0), // (0,0,0)
482        new Vector3D(position.X + width, position.Y + 0,           position.Z + 0), // (x,0,0)
483        new Vector3D(position.X + 0,     position.Y + 0,           position.Z + depth), // (0,0,z)
484        new Vector3D(position.X + width, position.Y + 0,           position.Z + depth), // (x,0,z)
485
486        new Vector3D(position.X + 0,     position.Y + item.Height, position.Z + 0), // (0,y,0)
487        new Vector3D(position.X + width, position.Y + item.Height, position.Z + 0), // (x,y,0)
488        new Vector3D(position.X + 0,     position.Y + item.Height, position.Z + depth), // (0,y,z)
489        new Vector3D(position.X + width, position.Y + item.Height, position.Z + depth), //(x,y,z)
490      };
491    }
492
493    private Edge3D[] GetProjectionEdgesOnLeft(PackingItem item, PackingPosition position) {
494      Vector3D[] points = GetVertices(item, position);
495
496      return new Edge3D[] {
497        new Edge3D(points[2], points[6]),
498        new Edge3D(points[6], points[4])
499      };
500    }
501
502    private Edge3D[] GetProjectionEdgesBelow(PackingItem item, PackingPosition position) {
503      Vector3D[] points = GetVertices(item, position);
504
505      return new Edge3D[] {
506        new Edge3D(points[2], points[3]),
507        new Edge3D(points[3], points[1])
508      };
509    }
510
511    private Edge3D[] GetProjectionEdgesBehind(PackingItem item, PackingPosition position) {
512      Vector3D[] points = GetVertices(item, position);
513
514      return new Edge3D[] {
515        new Edge3D(points[1], points[5]),
516        new Edge3D(points[5], points[4])
517      };
518    }
519
520    /// <summary>
521    /// Returns an array of edges which contains all edges of the rigth side of an given item.
522    /// </summary>
523    /// <param name="item"></param>
524    /// <param name="position"></param>
525    /// <returns></returns>
526    private Edge3D[] GetEdgesOnRight(PackingItem item, PackingPosition position) {
527      Vector3D[] points = GetVertices(item, position);
528
529      return new Edge3D[] {
530        new Edge3D(points[1], points[5]),
531        new Edge3D(points[5], points[7]),
532        new Edge3D(points[7], points[3]),
533        new Edge3D(points[3], points[1])
534      };
535    }
536
537    /// <summary>
538    /// Returns an array of edges which contains all edges on the top of an given item.
539    /// </summary>
540    /// <param name="item"></param>
541    /// <param name="position"></param>
542    /// <returns></returns>
543    private Edge3D[] GetEdgesOnTop(PackingItem item, PackingPosition position) {
544      Vector3D[] points = GetVertices(item, position);
545
546      return new Edge3D[] {
547        new Edge3D(points[4], points[5]),
548        new Edge3D(points[5], points[7]),
549        new Edge3D(points[7], points[6]),
550        new Edge3D(points[6], points[4])
551      };
552    }
553
554    /// <summary>
555    /// Returns an array of edges which contains all edges in front of an given item.
556    /// </summary>
557    /// <param name="item"></param>
558    /// <param name="position"></param>
559    /// <returns></returns>
560    private Edge3D[] GetEdgesInFront(PackingItem item, PackingPosition position) {
561      Vector3D[] points = GetVertices(item, position);
562
563      return new Edge3D[] {
564        new Edge3D(points[2], points[3]),
565        new Edge3D(points[3], points[7]),
566        new Edge3D(points[7], points[6]),
567        new Edge3D(points[6], points[2])
568      };
569    }
570
571    #endregion
572
573
574    #region Intersections
575
576    /// <summary>
577    /// Returns a collection of points where a given edge (projectedEdge) intersects with other edges.
578    /// The given edge (projectedEdge) will be projected by using the given vector direction
579    /// and a edge of the given edge collection.
580    /// The returned collecten can be empty.
581    /// </summary>
582    /// <param name="projectedEdge"></param>
583    /// <param name="edges"></param>
584    /// <param name="direction"></param>
585    /// <returns></returns>
586    private IEnumerable<Vector3D> IntersectionsForItem(Edge3D projectedEdge, Edge3D[] edges, Vector3D direction = null) {
587      IList<Vector3D> eps = new List<Vector3D>();
588      foreach (var edge in edges) {
589        Edge3D e = projectedEdge;
590        if (direction != null) {
591          if (direction.X != 0) {
592            e.Start.X = edge.Start.X;
593            e.End.X = edge.End.X;
594          } else if (direction.Y != 0) {
595            e.Start.Y = edge.Start.Y;
596            e.End.Y = edge.End.Y;
597          } else if (direction.Z != 0) {
598            e.Start.Z = edge.Start.Z;
599            e.End.Z = edge.End.Z;
600          }
601        }
602
603        var ep = edge.Intersects(e);
604        if (ep != null) {
605          eps.Add(ep);
606        }
607      }
608
609      return eps as IEnumerable<Vector3D>;
610    }
611
612
613
614    #endregion
615
616    /// <summary>
617    /// Calculates the residual spaces for an extreme point.
618    /// </summary>
619    /// <param name="binPacking"></param>
620    /// <param name="pos"></param>
621    /// <returns></returns>
622    protected override IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
623      return ResidualSpaceCalculatorFactory.CreateCalculator().CalculateResidualSpaces(binPacking, pos);
624    }
625  }
626
627
628}
Note: See TracBrowser for help on using the repository browser.