Free cookie consent management tool by TermsFeed Policy Generator

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

#2817:

  • Unittests
  • Bugfixes on the line projection based extreme point creation method
File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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}
Note: See TracChangeset for help on using the changeset viewer.