Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
02/01/18 12:21:34 (6 years ago)
Author:
rhanghof
Message:

#2817

  • Former material is now the layer.
  • Added material enumeration
  • Modification at the minimum residual space left bin packer
File:
1 edited

Legend:

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

    r15617 r15705  
    2222using HeuristicLab.Common;
    2323using HeuristicLab.Problems.BinPacking3D.Geometry;
     24using HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation;
    2425using System;
    2526using System.Collections.Generic;
     
    3637  /// </summary>
    3738  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
    3844    protected override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    39       GenerateNewExtremePointsForItem(binPacking, item, position);
    40 
    41       // if an item is fit in below, before, or left of another its extreme points have to be regenerated
    42       foreach (var above in GetItemsAbove(binPacking, position)) {
    43         GenerateNewExtremePointsForItem(binPacking, above.Item2, above.Item1);
    44       }
    45       foreach (var front in GetItemsInfront(binPacking, position)) {
    46         GenerateNewExtremePointsForItem(binPacking, front.Item2, front.Item1);
    47       }
    48       foreach (var right in GetItemsOnRight(binPacking, position)) {
    49         GenerateNewExtremePointsForItem(binPacking, right.Item2, right.Item1);
    50       }
    51     }
    52    
     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>
    53256    protected override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    54       foreach (var extremePoint in binPacking.ExtremePoints.ToList()) {
    55         var ep = extremePoint.Key;
    56         var residualSpaces = extremePoint.Value as IList<ResidualSpace>;
    57         for (int i = 0; i < residualSpaces.Count(); i++) {
    58           var rs = residualSpaces[i];
    59           var depth = item.Depth;
    60           var width = item.Width;
    61           var changed = false;
    62           if (ep.Z >= position.Z && ep.Z < position.Z + depth) {
    63             if (ep.X <= position.X && ep.Y >= position.Y && ep.Y < position.Y + item.Height) {
    64               var diff = position.X - ep.X;
    65               var newRSX = Math.Min(rs.Width, diff);
    66               rs = ResidualSpace.Create(newRSX, rs.Height, rs.Depth);
    67               changed = true;
    68             }
    69             if (ep.Y <= position.Y && ep.X >= position.X && ep.X < position.X + width) {
    70               var diff = position.Y - ep.Y;
    71               var newRSY = Math.Min(rs.Height, diff);
    72               rs = ResidualSpace.Create(rs.Width, newRSY, rs.Depth);
    73               changed = true;
    74             }
    75           }
    76 
    77           if (ep.Z <= position.Z &&
    78               ep.Y >= position.Y && ep.Y < position.Y + item.Height &&
    79               ep.X >= position.X && ep.X < position.X + width) {
    80             var diff = position.Z - ep.Z;
    81             var newRSZ = Math.Min(rs.Depth, diff);
    82             rs = ResidualSpace.Create(rs.Width, rs.Height, newRSZ);
    83             changed = true;
    84           }
    85 
    86           if (changed) {
    87             if (!rs.IsZero() && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) {
    88               residualSpaces[i] = rs;
    89             } else {
    90               binPacking.ExtremePoints.Remove(ep);
    91               break;
    92             }
    93           }
    94         }       
    95       }
    96       return;
    97     }
    98    
    99     /// <summary>
    100     /// Adds an extreme point to a given bin packing.
    101     /// It also adds the residual space for the new extreme point
    102     /// and removes the extreme point and the related residual space for the given position which are not needed anymore.
    103     /// </summary>
    104     /// <param name="binPacking"></param>
    105     /// <param name="position"></param>
    106     /// <returns></returns>
    107     protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
    108       if (binPacking.ExtremePoints.ContainsKey(position)) {
    109         return false;
    110       }
    111 
    112       var residualSpaces = CalculateResidualSpace(binPacking, new Vector3D(position));
    113       binPacking.ExtremePoints.Add(position, residualSpaces);
    114       // Check if the existing extreme points are shadowed by the new point
    115       // This is, their residual space fit entirely into the residual space of the new point
    116       foreach (var ep in binPacking.ExtremePoints.Where(x => x.Key != position && new Vector3D(x.Key).IsInside(position, residualSpaces)).ToList()) {
    117         foreach (var residualSpace in ep.Value) {
    118           if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep.Key), residualSpace, position, residualSpaces)) {
    119             binPacking.ExtremePoints.Remove(ep);
    120             break;
    121           }
    122         }         
    123       }
    124       return true;
    125     }
    126 
    127     /// <summary>
    128     /// Calculates the residual space for a given bin packing and position.
    129     /// It returns the residual space as a tuple which contains the dimensions
    130     /// </summary>
    131     /// <param name="binPacking"></param>
    132     /// <param name="pos"></param>
    133     /// <returns>A Tuple(width, Height, Depth)</width></returns>
    134     protected override IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
    135       var residualSpaces = new List<ResidualSpace>();
    136       var residualSpace = new ResidualSpace(CalculateResidualSpaceOld(binPacking, pos));
    137       if (!residualSpace.IsZero()) {
    138         residualSpaces.Add(residualSpace);
    139       }
    140       return residualSpaces;
    141     }
    142 
    143     protected Tuple<int, int, int> CalculateResidualSpaceOld(BinPacking3D binPacking, Vector3D pos) {
    144 
    145       if (pos == null) {
    146         return Tuple.Create(0, 0, 0);
    147       }
    148       var itemPos = binPacking.Items.Select(x => new {
     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 {
    149292        Item = x.Value,
    150293        Position = binPacking.Positions[x.Key]
    151       });
    152       Vector3D limit = new Vector3D() {
    153         X = binPacking.BinShape.Width,
    154         Y = binPacking.BinShape.Height,
    155         Z = binPacking.BinShape.Depth
     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)
    156489      };
    157 
    158       if (pos.X < limit.X && pos.Y < limit.Y && pos.Z < limit.Z) {
    159         var rightLimit = ProjectRight(binPacking, pos);
    160         var upLimit = ProjectUp(binPacking, pos);
    161         var forwardLimit = ProjectForward(binPacking, pos);
    162         if (rightLimit.X > 0) {
    163           limit.X = rightLimit.X;
    164         }
    165         if (upLimit.Y > 0) {
    166           limit.Y = upLimit.Y;
    167         }
    168         if (forwardLimit.Z > 0) {
    169           limit.Z = forwardLimit.Z;
    170         }
    171       }
    172 
    173       if (limit.X - pos.X <= 0 || limit.Y - pos.Y <= 0 || limit.Z - pos.Z <= 0) {
    174         return Tuple.Create(0, 0, 0);
    175       }
    176       return Tuple.Create(limit.X - pos.X, limit.Y - pos.Y, limit.Z - pos.Z);
     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);
    177623    }
    178624  }
Note: See TracChangeset for help on using the changeset viewer.