Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
02/07/18 14:54:42 (7 years ago)
Author:
rhanghof
Message:

#2817:

  • Added a new packer.
  • Enhanced the material types.
  • Added extreme point pruning for layer support in the extrem point creators.
  • BinPacking3D: Added a graph for calculating weigth distribution of the items.
Location:
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/LineProjectionBasedEPCreator.cs

    r15705 r15731  
    3535  /// This projection method enhances the point based projection method by creating extra extreme points on the intersection points of two items.
    3636  /// </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     }
     37  public class LineProjectionBasedEPCreator : PointProjectionBasedEPCreator {
     38   
     39
    15740
    15841    /// <summary>
    … …  
    16851      EdgeProjectionForNewItem(binPacking, newItem, position);
    16952    }
    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
     53   
    21654
    21755    #region Extreme point creation by using an edge projection based method
    … …  
    24583    }
    24684    #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     }
     85   
    25986
    26087    /// <summary>
    … …  
    609436      return eps as IEnumerable<Vector3D>;
    610437    }
    611 
    612 
    613 
    614438    #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     }
     439   
    625440  }
    626 
    627 
    628441}

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/PointProjectionBasedEPCreator.cs

    r15705 r15731  
    2121
    2222using HeuristicLab.Common;
     23using HeuristicLab.Problems.BinPacking3D.ExtremePointPruning;
    2324using HeuristicLab.Problems.BinPacking3D.Geometry;
    2425using HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation;
    … …  
    4041    /// This lock object is needed because of creating the extreme points in an parallel for loop.
    4142    /// </summary>
    42     object _lockAddExtremePoint = new object();
     43    protected object _lockAddExtremePoint = new object();
    4344
    4445    protected override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    4546      binPacking.ExtremePoints.Clear();
    4647
     48      if (binPacking.Items.Count <= 0) {
     49        return;
     50      }
     51
    4752      // generate all new extreme points parallel. This speeds up the creator.
    48       Parallel.ForEach(binPacking.Items, i => {
     53      var items = binPacking.Items.OrderBy(x => x.Value.Layer);
     54      Parallel.ForEach(items.Where(x => x.Value.Layer < item.Layer), i => {
    4955        PackingItem it = i.Value;
    50         PackingPosition p = binPacking.Positions[i.Key];
    51         GenerateNewExtremePointsForItem(binPacking, it, p);
     56        PackingPosition pos = binPacking.Positions[i.Key];
     57        GenerateNewExtremePointsForItem(binPacking, it, pos);
    5258      });
    53 
     59      ExtremePointPruningFactory.CreatePruning().PruneExtremePoints(ExtremePointPruningMethod.PruneBehind, new List<BinPacking3D>() { binPacking });
     60
     61      Parallel.ForEach(items.Where(x => x.Value.Layer >= item.Layer), i => {
     62        PackingItem it = i.Value;
     63        PackingPosition pos = binPacking.Positions[i.Key];
     64        GenerateNewExtremePointsForItem(binPacking, it, pos);
     65      });
     66     
    5467      // remove not needed extreme points.
    5568      foreach (var extremePoint in binPacking.ExtremePoints.ToList()) {
    … …  
    178191    /// <param name="newItem"></param>
    179192    /// <param name="position"></param>
    180     private void PointProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
     193    protected void PointProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
    181194      int newWidth = newItem.Width;
    182195      int newDepth = newItem.Depth;
    … …  
    210223          AddExtremePoint(binPacking, new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
    211224        }
    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);
    243225      }
    244226    }
    … …  
    277259    }
    278260
    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
    614261
    615262    /// <summary>
Note: See TracChangeset for help on using the changeset viewer.