Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
12/13/17 09:47:49 (7 years ago)
Author:
rhanghof
Message:

#2817:

  • Changed the calculation algorithm for creating extreme points by using line based projection
  • Changed the calculation of the residual spaces for line based projection
Location:
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation
Files:
4 edited

Legend:

Unmodified
Added
Removed

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

    r15488 r15520  
    11using HeuristicLab.Common;
    22using HeuristicLab.Problems.BinPacking3D.Geometry;
     3using HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation;
    34using System;
    45using System.Collections.Generic;
    … …  
    1112
    1213
    13     public abstract void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position);
    14 
    15     public abstract void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position);
     14    public void UpdateBinPacking(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
     15      UpdateExtremePoints(binPacking, item, position);
     16      UpdateResidualSpace(binPacking, item, position);
     17    }
     18
     19    protected abstract void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position);
     20
     21    /// <summary>
     22    /// Updates the residual space for a given bin packing
     23    /// </summary>
     24    /// <param name="binPacking"></param>
     25    /// <param name="item"></param>
     26    /// <param name="position"></param>
     27    protected abstract void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position);
    1628    protected abstract bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position);
    1729
    … …  
    2335    /// <param name="newItem"></param>
    2436    /// <param name="position"></param>
    25     protected virtual void GenerateNewExtremePointsForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
     37    protected virtual void GenerateNewExtremePointsForItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
    2638      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
    2739      int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
    … …  
    3547        var below = ProjectDown(binPacking, sourcePoint);
    3648        var residualSpace = CalculateResidualSpace(binPacking, below);
    37         if (IsNonZero(residualSpace)
     49        if (!residualSpace.IsZero()
    3850          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpace)) {
    3951          // add only if the projected point's residual space is not a sub-space
    … …  
    4557        var back = ProjectBackward(binPacking, sourcePoint);
    4658        residualSpace = CalculateResidualSpace(binPacking, back);
    47         if (IsNonZero(residualSpace)
     59        if (!residualSpace.IsZero()
    4860          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpace)) {
    4961          // add only if the projected point's residual space is not a sub-space
    … …  
    6072        var left = ProjectLeft(binPacking, sourcePoint);
    6173        var residualSpace = CalculateResidualSpace(binPacking, left);
    62         if (IsNonZero(residualSpace)
     74        if (!residualSpace.IsZero()
    6375          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpace)) {
    6476          // add only if the projected point's residual space is not a sub-space
    … …  
    7082        var back = ProjectBackward(binPacking, sourcePoint);
    7183        residualSpace = CalculateResidualSpace(binPacking, back);
    72         if (IsNonZero(residualSpace)
     84        if (!residualSpace.IsZero()
    7385          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpace)) {
    7486          // add only if the projected point's residual space is not a sub-space
    … …  
    8597        var below = ProjectDown(binPacking, sourcePoint);
    8698        var residualSpace = CalculateResidualSpace(binPacking, below);
    87         if (IsNonZero(residualSpace)
     99        if (!residualSpace.IsZero()
    88100          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpace)) {
    89101          // add only if the projected point's residual space is not a sub-space
    … …  
    95107        var left = ProjectLeft(binPacking, sourcePoint);
    96108        residualSpace = CalculateResidualSpace(binPacking, left);
    97         if (IsNonZero(residualSpace)
     109        if (!residualSpace.IsZero()
    98110          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpace)) {
    99111          // add only if the projected point's residual space is not a sub-space
    … …  
    171183    #region Residual space
    172184
    173 
    174 
    175     protected virtual bool IsNonZero(Tuple<int, int, int> space) {
    176       return space.Item1 > 0 && space.Item2 > 0 && space.Item3 > 0;
    177     }
    178185
    179186    /// <summary>
    … …  
    184191    /// <param name="residualSpace"></param>
    185192    /// <returns></returns>
    186     protected virtual bool IsWithinResidualSpaceOfAnotherExtremePoint(BinPacking3D binPacking, Vector3D pos, Tuple<int, int, int> residualSpace) {
    187       var eps = binPacking.ExtremePoints.Where(x => !pos.Equals(x) && pos.IsInside(x, binPacking.ResidualSpace[x]));
    188       return eps.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, residualSpace, x, binPacking.ResidualSpace[x]));
    189     }
    190 
    191     /// <summary>
    192     ///
     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]));
     196    }
     197
     198    /// <summary>
     199    /// Returns true, if the given poisition and the related residual space is within the residual space of the given extreme point
    193200    /// </summary>
    194201    /// <param name="pos"></param>
    … …  
    197204    /// <param name="rsEp"></param>
    198205    /// <returns></returns>
    199     protected virtual bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> rsPos, PackingPosition ep, Tuple<int, int, int> rsEp) {
    200       return rsEp.Item1 >= pos.X - ep.X + rsPos.Item1
    201           && rsEp.Item2 >= pos.Y - ep.Y + rsPos.Item2
    202           && rsEp.Item3 >= pos.Z - ep.Z + rsPos.Item3;
     206    protected virtual bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, ResidualSpace rsPos, PackingPosition ep, ResidualSpace rsEp) {
     207      return rsEp.Width >= pos.X - ep.X + rsPos.Width
     208          && rsEp.Height >= pos.Y - ep.Y + rsPos.Height
     209          && rsEp.Depth >= pos.Z - ep.Z + rsPos.Depth;
    203210    }
    204211
    … …  
    210217    /// <param name="pos"></param>
    211218    /// <returns>A Tuple(width, Height, Depth)</width></returns>
    212     protected Tuple<int, int, int> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
     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
    213226      if (pos == null) {
    214227        return Tuple.Create(0, 0, 0);

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

    r15488 r15520  
    1515    /// <param name="item"></param>
    1616    /// <param name="position"></param>
    17     void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position);
     17    void UpdateBinPacking(BinPacking3D binPacking, PackingItem item, PackingPosition position);
    1818
    19     /// <summary>
    20     /// Updates the residual space for a given bin packing
    21     /// </summary>
    22     /// <param name="binPacking"></param>
    23     /// <param name="item"></param>
    24     /// <param name="position"></param>
    25     void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position);
     19   
    2620  }
    2721}

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

    r15488 r15520  
    11using HeuristicLab.Common;
    22using HeuristicLab.Problems.BinPacking3D.Geometry;
     3using HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation;
    34using System;
    45using System.Collections.Generic;
    … …  
    1011  /// <summary>
    1112  /// This extreme point creation class uses the line projection based method for creating extreme points.
     13  /// This projection method enhances the point based projection method by creating extra extreme points on the intersection points of two items.
    1214  /// </summary>
    1315  public class LineProjectionBasedEPCreator : ExtremePointCreator {
    1416
    1517
    16    
    17 
    18     public override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    19       // Before any extreme point for an item can be created, each residual space must be resized if the new item is in the residual space.
    20       // If the residual spaces were not updated, it could be that an extreme point won't be generated because it lies in a residual space which
    21       // size isn't correct anymore.
    22       RecalculateResidualSpaces(binPacking, item, position);
    23 
    24       GenerateNewExtremePointsForNewItem(binPacking, item, position);
    25 
    26       foreach (var ep in GetEpsOnLeft(binPacking, item, position)) {
     18
     19
     20    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
     26      binPacking.ExtremePoints.Clear();
     27      binPacking.ResidualSpaces.Clear();
     28
     29      foreach (var i in binPacking.Items) {
     30        PackingItem it = i.Value;
     31        PackingPosition p = binPacking.Positions[i.Key];
     32        GenerateNewExtremePointsForItem(binPacking, it, p);
     33      }
     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>
     45    protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
     46      if (position == null) {
     47        return false;
     48      }
     49
     50      if (PointIsInItem(binPacking, new Vector3D(position))) {
     51        return false;
     52      }
     53
     54      var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
     55
     56      if (rs.IsZero()) {
     57        return false;
     58      }
     59
     60      if (!binPacking.ExtremePoints.Add(position)) {
     61        return false;
     62      }
     63
     64      binPacking.ResidualSpaces.Add(position, rs);
     65      return true;
     66    }
     67
     68    /// <summary>
     69    /// Getnerates the extreme points for a given item.
     70    /// It creates extreme points by using a point projection based method and
     71    /// creates points by using an edge projection based method.
     72    /// </summary>
     73    /// <param name="binPacking"></param>
     74    /// <param name="newItem"></param>
     75    /// <param name="position"></param>
     76    protected override void GenerateNewExtremePointsForItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
     77      PointProjectionForNewItem(binPacking, newItem, position);
     78      EdgeProjectionForNewItem(binPacking, newItem, position);
     79    }
     80
     81    #region Extreme point creation by using a point projection based method
     82
     83    /// <summary>
     84    /// 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.
     86    /// The direction of the projection depends on position of the point.
     87    /// </summary>
     88    /// <param name="binPacking"></param>
     89    /// <param name="newItem"></param>
     90    /// <param name="position"></param>
     91    private void PointProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
     92      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
     93      int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
     94      var binShape = binPacking.BinShape;
     95      var sourcePoint = new PackingPosition(position.AssignedBin, position.X + newWidth, position.Y, position.Z);
     96      PointProjection(binPacking, sourcePoint, ProjectDown);
     97      PointProjection(binPacking, sourcePoint, ProjectBackward);
     98
     99      sourcePoint = new PackingPosition(position.AssignedBin, position.X, position.Y + newItem.Height, position.Z);
     100      PointProjection(binPacking, sourcePoint, ProjectLeft);
     101      PointProjection(binPacking, sourcePoint, ProjectBackward);
     102
     103      sourcePoint = new PackingPosition(position.AssignedBin, position.X, position.Y, position.Z + newDepth);
     104      PointProjection(binPacking, sourcePoint, ProjectDown);
     105      PointProjection(binPacking, sourcePoint, ProjectLeft);
     106    }
     107
     108
     109    /// <summary>
     110    /// Projects a given point by using the given projection method to the neares item.
     111    /// The given projection method returns a point which lies on a side of the nearest item in the direction.
     112    /// </summary>
     113    /// <param name="binPacking"></param>
     114    /// <param name="position"></param>
     115    /// <param name="projectionMethod"></param>
     116    private void PointProjection(BinPacking3D binPacking, PackingPosition position, Func<BinPacking3D, Vector3D, Vector3D> projectionMethod) {
     117      Vector3D sourcePoint = new Vector3D(position);
     118      if (sourcePoint.X < binPacking.BinShape.Width && sourcePoint.Y < binPacking.BinShape.Height && sourcePoint.Z < binPacking.BinShape.Depth) {
     119        Vector3D point = projectionMethod?.Invoke(binPacking, sourcePoint);
     120        AddExtremePoint(binPacking, new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
     121      }
     122    }
     123    #endregion
     124
     125    #region Extreme point creation by using an edge projection based method
     126
     127    /// <summary>
     128    /// This method creates extreme points be projecting the edges of a given item
     129    ///   - left
     130    ///   - back
     131    ///   - down.
     132    /// A extreme point will be created, if an edge instersects with an edge of another item.
     133    /// </summary>
     134    /// <param name="binPacking"></param>
     135    /// <param name="newItem"></param>
     136    /// <param name="position"></param>
     137    private void EdgeProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
     138      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
     139      int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
     140      var binShape = binPacking.BinShape;
     141
     142      foreach (var ep in GetEpsOnLeft(binPacking, newItem, position)) {
    27143        AddExtremePoint(binPacking, ep);
    28144      }
    29145
    30       foreach (var ep in GetEpsBelow(binPacking, item, position)) {
     146      foreach (var ep in GetEpsBelow(binPacking, newItem, position)) {
    31147        AddExtremePoint(binPacking, ep);
    32148      }
    33149
    34       foreach (var ep in GetEpsBehind(binPacking, item, position)) {
     150      foreach (var ep in GetEpsBehind(binPacking, newItem, position)) {
    35151        AddExtremePoint(binPacking, ep);
    36152      }
    37153    }
    38 
    39     /// <summary>
    40     /// Returns true, if the given poisition and the related residual space is within the residual space of the given extreme point
    41     /// </summary>
    42     /// <param name="pos">New Position</param>
    43     /// <param name="rsPos"></param>
    44     /// <param name="ep"></param>
    45     /// <param name="rsEp"></param>
    46     /// <returns></returns>
    47     protected override bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> rsPos, PackingPosition ep, Tuple<int, int, int> rsEp) {
    48       bool x = pos.X >= ep.X && rsPos.Item1 + pos.X <= rsEp.Item1 + ep.X;
    49       bool y = (pos.Y >= ep.Y && pos.Y == 0 || pos.Y > ep.Y && pos.Y > 0) && rsPos.Item2 + pos.Y <= rsEp.Item2 + ep.Y;
    50       bool z = pos.Z >= ep.Z && rsPos.Item3 + pos.Z <= rsEp.Item3 + ep.Z;
    51       return x && y && z;
    52     }
    53 
    54     public override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    55       foreach (var ep in binPacking.ExtremePoints.ToList()) {
    56         var rs = binPacking.ResidualSpace[ep];
    57         var depth = position.Rotated ? item.Width : item.Depth;
    58         var width = position.Rotated ? item.Depth : item.Width;
    59         var changed = false;
    60         if (ep.Z >= position.Z && ep.Z < position.Z + depth) {
    61           if (ep.X <= position.X && ep.Y >= position.Y && ep.Y < position.Y + item.Height) {
    62             var diff = position.X - ep.X;
    63             var newRSX = Math.Min(rs.Item1, diff);
    64             rs = Tuple.Create(newRSX, rs.Item2, rs.Item3);
    65             changed = true;
    66           }
    67           if (ep.Y <= position.Y && ep.X >= position.X && ep.X < position.X + width) {
    68             var diff = position.Y - ep.Y;
    69             var newRSY = Math.Min(rs.Item2, diff);
    70             rs = Tuple.Create(rs.Item1, newRSY, rs.Item3);
    71             changed = true;
    72           }
    73         }
    74 
    75         if (ep.Z <= position.Z &&
    76             ep.Y >= position.Y && ep.Y < position.Y + item.Height &&
    77             ep.X >= position.X && ep.X < position.X + width) {
    78           var diff = position.Z - ep.Z;
    79           var newRSZ = Math.Min(rs.Item3, diff);
    80           rs = Tuple.Create(rs.Item1, rs.Item2, newRSZ);
    81           changed = true;
    82         }
    83 
    84         if (changed) {
    85           if (IsNonZero(rs) && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) {
    86             binPacking.ResidualSpace[ep] = rs;
    87           } else {
    88             binPacking.ExtremePoints.Remove(ep);
    89             binPacking.ResidualSpace.Remove(ep);
    90           }
    91         }
    92       }
     154    #endregion
     155
     156
     157    protected override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    93158      return;
    94159    }
    95160
    96     protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
    97       if (binPacking.ExtremePoints.Add(position)) {
    98         var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
    99         binPacking.ResidualSpace.Add(position, rs);
    100         // Check if the existing extreme points are shadowed by the new point
    101         // This is, their residual space fit entirely into the residual space of the new point
    102         foreach (var ep in binPacking.ExtremePoints.Where(x => x != position && new Vector3D(x).IsInside(position, rs)).ToList()) {
    103           if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), binPacking.ResidualSpace[ep], position, rs)) {
    104             binPacking.ExtremePoints.Remove(ep);
    105             binPacking.ResidualSpace.Remove(ep);
    106           }
    107         }
    108         return true;
     161    private bool PointIsInItem(BinPacking3D binPacking, Vector3D point) {
     162      foreach (var item in binPacking.Items) {
     163        PackingPosition position = binPacking.Positions[item.Key];
     164        var depth = position.Rotated ? item.Value.Width : item.Value.Depth;
     165        var width = position.Rotated ? item.Value.Depth : item.Value.Width;
     166        if (position.X <= point.X && point.X < position.X + width &&
     167            position.Y <= point.Y && point.Y < position.Y + item.Value.Height &&
     168            position.Z <= point.Z && point.Z < position.Z + depth) {
     169          return true;
     170        }
    109171      }
    110172      return false;
    … …  
    118180    /// <param name="position">Given position</param>
    119181    /// <returns></returns>
    120     private bool ItemIsInRs(KeyValuePair<PackingPosition, Tuple<int, int, int>> rs, PackingItem item, PackingPosition position) {
     182    private bool ItemIsInRs(KeyValuePair<PackingPosition, ResidualSpace> rs, PackingItem item, PackingPosition position) {
    121183      return GetVertices(item, position).Where(pos => pos.IsInside(rs.Key, rs.Value)).Any();
    122184    }
    … …  
    124186    /// <summary>
    125187    /// Recalculates the residual spaces if needed.
    126     /// It checks if an item is in an residual space and if so the residual space will be recalculated
    127     /// </summary>
    128     /// <param name="binPacking"></param>
    129     /// <param name="item"></param>
    130     /// <param name="position"></param>
    131     private void RecalculateResidualSpaces(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    132       var recalculatedSpaces = new Dictionary<PackingPosition, Tuple<int, int, int>>();
    133       foreach (var rs in binPacking.ResidualSpace) {
    134         int width = rs.Value.Item1;
    135         int height = rs.Value.Item2;
    136         int depth = rs.Value.Item3;
    137 
    138         if (ItemIsInRs(rs, item, position)) {
    139           if (rs.Key.X + rs.Value.Item1 > position.X) {
    140             width = position.X - rs.Key.X;
    141           } else if (rs.Key.Y + rs.Value.Item2 > position.Y) {
    142             height = position.Y - rs.Key.Y;
    143           } else if (rs.Key.Z + rs.Value.Item3 > position.Z) {
    144             depth = position.Z - rs.Key.Z;
    145           }
    146         }
    147 
    148         var newRs = new Tuple<int, int, int>(width, height, depth);
    149         if (IsNonZero(newRs)) {
    150           recalculatedSpaces.Add(rs.Key, newRs);
     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);
    151198        } else {
    152           recalculatedSpaces.Add(rs.Key, rs.Value);
    153         }
    154       }
    155       binPacking.ResidualSpace = recalculatedSpaces;
     199          binPacking.ExtremePoints.Remove(ep);
     200        }
     201      }
     202      binPacking.ResidualSpaces = recalculatedSpaces;
     203    }
     204
     205    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
     206      return binPacking.Items.Select(x => new {
     207        Item = x.Value,
     208        Position = binPacking.Positions[x.Key]
     209      }).Where(x => x.Position.Y < position.Y)
     210          .Select(x => Tuple.Create(x.Position, x.Item));
     211    }
     212
     213    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
     214      return binPacking.Items.Select(x => new {
     215        Item = x.Value,
     216        Position = binPacking.Positions[x.Key]
     217      }).Where(x => x.Position.Z < position.Z)
     218          .Select(x => Tuple.Create(x.Position, x.Item));
     219    }
     220
     221    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
     222      return binPacking.Items.Select(x => new {
     223        Item = x.Value,
     224        Position = binPacking.Positions[x.Key]
     225      }).Where(x => x.Position.X < position.X)
     226          .Select(x => Tuple.Create(x.Position, x.Item));
    156227    }
    157228
    … …  
    164235    private IList<PackingPosition> GetEpsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    165236      IList<PackingPosition> eps = new List<PackingPosition>();
    166       IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsOnLeft(binPacking, position);
     237      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsOnLeft(binPacking, item, position);
    167238      var edges = GetProjectionEdgesOnLeft(item, position);
    168239
    169       foreach (var i in items) {
    170         foreach (var edge in edges) {
    171           var newEps = IntersectionsForItem(edge, GetEdgesOnRight(i.Item2, i.Item1));
    172           foreach (var ep in newEps) {
    173             try {
    174               if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
    175                 var point = ProjectLeft(binPacking, ep);
    176                 var residualSpace = CalculateResidualSpace(binPacking, point);
    177                 if (IsNonZero(residualSpace)) {
    178                   eps.Add(new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
    179                 }
    180               }
    181             } catch {
    182               var s = ep;
     240      foreach (var otherItem in items) {
     241        var otherItemEdges = GetEdgesOnRight(otherItem.Item2, otherItem.Item1);
     242        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(1, 0, 0))) {
     243          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
     244            var point = ProjectDown(binPacking, ProjectLeft(binPacking, ep));
     245            var residualSpace = CalculateResidualSpace(binPacking, point);
     246            if (!residualSpace.IsZero()) {
     247              eps.Add(point.ToPackingPosition(position.AssignedBin));
     248            }
     249          }
     250        }
     251        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(1, 0, 0))) {
     252          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
     253            var point = ProjectLeft(binPacking, ep);
     254            var residualSpace = CalculateResidualSpace(binPacking, point);
     255            if (!residualSpace.IsZero()) {
     256              eps.Add(point.ToPackingPosition(position.AssignedBin));
    183257            }
    184258          }
    … …  
    187261      return eps;
    188262    }
     263
    189264
    190265    /// <summary>
    … …  
    199274      var edges = GetProjectionEdgesBelow(item, position);
    200275
    201       foreach (var i in items) {
    202         foreach (var edge in edges) {
    203           var newEps = IntersectionsForItem(edge, GetEdgesOnTop(i.Item2, i.Item1));
    204           foreach (var ep in newEps) {
    205             try {
    206               var point = ProjectDown(binPacking, ep);
    207               var residualSpace = CalculateResidualSpace(binPacking, point);
    208               if (IsNonZero(residualSpace)) {
    209                 eps.Add(new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
    210               }
    211             } catch {
    212               var s = ep;
     276      foreach (var otherItem in items) {
     277        var otherItemEdges = GetEdgesOnTop(otherItem.Item2, otherItem.Item1);
     278        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 1, 0))) {
     279          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
     280            var point = ProjectDown(binPacking, ep);
     281            var residualSpace = CalculateResidualSpace(binPacking, point);
     282            if (!residualSpace.IsZero()) {
     283              eps.Add(point.ToPackingPosition(position.AssignedBin));
     284            }
     285          }
     286        }
     287        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 1, 0))) {
     288          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
     289            var point = ProjectDown(binPacking, ep);
     290            var residualSpace = CalculateResidualSpace(binPacking, point);
     291            if (!residualSpace.IsZero()) {
     292              eps.Add(point.ToPackingPosition(position.AssignedBin));
    213293            }
    214294          }
    … …  
    219299
    220300    /// <summary>
    221     /// Returns the extremepoints on the left side of an given item
     301    /// Returns
    222302    /// </summary>
    223303    /// <param name="item"></param>
    … …  
    229309      var edges = GetProjectionEdgesBehind(item, position);
    230310
    231       foreach (var i in items) {
    232         foreach (var edge in edges) {
    233           var newEps = IntersectionsForItem(edge, GetEdgesInFront(i.Item2, i.Item1));
    234           foreach (var ep in newEps) {
    235             try {
    236               var point = ProjectBackward(binPacking, ep);
    237               var residualSpace = CalculateResidualSpace(binPacking, point);
    238               if (IsNonZero(residualSpace)) {
    239                 eps.Add(new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
    240               }
    241             } catch {
    242               var s = ep;
     311      foreach (var otherItem in items) {
     312        var otherItemEdges = GetEdgesInFront(otherItem.Item2, otherItem.Item1);
     313        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 0, 1))) {
     314          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
     315            var point = ProjectDown(binPacking, ProjectBackward(binPacking, ep));
     316            var residualSpace = CalculateResidualSpace(binPacking, point);
     317            if (!residualSpace.IsZero()) {
     318              eps.Add(point.ToPackingPosition(position.AssignedBin));
     319            }
     320          }
     321        }
     322        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 0, 1))) {
     323          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
     324            var point = ProjectBackward(binPacking, ep);
     325            var residualSpace = CalculateResidualSpace(binPacking, point);
     326            if (!residualSpace.IsZero()) {
     327              eps.Add(point.ToPackingPosition(position.AssignedBin));
    243328            }
    244329          }
    … …  
    367452
    368453    /// <summary>
    369     /// Returns a list of extreme points.
    370     /// </summary>
    371     /// <param name="item"></param>
    372     /// <param name="position"></param>
    373     /// <param name="projectedEdge3D"></param>
    374     /// <returns></returns>
    375     private IEnumerable<Vector3D> IntersectionsForItem(Edge3D projectedEdge, Edge3D[] edges) {
     454    ///
     455    /// </summary>
     456    /// <param name="projectedEdge"></param>
     457    /// <param name="edges"></param>
     458    /// <returns></returns>
     459    private IEnumerable<Vector3D> IntersectionsForItem(Edge3D projectedEdge, Edge3D[] edges, Vector3D direction = null) {
    376460      IList<Vector3D> eps = new List<Vector3D>();
    377461      foreach (var edge in edges) {
    378         var ep = edge.Intersects(projectedEdge);
     462        Edge3D e = projectedEdge;
     463        if (direction != null) {
     464          if (direction.X != 0) {
     465            e.Start.X = edge.Start.X;
     466            e.End.X = edge.End.X;
     467          } else if (direction.Y != 0) {
     468            e.Start.Y = edge.Start.Y;
     469            e.End.Y = edge.End.Y;
     470          } else if (direction.Z != 0) {
     471            e.Start.Z = edge.Start.Z;
     472            e.End.Z = edge.End.Z;
     473          }
     474        }
     475
     476        var ep = edge.Intersects(e);
    379477        if (ep != null) {
    380478          eps.Add(ep);
    … …  
    385483
    386484
     485
    387486    #endregion
    388487
     488   
     489    protected override ResidualSpace CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
     490      return ResidualSpaceCalculatorFactory.CreateCalculator().CalculateResidualSpaces(binPacking, pos).First();
     491    }
    389492  }
     493
     494 
    390495}

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

    r15488 r15520  
    1515  /// </summary>
    1616  public class PointProjectionBasedEPCreator : ExtremePointCreator {
    17     public override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    18       GenerateNewExtremePointsForNewItem(binPacking, item, position);
     17    protected override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
     18      GenerateNewExtremePointsForItem(binPacking, item, position);
    1919
    2020      // if an item is fit in below, before, or left of another its extreme points have to be regenerated
    2121      foreach (var above in GetItemsAbove(binPacking, position)) {
    22         GenerateNewExtremePointsForNewItem(binPacking, above.Item2, above.Item1);
     22        GenerateNewExtremePointsForItem(binPacking, above.Item2, above.Item1);
    2323      }
    2424      foreach (var front in GetItemsInfront(binPacking, position)) {
    25         GenerateNewExtremePointsForNewItem(binPacking, front.Item2, front.Item1);
     25        GenerateNewExtremePointsForItem(binPacking, front.Item2, front.Item1);
    2626      }
    2727      foreach (var right in GetItemsOnRight(binPacking, position)) {
    28         GenerateNewExtremePointsForNewItem(binPacking, right.Item2, right.Item1);
     28        GenerateNewExtremePointsForItem(binPacking, right.Item2, right.Item1);
    2929      }
    3030    }
    3131   
    32     public override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
     32    protected override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    3333      foreach (var ep in binPacking.ExtremePoints.ToList()) {
    34         var rs = binPacking.ResidualSpace[ep];
     34        var rs = binPacking.ResidualSpaces[ep];
    3535        var depth = position.Rotated ? item.Width : item.Depth;
    3636        var width = position.Rotated ? item.Depth : item.Width;
    … …  
    3939          if (ep.X <= position.X && ep.Y >= position.Y && ep.Y < position.Y + item.Height) {
    4040            var diff = position.X - ep.X;
    41             var newRSX = Math.Min(rs.Item1, diff);
    42             rs = Tuple.Create(newRSX, rs.Item2, rs.Item3);
     41            var newRSX = Math.Min(rs.Width, diff);
     42            rs = ResidualSpace.Create(newRSX, rs.Height, rs.Depth);
    4343            changed = true;
    4444          }
    4545          if (ep.Y <= position.Y && ep.X >= position.X && ep.X < position.X + width) {
    4646            var diff = position.Y - ep.Y;
    47             var newRSY = Math.Min(rs.Item2, diff);
    48             rs = Tuple.Create(rs.Item1, newRSY, rs.Item3);
     47            var newRSY = Math.Min(rs.Height, diff);
     48            rs = ResidualSpace.Create(rs.Width, newRSY, rs.Depth);
    4949            changed = true;
    5050          }
    … …  
    5555            ep.X >= position.X && ep.X < position.X + width) {
    5656          var diff = position.Z - ep.Z;
    57           var newRSZ = Math.Min(rs.Item3, diff);
    58           rs = Tuple.Create(rs.Item1, rs.Item2, newRSZ);
     57          var newRSZ = Math.Min(rs.Depth, diff);
     58          rs = ResidualSpace.Create(rs.Width, rs.Height, newRSZ);
    5959          changed = true;
    6060        }
    6161
    6262        if (changed) {
    63           if (IsNonZero(rs) && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) {
    64             binPacking.ResidualSpace[ep] = rs;
     63          if (!rs.IsZero() && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) {
     64            binPacking.ResidualSpaces[ep] = rs;
    6565          } else {
    6666            binPacking.ExtremePoints.Remove(ep);
    67             binPacking.ResidualSpace.Remove(ep);
     67            binPacking.ResidualSpaces.Remove(ep);
    6868          }
    6969        }
    … …  
    8383      if (binPacking.ExtremePoints.Add(position)) {
    8484        var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
    85         binPacking.ResidualSpace.Add(position, rs);
     85        binPacking.ResidualSpaces.Add(position, rs);
    8686        // Check if the existing extreme points are shadowed by the new point
    8787        // This is, their residual space fit entirely into the residual space of the new point
    8888        foreach (var ep in binPacking.ExtremePoints.Where(x => x != position && new Vector3D(x).IsInside(position, rs)).ToList()) {
    89           if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), binPacking.ResidualSpace[ep], position, rs)) {
     89          if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), binPacking.ResidualSpaces[ep], position, rs)) {
    9090            binPacking.ExtremePoints.Remove(ep);
    91             binPacking.ResidualSpace.Remove(ep);
     91            binPacking.ResidualSpaces.Remove(ep);
    9292          }
    9393        }
Note: See TracChangeset for help on using the changeset viewer.