Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
12/20/17 16:15:38 (7 years ago)
Author:
rhanghof
Message:

#2817:

  • Unittests
  • Bugfixes on the line projection based extreme point creation method
Location:
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation
Files:
3 edited

Legend:

Unmodified
Added
Removed

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

    r15520 r15554  
    4646        // Projecting onto the XZ-plane
    4747        var below = ProjectDown(binPacking, sourcePoint);
    48         var residualSpace = CalculateResidualSpace(binPacking, below);
    49         if (!residualSpace.IsZero()
    50           && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpace)) {
     48        var residualSpaces = CalculateResidualSpace(binPacking, below);
     49        if (residualSpaces.Count() > 0
     50          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpaces)) {
    5151          // add only if the projected point's residual space is not a sub-space
    5252          // of another extreme point's residual space
    … …  
    5656        // Projecting onto the XY-plane
    5757        var back = ProjectBackward(binPacking, sourcePoint);
    58         residualSpace = CalculateResidualSpace(binPacking, back);
    59         if (!residualSpace.IsZero()
    60           && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpace)) {
     58        residualSpaces = CalculateResidualSpace(binPacking, back);
     59        if (residualSpaces.Count() > 0
     60          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpaces)) {
    6161          // add only if the projected point's residual space is not a sub-space
    6262          // of another extreme point's residual space
    … …  
    7171        // Projecting onto the YZ-plane
    7272        var left = ProjectLeft(binPacking, sourcePoint);
    73         var residualSpace = CalculateResidualSpace(binPacking, left);
    74         if (!residualSpace.IsZero()
    75           && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpace)) {
     73        var residualSpaces = CalculateResidualSpace(binPacking, left);
     74        if (residualSpaces.Count() > 0
     75          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpaces)) {
    7676          // add only if the projected point's residual space is not a sub-space
    7777          // of another extreme point's residual space
    … …  
    8181        // Projecting onto the XY-plane
    8282        var back = ProjectBackward(binPacking, sourcePoint);
    83         residualSpace = CalculateResidualSpace(binPacking, back);
    84         if (!residualSpace.IsZero()
    85           && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpace)) {
     83        residualSpaces = CalculateResidualSpace(binPacking, back);
     84        if (residualSpaces.Count() > 0
     85          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpaces)) {
    8686          // add only if the projected point's residual space is not a sub-space
    8787          // of another extreme point's residual space
    … …  
    9696        // Projecting onto the XZ-plane
    9797        var below = ProjectDown(binPacking, sourcePoint);
    98         var residualSpace = CalculateResidualSpace(binPacking, below);
    99         if (!residualSpace.IsZero()
    100           && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpace)) {
     98        var residualSpaces = CalculateResidualSpace(binPacking, below);
     99        if (residualSpaces.Count() > 0
     100          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpaces)) {
    101101          // add only if the projected point's residual space is not a sub-space
    102102          // of another extreme point's residual space
    … …  
    106106        // Projecting onto the YZ-plane
    107107        var left = ProjectLeft(binPacking, sourcePoint);
    108         residualSpace = CalculateResidualSpace(binPacking, left);
    109         if (!residualSpace.IsZero()
    110           && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpace)) {
     108        residualSpaces = CalculateResidualSpace(binPacking, left);
     109        if (residualSpaces.Count() > 0
     110          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpaces)) {
    111111          // add only if the projected point's residual space is not a sub-space
    112112          // of another extreme point's residual space
    … …  
    191191    /// <param name="residualSpace"></param>
    192192    /// <returns></returns>
    193     protected virtual bool IsWithinResidualSpaceOfAnotherExtremePoint(BinPacking3D binPacking, Vector3D pos, ResidualSpace residualSpace) {
    194       var eps = binPacking.ExtremePoints.Where(x => !pos.Equals(x) && pos.IsInside(x, binPacking.ResidualSpaces[x]));
    195       return eps.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, residualSpace, x, binPacking.ResidualSpaces[x]));
     193    protected bool IsWithinResidualSpaceOfAnotherExtremePoint(BinPacking3D binPacking, Vector3D pos, ResidualSpace residualSpace) {
     194      var eps = binPacking.ExtremePoints.Where(x => !pos.Equals(x.Key) && pos.IsInside(x.Key, x.Value));
     195      return eps.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, residualSpace, x.Key, x.Value));
     196    }
     197
     198    /// <summary>
     199    ///
     200    /// </summary>
     201    /// <param name="binPacking"></param>
     202    /// <param name="pos"></param>
     203    /// <param name="residualSpaces"></param>
     204    /// <returns></returns>
     205    protected bool IsWithinResidualSpaceOfAnotherExtremePoint(BinPacking3D binPacking, Vector3D pos, IEnumerable<ResidualSpace> residualSpaces) {
     206      foreach (var residualSpace in residualSpaces) {
     207        if (IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, pos, residualSpace)) {
     208          return true;
     209        }
     210      }
     211      return false;
     212    }
     213
     214
     215    /// <summary>
     216    /// Returns true, if the given poisition and the related residual space is within the residual space of the given extreme point
     217    /// </summary>
     218    /// <param name="pos"></param>
     219    /// <param name="rsPos"></param>
     220    /// <param name="ep"></param>
     221    /// <param name="rsEp"></param>
     222    /// <returns></returns>
     223    protected bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, ResidualSpace rsPos, PackingPosition ep, IEnumerable<ResidualSpace> rsEp) {
     224      return rsEp.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, rsPos, ep, x));
    196225    }
    197226
    … …  
    211240
    212241    /// <summary>
    213     /// Calculates the residual space for a given bin packing and position.
    214     /// It returns the residual space as a tuple which contains the dimensions
    215     /// </summary>
    216     /// <param name="binPacking"></param>
    217     /// <param name="pos"></param>
    218     /// <returns>A Tuple(width, Height, Depth)</width></returns>
    219     protected virtual ResidualSpace CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
    220       //return ResidualSpaceCalculator.Create().CalculateResidualSpace(binPacking, pos).First();
    221       return new ResidualSpace(CalculateResidualSpaceOld(binPacking, pos));
    222     }
    223 
    224     protected virtual Tuple<int, int, int> CalculateResidualSpaceOld(BinPacking3D binPacking, Vector3D pos) {
    225 
    226       if (pos == null) {
    227         return Tuple.Create(0, 0, 0);
    228       }
    229       var itemPos = binPacking.Items.Select(x => new {
    230         Item = x.Value,
    231         Position = binPacking.Positions[x.Key]
    232       });
    233       Vector3D limit = new Vector3D() {
    234         X = binPacking.BinShape.Width,
    235         Y = binPacking.BinShape.Height,
    236         Z = binPacking.BinShape.Depth
    237       };
    238 
    239       if (pos.X < limit.X && pos.Y < limit.Y && pos.Z < limit.Z) {
    240         var rightLimit = ProjectRight(binPacking, pos);
    241         var upLimit = ProjectUp(binPacking, pos);
    242         var forwardLimit = ProjectForward(binPacking, pos);
    243         if (rightLimit.X > 0) {
    244           limit.X = rightLimit.X;
    245         }
    246         if (upLimit.Y > 0) {
    247           limit.Y = upLimit.Y;
    248         }
    249         if (forwardLimit.Z > 0) {
    250           limit.Z = forwardLimit.Z;
    251         }
    252       }
    253 
    254       if (limit.X - pos.X <= 0 || limit.Y - pos.Y <= 0 || limit.Z - pos.Z <= 0) {
    255         return Tuple.Create(0, 0, 0);
    256       }
    257       return Tuple.Create(limit.X - pos.X, limit.Y - pos.Y, limit.Z - pos.Z);
    258     }
    259 
     242    /// Calculates the residual spaces for a given bin packing and position.
     243    /// It returns a collection of residual spaces
     244    /// </summary>
     245    /// <param name="binPacking"></param>
     246    /// <param name="pos"></param>
     247    /// <returns></returns>
     248    protected abstract IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos);
     249   
    260250    #endregion
    261251

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

    r15520 r15554  
    1515  public class LineProjectionBasedEPCreator : ExtremePointCreator {
    1616
    17 
    18 
    19 
    2017    protected override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    21       // After a item has been placed, the residual space has to be recalculated.
    22       //RecalculateResidualSpaces(binPacking);
    23 
    24       //GenerateNewExtremePointsForItem(binPacking, item, position);
    25 
    2618      binPacking.ExtremePoints.Clear();
    27       binPacking.ResidualSpaces.Clear();
    2819
    2920      foreach (var i in binPacking.Items) {
    … …  
    3223        GenerateNewExtremePointsForItem(binPacking, it, p);
    3324      }
    34       //RecalculateResidualSpaces(binPacking);
    35     }
    36 
    37     /// <summary>
    38     /// Adds an new extreme point an the related residual space to a given bin packing.
    39     /// - The given position has to be valid
    40     /// - The residual space must not be zero
    41     /// </summary>
    42     /// <param name="binPacking"></param>
    43     /// <param name="position"></param>
    44     /// <returns></returns>
     25    }
     26
     27    /// <summary>
     28    /// Adds a new extreme point an the related residual spaces to a given bin packing.
     29    /// - The given position has to be valid.
     30    /// - The extreme point does not exist in the bin packing.
     31    /// - There must be at minimum one valid residual space. A residual space is invalid if the space is zero.
     32    /// </summary>
     33    /// <param name="binPacking"></param>
     34    /// <param name="position"></param>
     35    /// <returns>True = the given point and its related residual spaces were successfully added to the bin packing</returns>
    4536    protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
    4637      if (position == null) {
    … …  
    4839      }
    4940
    50       if (PointIsInItem(binPacking, new Vector3D(position))) {
     41      if (PointIsInAnyItem(binPacking, new Vector3D(position))) {
    5142        return false;
    5243      }
    5344
     45      if (binPacking.ExtremePoints.ContainsKey(position)) {
     46        return false;
     47      }
     48
    5449      var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
    5550
    56       if (rs.IsZero()) {
     51      if (rs.Count() <= 0) {
    5752        return false;
    5853      }
    5954
    60       if (!binPacking.ExtremePoints.Add(position)) {
     55      // todo
     56      /*
     57       ist der extrempunkt im residual space eines anderen muss ueberprueft werden:
     58          - ist der andere ep in der luft, kann auch dieser hinzugefuegt werden.
     59          - hat der andere ep ein item unterhalb, darf dieser nicht hinzugefuegt werden.
     60       -> neu methode basierend auf IsWithinResidualSpaceOfAnotherExtremePoint, die den ep oder rs zurueck gibt, der einen anderen rs einschließt.
     61          eventuell gehoert diese logik in den ResidualSpaceCreator.
     62      if (LiesOnAnyItem(binPacking, position)) {
    6163        return false;
    62       }
    63 
    64       binPacking.ResidualSpaces.Add(position, rs);
     64      }*/
     65
     66      binPacking.ExtremePoints.Add(position, rs);
    6567      return true;
     68    }
     69
     70    private bool LiesOnAnyItem(BinPacking3D binPacking, PackingPosition position) {
     71      if (position.Y == 0) {
     72        return true;
     73      }
     74
     75      var items = binPacking.Items.Where(x => {
     76        var itemPosition = binPacking.Positions[x.Key];
     77        var item = x.Value;
     78        int width = itemPosition.Rotated ? item.Depth : item.Width;
     79        int depth = itemPosition.Rotated ? item.Width : item.Depth;
     80
     81        return itemPosition.Y + item.Height == position.Y &&
     82               itemPosition.X <= position.X && position.X < itemPosition.X + width &&
     83               itemPosition.Z <= position.Z && position.Z < itemPosition.Z + depth;
     84      });
     85
     86      return items.Count() > 0;
    6687    }
    6788
    … …  
    83104    /// <summary>
    84105    /// This method creates extreme points by using a point projection based method.
    85     /// For each item there will be three points created and each of the point will be projected twice.
     106    /// For each item there will be created three points and each of the points will be projected twice.
    86107    /// The direction of the projection depends on position of the point.
    87108    /// </summary>
    … …  
    118139      if (sourcePoint.X < binPacking.BinShape.Width && sourcePoint.Y < binPacking.BinShape.Height && sourcePoint.Z < binPacking.BinShape.Depth) {
    119140        Vector3D point = projectionMethod?.Invoke(binPacking, sourcePoint);
    120         AddExtremePoint(binPacking, new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
     141        if (point != null) {
     142          AddExtremePoint(binPacking, new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
     143        }
    121144      }
    122145    }
    … …  
    141164
    142165      foreach (var ep in GetEpsOnLeft(binPacking, newItem, position)) {
    143         AddExtremePoint(binPacking, ep);
     166        AddExtremePoint(binPacking, ep.Key);
    144167      }
    145168
    146169      foreach (var ep in GetEpsBelow(binPacking, newItem, position)) {
    147         AddExtremePoint(binPacking, ep);
     170        AddExtremePoint(binPacking, ep.Key);
    148171      }
    149172
    150173      foreach (var ep in GetEpsBehind(binPacking, newItem, position)) {
    151         AddExtremePoint(binPacking, ep);
     174        AddExtremePoint(binPacking, ep.Key);
    152175      }
    153176    }
    154177    #endregion
    155178
    156 
     179    /// <summary>
     180    /// Updates the residual spaces.
     181    /// It removes not needed ones.
     182    /// A residual space will be removed if the space is a subspace of another one and
     183    /// the current one has no item below or both have an item below.
     184    /// </summary>
     185    /// <param name="binPacking"></param>
     186    /// <param name="item"></param>
     187    /// <param name="position"></param>
    157188    protected override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    158       return;
    159     }
    160 
    161     private bool PointIsInItem(BinPacking3D binPacking, Vector3D point) {
     189    }
     190
     191    /// <summary>
     192    /// Returns true if any item in the bin packing encapsulates the given point
     193    /// </summary>
     194    /// <param name="binPacking"></param>
     195    /// <param name="point"></param>
     196    /// <returns></returns>
     197    private bool PointIsInAnyItem(BinPacking3D binPacking, Vector3D point) {
    162198      foreach (var item in binPacking.Items) {
    163199        PackingPosition position = binPacking.Positions[item.Key];
    … …  
    184220    }
    185221
    186     /// <summary>
    187     /// Recalculates the residual spaces if needed.
    188     /// It checks if an item is in an residual space and if so the residual space will be recalculated.
    189     /// If the residual space has gone to zero, this residual space and its related extreme point will be removed.
    190     /// </summary>
    191     /// <param name="binPacking"></param>
    192     private void RecalculateResidualSpaces(BinPacking3D binPacking) {
    193       var recalculatedSpaces = new Dictionary<PackingPosition, ResidualSpace>();
    194       foreach (var ep in binPacking.ExtremePoints.ToList()) {
    195         var newRs = CalculateResidualSpace(binPacking, new Vector3D(ep));
    196         if (!newRs.IsZero() && !PointIsInItem(binPacking, new Vector3D(ep))) {
    197           recalculatedSpaces.Add(ep, newRs);
    198         } else {
    199           binPacking.ExtremePoints.Remove(ep);
    200         }
    201       }
    202       binPacking.ResidualSpaces = recalculatedSpaces;
    203     }
    204 
    205222    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    206223      return binPacking.Items.Select(x => new {
    … …  
    228245
    229246    /// <summary>
    230     /// Returns the extremepoints on the left side of an given item
    231     /// </summary>
    232     /// <param name="item"></param>
    233     /// <param name="position"></param>
    234     /// <returns></returns>
    235     private IList<PackingPosition> GetEpsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    236       IList<PackingPosition> eps = new List<PackingPosition>();
     247    /// Returns the extreme points and its related residual spaces on the left side of an given item.
     248    /// This extreme points are being created by intersecting two edges on the left side of the given item
     249    /// (left - in front, left - on top) with all edges on the right side of all other items int the bin packing.
     250    /// </summary>
     251    /// <param name="item"></param>
     252    /// <param name="position"></param>
     253    /// <returns></returns>
     254    private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
     255      var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
    237256      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsOnLeft(binPacking, item, position);
    238257      var edges = GetProjectionEdgesOnLeft(item, position);
    239258
    240259      foreach (var otherItem in items) {
     260        if (position.Equals(otherItem.Item1)) {
     261          continue;
     262        }
     263
    241264        var otherItemEdges = GetEdgesOnRight(otherItem.Item2, otherItem.Item1);
     265        // left - in front
    242266        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(1, 0, 0))) {
    243267          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
     268            // As this edge has a vertical direction, every point of intersection won't have an item below.
     269            // So finally it is being projected down.
    244270            var point = ProjectDown(binPacking, ProjectLeft(binPacking, ep));
    245             var residualSpace = CalculateResidualSpace(binPacking, point);
    246             if (!residualSpace.IsZero()) {
    247               eps.Add(point.ToPackingPosition(position.AssignedBin));
     271            var residualSpaces = CalculateResidualSpace(binPacking, point);
     272            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
     273            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
     274              eps.Add(newExtremePoint, residualSpaces);
    248275            }
    249276          }
    250277        }
     278
     279        // left - on top
    251280        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(1, 0, 0))) {
    252281          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
    253282            var point = ProjectLeft(binPacking, ep);
    254             var residualSpace = CalculateResidualSpace(binPacking, point);
    255             if (!residualSpace.IsZero()) {
    256               eps.Add(point.ToPackingPosition(position.AssignedBin));
     283            var residualSpaces = CalculateResidualSpace(binPacking, point);
     284            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
     285            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
     286              eps.Add(newExtremePoint, residualSpaces);
    257287            }
    258288          }
    … …  
    264294
    265295    /// <summary>
    266     /// Returns the extremepoints below of an given item
    267     /// </summary>
    268     /// <param name="item"></param>
    269     /// <param name="position"></param>
    270     /// <returns></returns>
    271     private IList<PackingPosition> GetEpsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    272       IList<PackingPosition> eps = new List<PackingPosition>();
     296    /// Returns the extreme points and its related residual spaces below of an given item.
     297    /// This extreme points are being created by intersecting two edges below of the given item
     298    /// (below - in front, below - right) with all edges on top side of all other items int the bin packing.
     299    /// </summary>
     300    /// <param name="item"></param>
     301    /// <param name="position"></param>
     302    /// <returns></returns>
     303    private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
     304      var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
    273305      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBelow(binPacking, position);
    274306      var edges = GetProjectionEdgesBelow(item, position);
    275307
    276308      foreach (var otherItem in items) {
     309        if (position.Equals(otherItem.Item1)) {
     310          continue;
     311        }
     312
    277313        var otherItemEdges = GetEdgesOnTop(otherItem.Item2, otherItem.Item1);
     314        // below - in front
    278315        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 1, 0))) {
    279316          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
    280317            var point = ProjectDown(binPacking, ep);
    281             var residualSpace = CalculateResidualSpace(binPacking, point);
    282             if (!residualSpace.IsZero()) {
    283               eps.Add(point.ToPackingPosition(position.AssignedBin));
     318            var residualSpaces = CalculateResidualSpace(binPacking, point);
     319            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
     320            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
     321              eps.Add(newExtremePoint, residualSpaces);
    284322            }
    285323          }
    286324        }
     325
     326        // below - right
    287327        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 1, 0))) {
    288328          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
    289329            var point = ProjectDown(binPacking, ep);
    290             var residualSpace = CalculateResidualSpace(binPacking, point);
    291             if (!residualSpace.IsZero()) {
    292               eps.Add(point.ToPackingPosition(position.AssignedBin));
     330            var residualSpaces = CalculateResidualSpace(binPacking, point);
     331            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
     332            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
     333              eps.Add(newExtremePoint, residualSpaces);
    293334            }
    294335          }
    … …  
    299340
    300341    /// <summary>
    301     /// Returns
    302     /// </summary>
    303     /// <param name="item"></param>
    304     /// <param name="position"></param>
    305     /// <returns></returns>
    306     private IList<PackingPosition> GetEpsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    307       IList<PackingPosition> eps = new List<PackingPosition>();
     342    /// Returns the extreme points and its related residual spaces below of an given item.
     343    /// This extreme points are being created by intersecting two edges below of the given item
     344    /// (right - behind, on top - behind) with all edges on top side of all other items int the bin packing.
     345    /// </summary>
     346    /// <param name="item"></param>
     347    /// <param name="position"></param>
     348    /// <returns></returns>
     349    private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
     350      var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
    308351      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBehind(binPacking, position);
    309352      var edges = GetProjectionEdgesBehind(item, position);
    310353
    311354      foreach (var otherItem in items) {
     355        if (position.Equals(otherItem.Item1)) {
     356          continue;
     357        }
     358
    312359        var otherItemEdges = GetEdgesInFront(otherItem.Item2, otherItem.Item1);
     360        // right - behind
    313361        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 0, 1))) {
    314362          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
     363            // As this edge has a vertical direction, every point of intersection won't have an item below.
     364            // So finally it is being projected down.
    315365            var point = ProjectDown(binPacking, ProjectBackward(binPacking, ep));
    316             var residualSpace = CalculateResidualSpace(binPacking, point);
    317             if (!residualSpace.IsZero()) {
    318               eps.Add(point.ToPackingPosition(position.AssignedBin));
     366            var residualSpaces = CalculateResidualSpace(binPacking, point);
     367            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
     368            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
     369              eps.Add(newExtremePoint, residualSpaces);
    319370            }
    320371          }
    321372        }
     373
     374        // on top - behind
    322375        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 0, 1))) {
    323376          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
    324377            var point = ProjectBackward(binPacking, ep);
    325             var residualSpace = CalculateResidualSpace(binPacking, point);
    326             if (!residualSpace.IsZero()) {
    327               eps.Add(point.ToPackingPosition(position.AssignedBin));
     378            var residualSpaces = CalculateResidualSpace(binPacking, point);
     379            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
     380            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
     381              eps.Add(newExtremePoint, residualSpaces);
    328382            }
    329383          }
    … …  
    452506
    453507    /// <summary>
    454     ///
     508    /// Returns a collection of points where a given edge (projectedEdge) intersects with other edges.
     509    /// The given edge (projectedEdge) will be projected by using the given vector direction
     510    /// and a edge of the given edge collection.
     511    /// The returned collecten can be empty.
    455512    /// </summary>
    456513    /// <param name="projectedEdge"></param>
    457514    /// <param name="edges"></param>
     515    /// <param name="direction"></param>
    458516    /// <returns></returns>
    459517    private IEnumerable<Vector3D> IntersectionsForItem(Edge3D projectedEdge, Edge3D[] edges, Vector3D direction = null) {
    … …  
    486544    #endregion
    487545
    488    
    489     protected override ResidualSpace CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
    490       return ResidualSpaceCalculatorFactory.CreateCalculator().CalculateResidualSpaces(binPacking, pos).First();
     546    /// <summary>
     547    /// Calculates the residual spaces for an extreme point.
     548    /// </summary>
     549    /// <param name="binPacking"></param>
     550    /// <param name="pos"></param>
     551    /// <returns></returns>
     552    protected override IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
     553      return ResidualSpaceCalculatorFactory.CreateCalculator().CalculateResidualSpaces(binPacking, pos);
    491554    }
    492555  }
    493556
    494  
     557
    495558}

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

    r15520 r15554  
    3131   
    3232    protected override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    33       foreach (var ep in binPacking.ExtremePoints.ToList()) {
    34         var rs = binPacking.ResidualSpaces[ep];
    35         var depth = position.Rotated ? item.Width : item.Depth;
    36         var width = position.Rotated ? item.Depth : item.Width;
    37         var changed = false;
    38         if (ep.Z >= position.Z && ep.Z < position.Z + depth) {
    39           if (ep.X <= position.X && ep.Y >= position.Y && ep.Y < position.Y + item.Height) {
    40             var diff = position.X - ep.X;
    41             var newRSX = Math.Min(rs.Width, diff);
    42             rs = ResidualSpace.Create(newRSX, rs.Height, rs.Depth);
     33      foreach (var extremePoint in binPacking.ExtremePoints.ToList()) {
     34        var ep = extremePoint.Key;
     35        var residualSpaces = extremePoint.Value as IList<ResidualSpace>;
     36        for (int i = 0; i < residualSpaces.Count(); i++) {
     37          var rs = residualSpaces[i];
     38          var depth = position.Rotated ? item.Width : item.Depth;
     39          var width = position.Rotated ? item.Depth : item.Width;
     40          var changed = false;
     41          if (ep.Z >= position.Z && ep.Z < position.Z + depth) {
     42            if (ep.X <= position.X && ep.Y >= position.Y && ep.Y < position.Y + item.Height) {
     43              var diff = position.X - ep.X;
     44              var newRSX = Math.Min(rs.Width, diff);
     45              rs = ResidualSpace.Create(newRSX, rs.Height, rs.Depth);
     46              changed = true;
     47            }
     48            if (ep.Y <= position.Y && ep.X >= position.X && ep.X < position.X + width) {
     49              var diff = position.Y - ep.Y;
     50              var newRSY = Math.Min(rs.Height, diff);
     51              rs = ResidualSpace.Create(rs.Width, newRSY, rs.Depth);
     52              changed = true;
     53            }
     54          }
     55
     56          if (ep.Z <= position.Z &&
     57              ep.Y >= position.Y && ep.Y < position.Y + item.Height &&
     58              ep.X >= position.X && ep.X < position.X + width) {
     59            var diff = position.Z - ep.Z;
     60            var newRSZ = Math.Min(rs.Depth, diff);
     61            rs = ResidualSpace.Create(rs.Width, rs.Height, newRSZ);
    4362            changed = true;
    4463          }
    45           if (ep.Y <= position.Y && ep.X >= position.X && ep.X < position.X + width) {
    46             var diff = position.Y - ep.Y;
    47             var newRSY = Math.Min(rs.Height, diff);
    48             rs = ResidualSpace.Create(rs.Width, newRSY, rs.Depth);
    49             changed = true;
     64
     65          if (changed) {
     66            if (!rs.IsZero() && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) {
     67              residualSpaces[i] = rs;
     68            } else {
     69              binPacking.ExtremePoints.Remove(ep);
     70              break;
     71            }
    5072          }
    51         }
    52 
    53         if (ep.Z <= position.Z &&
    54             ep.Y >= position.Y && ep.Y < position.Y + item.Height &&
    55             ep.X >= position.X && ep.X < position.X + width) {
    56           var diff = position.Z - ep.Z;
    57           var newRSZ = Math.Min(rs.Depth, diff);
    58           rs = ResidualSpace.Create(rs.Width, rs.Height, newRSZ);
    59           changed = true;
    60         }
    61 
    62         if (changed) {
    63           if (!rs.IsZero() && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) {
    64             binPacking.ResidualSpaces[ep] = rs;
    65           } else {
    66             binPacking.ExtremePoints.Remove(ep);
    67             binPacking.ResidualSpaces.Remove(ep);
    68           }
    69         }
     73        }       
    7074      }
    7175      return;
    … …  
    8185    /// <returns></returns>
    8286    protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
    83       if (binPacking.ExtremePoints.Add(position)) {
    84         var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
    85         binPacking.ResidualSpaces.Add(position, rs);
    86         // Check if the existing extreme points are shadowed by the new point
    87         // This is, their residual space fit entirely into the residual space of the new point
    88         foreach (var ep in binPacking.ExtremePoints.Where(x => x != position && new Vector3D(x).IsInside(position, rs)).ToList()) {
    89           if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), binPacking.ResidualSpaces[ep], position, rs)) {
     87      if (binPacking.ExtremePoints.ContainsKey(position)) {
     88        return false;
     89      }
     90
     91      var residualSpaces = CalculateResidualSpace(binPacking, new Vector3D(position));
     92      binPacking.ExtremePoints.Add(position, residualSpaces);
     93      // Check if the existing extreme points are shadowed by the new point
     94      // This is, their residual space fit entirely into the residual space of the new point
     95      foreach (var ep in binPacking.ExtremePoints.Where(x => x.Key != position && new Vector3D(x.Key).IsInside(position, residualSpaces)).ToList()) {
     96        foreach (var residualSpace in ep.Value) {
     97          if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep.Key), residualSpace, position, residualSpaces)) {
    9098            binPacking.ExtremePoints.Remove(ep);
    91             binPacking.ResidualSpaces.Remove(ep);
     99            break;
    92100          }
     101        }         
     102      }
     103      return true;
     104    }
     105
     106    /// <summary>
     107    /// Calculates the residual space for a given bin packing and position.
     108    /// It returns the residual space as a tuple which contains the dimensions
     109    /// </summary>
     110    /// <param name="binPacking"></param>
     111    /// <param name="pos"></param>
     112    /// <returns>A Tuple(width, Height, Depth)</width></returns>
     113    protected override IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
     114      var residualSpaces = new List<ResidualSpace>();
     115      var residualSpace = new ResidualSpace(CalculateResidualSpaceOld(binPacking, pos));
     116      if (!residualSpace.IsZero()) {
     117        residualSpaces.Add(residualSpace);
     118      }
     119      return residualSpaces;
     120    }
     121
     122    protected Tuple<int, int, int> CalculateResidualSpaceOld(BinPacking3D binPacking, Vector3D pos) {
     123
     124      if (pos == null) {
     125        return Tuple.Create(0, 0, 0);
     126      }
     127      var itemPos = binPacking.Items.Select(x => new {
     128        Item = x.Value,
     129        Position = binPacking.Positions[x.Key]
     130      });
     131      Vector3D limit = new Vector3D() {
     132        X = binPacking.BinShape.Width,
     133        Y = binPacking.BinShape.Height,
     134        Z = binPacking.BinShape.Depth
     135      };
     136
     137      if (pos.X < limit.X && pos.Y < limit.Y && pos.Z < limit.Z) {
     138        var rightLimit = ProjectRight(binPacking, pos);
     139        var upLimit = ProjectUp(binPacking, pos);
     140        var forwardLimit = ProjectForward(binPacking, pos);
     141        if (rightLimit.X > 0) {
     142          limit.X = rightLimit.X;
    93143        }
    94         return true;
     144        if (upLimit.Y > 0) {
     145          limit.Y = upLimit.Y;
     146        }
     147        if (forwardLimit.Z > 0) {
     148          limit.Z = forwardLimit.Z;
     149        }
    95150      }
    96       return false;
     151
     152      if (limit.X - pos.X <= 0 || limit.Y - pos.Y <= 0 || limit.Z - pos.Z <= 0) {
     153        return Tuple.Create(0, 0, 0);
     154      }
     155      return Tuple.Create(limit.X - pos.X, limit.Y - pos.Y, limit.Z - pos.Z);
    97156    }
    98157  }
Note: See TracChangeset for help on using the changeset viewer.