Free cookie consent management tool by TermsFeed Policy Generator

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

#2817

  • Former material is now the layer.
  • Added material enumeration
  • Modification at the minimum residual space left bin packer
Location:
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3
Files:
13 edited

Legend:

Unmodified
Added
Removed

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/2D/BinPacking2D.cs

    r15520 r15705  
    9494        rotated ? item.Width : item.Height,
    9595        item.TargetBin) {
    96         Material = item.Material,
     96        Layer = item.Layer,
    9797        Weight = item.Weight
    9898      };

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/2D/PackingItem.cs

    r14162 r15705  
    4343    }
    4444
    45     public int Material {
    46       get { return ((IFixedValueParameter<IntValue>)Parameters["Material"]).Value.Value; }
    47       set { ((IFixedValueParameter<IntValue>)Parameters["Material"]).Value.Value = value; }
     45    public int Layer {
     46      get { return ((IFixedValueParameter<IntValue>)Parameters["Layer"]).Value.Value; }
     47      set { ((IFixedValueParameter<IntValue>)Parameters["Layer"]).Value.Value = value; }
    4848    }
    4949
    … …  
    6262      Parameters.Add(new ValueParameter<PackingShape>("TargetBin"));
    6363      Parameters.Add(new FixedValueParameter<DoubleValue>("Weight"));
    64       Parameters.Add(new FixedValueParameter<IntValue>("Material"));
     64      Parameters.Add(new FixedValueParameter<IntValue>("Layer"));
    6565    }
    6666
    … …  
    7373
    7474    public bool SupportsStacking(IPackingItem other) {
    75       return ((other.Material < this.Material) || (other.Material.Equals(this.Material) && other.Weight <= this.Weight));
     75      return ((other.Layer < this.Layer) || (other.Layer.Equals(this.Layer) && other.Weight <= this.Weight));
    7676    }
    7777  }

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/2D/ProblemBase.cs

    r14162 r15705  
    4545      BinShape = new PackingShape(20, 16),
    4646      Items = new PackingItem[] {
    47         new PackingItem(3,  8, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    48         new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    49         new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    50         new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    51         new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    52         new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    53         new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    54         new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    55         new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    56         new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    57         new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    58         new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    59         new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    60         new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    61         new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    62         new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    63         new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    64         new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    65         new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    66         new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    67         new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    68         new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    69         new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    70         new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    71         new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    72         new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    73         new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    74         new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    75         new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    76         new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    77         new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    78         new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    79         new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    80         new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    81         new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    82         new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    83         new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0}
     47        new PackingItem(3,  8, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     48        new PackingItem(5,  3, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     49        new PackingItem(9,  3, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     50        new PackingItem(2,  7, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     51        new PackingItem(5,  3, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     52        new PackingItem(9,  3, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     53        new PackingItem(2,  7, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     54        new PackingItem(5,  3, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     55        new PackingItem(9,  3, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     56        new PackingItem(2,  7, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     57        new PackingItem(5,  3, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     58        new PackingItem(9,  3, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     59        new PackingItem(2,  7, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     60        new PackingItem(5,  3, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     61        new PackingItem(9,  3, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     62        new PackingItem(2,  7, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     63        new PackingItem(5,  3, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     64        new PackingItem(9,  3, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     65        new PackingItem(2,  7, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     66        new PackingItem(5,  3, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     67        new PackingItem(9,  3, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     68        new PackingItem(2,  7, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     69        new PackingItem(5,  3, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     70        new PackingItem(9,  3, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     71        new PackingItem(2,  7, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     72        new PackingItem(5,  3, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     73        new PackingItem(9,  3, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     74        new PackingItem(2,  7, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     75        new PackingItem(5,  3, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     76        new PackingItem(9,  3, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     77        new PackingItem(2,  7, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     78        new PackingItem(5,  3, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     79        new PackingItem(9,  3, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     80        new PackingItem(2,  7, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     81        new PackingItem(5,  3, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     82        new PackingItem(9,  3, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0},
     83        new PackingItem(2,  7, new PackingShape(20, 16)) { Layer = 1, Weight = 1.0}
    8484      },
    8585    };

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

    r15646 r15705  
    3737    [Storable]
    3838    public IDictionary<PackingPosition, IEnumerable<ResidualSpace>> ExtremePoints { get; protected set; }
    39 
     39   
    4040
    4141    public BinPacking3D(PackingShape binShape)
    … …  
    5151    protected BinPacking3D(BinPacking3D original, Cloner cloner)
    5252      : base(original, cloner) {
    53 
    5453      this.ExtremePoints = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
    5554      foreach (var extremePoint in original.ExtremePoints) {
    … …  
    5958        }
    6059        ExtremePoints.Add(cloner.Clone(extremePoint.Key), residualSpaces);
    61       }
     60      }     
    6261    }
    6362
    … …  
    7978      ExtremePoints.Remove(position);
    8079    }
    81 
    82     /*
    83     /// <summary>
    84     /// Updates the extreme points of the bin
    85     /// </summary>
    86     /// <param name="item"></param>
    87     /// <param name="position"></param>
    88     /// <param name="stackingConstraints"></param>
    89     public void UpdateExtremePoints(PackingItem item, PackingPosition position, bool stackingConstraints) {
    90       if (stackingConstraints) {
    91         UpdateExtremePointsWithStackingConstriants(item, position);
    92       } else {
    93         UpdateExtremePointsWithoutStackingConstriants(item, position);
    94       }
    95     }*/
    96 
    97 
    98     /*
    99   /// <summary>
    100   /// Updates the extreme points of the bin.
    101   /// As there is no need to project the extreme points to the next side of an item, the extreme points are only generated for the current item.
    102   /// </summary>
    103   /// <param name="item"></param>
    104   /// <param name="position"></param>
    105   private void UpdateExtremePointsWithStackingConstriants(PackingItem newItem, PackingPosition position) {
    106     int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
    107     int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
    108     var ep1 = new PackingPosition(position.AssignedBin, position.X + newWidth, position.Y, position.Z);
    109     var ep2 = new PackingPosition(position.AssignedBin, position.X, position.Y + newItem.Height, position.Z);
    110     var ep3 = new PackingPosition(position.AssignedBin, position.X, position.Y, position.Z + newDepth);
    111     AddExtremePoint(ep1);
    112     AddExtremePoint(ep2);
    113     AddExtremePoint(ep3);
    114   }*/
    115 
    11680
    11781    #region MassPoint
    … …  
    146110        }
    147111      }
    148      
     112
    149113      return Tuple.Create<double, double, double>(packingMassPoint.X, packingMassPoint.Y, packingMassPoint.Z);
    150114    }
    … …  
    316280    }
    317281
    318     /// <summary>
    319     /// Checks if a given the weight of an given item is supportet by the items below.
     282    #region Weight supported
     283    //old implementation
     284    /// <summary>
     285    /// Checks if a given the weight of an given item is supported by the items below.
    320286    /// </summary>
    321287    /// <param name="item"></param>
    … …  
    338304        itemsP4.Where(x => x.Item2.SupportsStacking(item)).Any();
    339305    }
     306
     307    private double CalculateOverlay(Tuple<PackingPosition, PackingItem> item1, Tuple<PackingPosition, PackingItem> item2) {
     308      var left = item1.Item1.X <= item2.Item1.X ? item1 : item2;
     309      var right = item1.Item1.X <= item2.Item1.X ? item2 : item1;
     310      var behind = item1.Item1.Z <= item2.Item1.Z ? item1 : item2;
     311      var inFront = item1.Item1.Z <= item2.Item1.Z ? item2 : item1;
     312
     313      var overlayX = right.Item2.Width;
     314      if (left.Item1.X + left.Item2.Width < right.Item1.X + right.Item2.Width) {
     315        overlayX = left.Item1.X + left.Item2.Width - right.Item1.X;
     316      }
     317
     318      var overlayZ = inFront.Item2.Width;
     319      if (behind.Item1.X + behind.Item2.Width < inFront.Item1.X + inFront.Item2.Width) {
     320        overlayZ = behind.Item1.X + behind.Item2.Width - inFront.Item1.X;
     321      }
     322
     323      return overlayX * overlayZ;
     324    }
     325
     326    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsAboveAnItem(PackingPosition position, PackingItem item) {
     327      var selected = Items.Select(x => new {
     328        Item = x.Value,
     329        Position = Positions[x.Key]
     330      }).Where(x => x.Position.Y == position.Y + item.Height)
     331        .Where(x => x.Position.X <= position.X && x.Position.X + x.Item.Width > position.X ||
     332                    x.Position.X > position.X && x.Position.X < position.X + item.Width)
     333        .Where(x => x.Position.Z <= position.Z && x.Position.Z + x.Item.Height > position.Z ||
     334                    x.Position.Z > position.Z && x.Position.Z < position.Z + item.Height);
     335
     336      return selected.Select(x => Tuple.Create(x.Position, x.Item));
     337    }
     338
     339    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsUnderAnItem(PackingPosition position, PackingItem item) {
     340      var selected = Items.Select(x => new {
     341        Item = x.Value,
     342        Position = Positions[x.Key]
     343      }).Where(x => x.Position.Y + x.Item.Height == position.Y)
     344        .Where(x => x.Position.X <= position.X && x.Position.X + x.Item.Width > position.X ||
     345                    x.Position.X > position.X && x.Position.X < position.X + item.Width)
     346        .Where(x => x.Position.Z <= position.Z && x.Position.Z + x.Item.Height > position.Z ||
     347                    x.Position.Z > position.Z && x.Position.Z < position.Z + item.Height);
     348
     349      return selected.Select(x => Tuple.Create(x.Position, x.Item));
     350    }
     351
     352    #endregion
     353
    340354
    341355    #endregion

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

    r15646 r15705  
    166166    protected override void GenerateNewExtremePointsForItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
    167167      PointProjectionForNewItem(binPacking, newItem, position);
    168       //EdgeProjectionForNewItem(binPacking, newItem, position);
     168      EdgeProjectionForNewItem(binPacking, newItem, position);
    169169    }
    170170

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

    r15617 r15705  
    2222using HeuristicLab.Common;
    2323using HeuristicLab.Problems.BinPacking3D.Geometry;
     24using HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation;
    2425using System;
    2526using System.Collections.Generic;
    … …  
    3637  /// </summary>
    3738  public class PointProjectionBasedEPCreator : ExtremePointCreator {
     39    /// <summary>
     40    /// This lock object is needed because of creating the extreme points in an parallel for loop.
     41    /// </summary>
     42    object _lockAddExtremePoint = new object();
     43
    3844    protected override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    39       GenerateNewExtremePointsForItem(binPacking, item, position);
    40 
    41       // if an item is fit in below, before, or left of another its extreme points have to be regenerated
    42       foreach (var above in GetItemsAbove(binPacking, position)) {
    43         GenerateNewExtremePointsForItem(binPacking, above.Item2, above.Item1);
    44       }
    45       foreach (var front in GetItemsInfront(binPacking, position)) {
    46         GenerateNewExtremePointsForItem(binPacking, front.Item2, front.Item1);
    47       }
    48       foreach (var right in GetItemsOnRight(binPacking, position)) {
    49         GenerateNewExtremePointsForItem(binPacking, right.Item2, right.Item1);
    50       }
    51     }
    52    
     45      binPacking.ExtremePoints.Clear();
     46
     47      // generate all new extreme points parallel. This speeds up the creator.
     48      Parallel.ForEach(binPacking.Items, i => {
     49        PackingItem it = i.Value;
     50        PackingPosition p = binPacking.Positions[i.Key];
     51        GenerateNewExtremePointsForItem(binPacking, it, p);
     52      });
     53
     54      // remove not needed extreme points.
     55      foreach (var extremePoint in binPacking.ExtremePoints.ToList()) {
     56        // check if a residual space can be removed
     57        foreach (var rs in extremePoint.Value.ToList()) {
     58          if (ResidualSpaceCanBeRemoved(binPacking, extremePoint.Key, rs)) {
     59            ((IList<ResidualSpace>)extremePoint.Value).Remove(rs);
     60          }
     61        }
     62        // if the current extreme point has no more residual spaces, it can be removed.
     63        if (((IList<ResidualSpace>)extremePoint.Value).Count <= 0) {
     64          binPacking.ExtremePoints.Remove(extremePoint);
     65        }
     66      }
     67
     68    }
     69
     70    /// <summary>
     71    /// Returns true if a given residual space can be removed.
     72    /// The given residual space can be removed if it is within another residual space and
     73    /// - neither the position of the other residual space and the current extreme point have an item below or
     74    /// - the current extreme point has an item below.
     75    /// </summary>
     76    /// <param name="binPacking"></param>
     77    /// <param name="position"></param>
     78    /// <param name="rs"></param>
     79    /// <returns></returns>
     80    private bool ResidualSpaceCanBeRemoved(BinPacking3D binPacking, PackingPosition position, ResidualSpace rs) {
     81      foreach (var extremePoint in binPacking.ExtremePoints) {
     82        if (position.Equals(extremePoint.Key)) {
     83          continue;
     84        }
     85        if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(position), rs, extremePoint.Key, extremePoint.Value)) {
     86          var itemBelowEp = LiesOnAnyItem(binPacking, extremePoint.Key);
     87          var itemBelowPos = LiesOnAnyItem(binPacking, position);
     88
     89          if (itemBelowEp || !itemBelowEp && !itemBelowPos) {
     90            return true;
     91          }
     92        }
     93      }
     94      return false;
     95    }
     96
     97    /// <summary>
     98    /// Returns true if the given position lies on an item or an the ground.
     99    /// </summary>
     100    /// <param name="binPacking"></param>
     101    /// <param name="position"></param>
     102    /// <returns></returns>
     103    private bool LiesOnAnyItem(BinPacking3D binPacking, PackingPosition position) {
     104      if (position.Y == 0) {
     105        return true;
     106      }
     107
     108      var items = binPacking.Items.Where(x => {
     109        var itemPosition = binPacking.Positions[x.Key];
     110        var item = x.Value;
     111        int width = item.Width;
     112        int depth = item.Depth;
     113
     114        return itemPosition.Y + item.Height == position.Y &&
     115               itemPosition.X <= position.X && position.X < itemPosition.X + width &&
     116               itemPosition.Z <= position.Z && position.Z < itemPosition.Z + depth;
     117      });
     118
     119      return items.Count() > 0;
     120    }
     121
     122
     123    /// <summary>
     124    /// Adds a new extreme point an the related residual spaces to a given bin packing.
     125    /// - The given position has to be valid.
     126    /// - The extreme point does not exist in the bin packing.
     127    /// - There must be at minimum one valid residual space. A residual space is invalid if the space is zero.
     128    /// </summary>
     129    /// <param name="binPacking"></param>
     130    /// <param name="position"></param>
     131    /// <returns>True = the given point and its related residual spaces were successfully added to the bin packing</returns>
     132    protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
     133      if (position == null) {
     134        return false;
     135      }
     136
     137      if (PointIsInAnyItem(binPacking, new Vector3D(position))) {
     138        return false;
     139      }
     140
     141      // this is necessary if the extreme points are being created in a parallel loop.
     142      lock (_lockAddExtremePoint) {
     143        if (binPacking.ExtremePoints.ContainsKey(position)) {
     144          return false;
     145        }
     146
     147        var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
     148
     149        if (rs.Count() <= 0) {
     150          return false;
     151        }
     152
     153        binPacking.ExtremePoints.Add(position, rs);
     154        return true;
     155      }
     156    }
     157
     158    /// <summary>
     159    /// Getnerates the extreme points for a given item.
     160    /// It creates extreme points by using a point projection based method and
     161    /// creates points by using an edge projection based method.
     162    /// </summary>
     163    /// <param name="binPacking"></param>
     164    /// <param name="newItem"></param>
     165    /// <param name="position"></param>
     166    protected override void GenerateNewExtremePointsForItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
     167      PointProjectionForNewItem(binPacking, newItem, position);
     168    }
     169
     170    #region Extreme point creation by using a point projection based method
     171
     172    /// <summary>
     173    /// This method creates extreme points by using a point projection based method.
     174    /// For each item there will be created three points and each of the points will be projected twice.
     175    /// The direction of the projection depends on position of the point.
     176    /// </summary>
     177    /// <param name="binPacking"></param>
     178    /// <param name="newItem"></param>
     179    /// <param name="position"></param>
     180    private void PointProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
     181      int newWidth = newItem.Width;
     182      int newDepth = newItem.Depth;
     183      var binShape = binPacking.BinShape;
     184      var sourcePoint = new PackingPosition(position.AssignedBin, position.X + newWidth, position.Y, position.Z);
     185      PointProjection(binPacking, sourcePoint, ProjectDown);
     186      PointProjection(binPacking, sourcePoint, ProjectBackward);
     187
     188      sourcePoint = new PackingPosition(position.AssignedBin, position.X, position.Y + newItem.Height, position.Z);
     189      PointProjection(binPacking, sourcePoint, ProjectLeft);
     190      PointProjection(binPacking, sourcePoint, ProjectBackward);
     191
     192      sourcePoint = new PackingPosition(position.AssignedBin, position.X, position.Y, position.Z + newDepth);
     193      PointProjection(binPacking, sourcePoint, ProjectDown);
     194      PointProjection(binPacking, sourcePoint, ProjectLeft);
     195    }
     196
     197
     198    /// <summary>
     199    /// Projects a given point by using the given projection method to the neares item.
     200    /// The given projection method returns a point which lies on a side of the nearest item in the direction.
     201    /// </summary>
     202    /// <param name="binPacking"></param>
     203    /// <param name="position"></param>
     204    /// <param name="projectionMethod"></param>
     205    private void PointProjection(BinPacking3D binPacking, PackingPosition position, Func<BinPacking3D, Vector3D, Vector3D> projectionMethod) {
     206      Vector3D sourcePoint = new Vector3D(position);
     207      if (sourcePoint.X < binPacking.BinShape.Width && sourcePoint.Y < binPacking.BinShape.Height && sourcePoint.Z < binPacking.BinShape.Depth) {
     208        Vector3D point = projectionMethod?.Invoke(binPacking, sourcePoint);
     209        if (point != null) {
     210          AddExtremePoint(binPacking, new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
     211        }
     212      }
     213    }
     214    #endregion
     215
     216    #region Extreme point creation by using an edge projection based method
     217
     218    /// <summary>
     219    /// This method creates extreme points be projecting the edges of a given item
     220    ///   - left
     221    ///   - back
     222    ///   - down.
     223    /// A extreme point will be created, if an edge instersects with an edge of another item.
     224    /// </summary>
     225    /// <param name="binPacking"></param>
     226    /// <param name="newItem"></param>
     227    /// <param name="position"></param>
     228    private void EdgeProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
     229      int newWidth = newItem.Width;
     230      int newDepth = newItem.Depth;
     231      var binShape = binPacking.BinShape;
     232
     233      foreach (var ep in GetEpsOnLeft(binPacking, newItem, position)) {
     234        AddExtremePoint(binPacking, ep.Key);
     235      }
     236
     237      foreach (var ep in GetEpsBelow(binPacking, newItem, position)) {
     238        AddExtremePoint(binPacking, ep.Key);
     239      }
     240
     241      foreach (var ep in GetEpsBehind(binPacking, newItem, position)) {
     242        AddExtremePoint(binPacking, ep.Key);
     243      }
     244    }
     245    #endregion
     246
     247    /// <summary>
     248    /// Updates the residual spaces.
     249    /// It removes not needed ones.
     250    /// A residual space will be removed if the space is a subspace of another one and
     251    /// the current one has no item below or both have an item below.
     252    /// </summary>
     253    /// <param name="binPacking"></param>
     254    /// <param name="item"></param>
     255    /// <param name="position"></param>
    53256    protected override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    54       foreach (var extremePoint in binPacking.ExtremePoints.ToList()) {
    55         var ep = extremePoint.Key;
    56         var residualSpaces = extremePoint.Value as IList<ResidualSpace>;
    57         for (int i = 0; i < residualSpaces.Count(); i++) {
    58           var rs = residualSpaces[i];
    59           var depth = item.Depth;
    60           var width = item.Width;
    61           var changed = false;
    62           if (ep.Z >= position.Z && ep.Z < position.Z + depth) {
    63             if (ep.X <= position.X && ep.Y >= position.Y && ep.Y < position.Y + item.Height) {
    64               var diff = position.X - ep.X;
    65               var newRSX = Math.Min(rs.Width, diff);
    66               rs = ResidualSpace.Create(newRSX, rs.Height, rs.Depth);
    67               changed = true;
    68             }
    69             if (ep.Y <= position.Y && ep.X >= position.X && ep.X < position.X + width) {
    70               var diff = position.Y - ep.Y;
    71               var newRSY = Math.Min(rs.Height, diff);
    72               rs = ResidualSpace.Create(rs.Width, newRSY, rs.Depth);
    73               changed = true;
    74             }
    75           }
    76 
    77           if (ep.Z <= position.Z &&
    78               ep.Y >= position.Y && ep.Y < position.Y + item.Height &&
    79               ep.X >= position.X && ep.X < position.X + width) {
    80             var diff = position.Z - ep.Z;
    81             var newRSZ = Math.Min(rs.Depth, diff);
    82             rs = ResidualSpace.Create(rs.Width, rs.Height, newRSZ);
    83             changed = true;
    84           }
    85 
    86           if (changed) {
    87             if (!rs.IsZero() && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) {
    88               residualSpaces[i] = rs;
    89             } else {
    90               binPacking.ExtremePoints.Remove(ep);
    91               break;
    92             }
    93           }
    94         }       
    95       }
    96       return;
    97     }
    98    
    99     /// <summary>
    100     /// Adds an extreme point to a given bin packing.
    101     /// It also adds the residual space for the new extreme point
    102     /// and removes the extreme point and the related residual space for the given position which are not needed anymore.
    103     /// </summary>
    104     /// <param name="binPacking"></param>
    105     /// <param name="position"></param>
    106     /// <returns></returns>
    107     protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
    108       if (binPacking.ExtremePoints.ContainsKey(position)) {
    109         return false;
    110       }
    111 
    112       var residualSpaces = CalculateResidualSpace(binPacking, new Vector3D(position));
    113       binPacking.ExtremePoints.Add(position, residualSpaces);
    114       // Check if the existing extreme points are shadowed by the new point
    115       // This is, their residual space fit entirely into the residual space of the new point
    116       foreach (var ep in binPacking.ExtremePoints.Where(x => x.Key != position && new Vector3D(x.Key).IsInside(position, residualSpaces)).ToList()) {
    117         foreach (var residualSpace in ep.Value) {
    118           if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep.Key), residualSpace, position, residualSpaces)) {
    119             binPacking.ExtremePoints.Remove(ep);
    120             break;
    121           }
    122         }         
    123       }
    124       return true;
    125     }
    126 
    127     /// <summary>
    128     /// Calculates the residual space for a given bin packing and position.
    129     /// It returns the residual space as a tuple which contains the dimensions
    130     /// </summary>
    131     /// <param name="binPacking"></param>
    132     /// <param name="pos"></param>
    133     /// <returns>A Tuple(width, Height, Depth)</width></returns>
    134     protected override IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
    135       var residualSpaces = new List<ResidualSpace>();
    136       var residualSpace = new ResidualSpace(CalculateResidualSpaceOld(binPacking, pos));
    137       if (!residualSpace.IsZero()) {
    138         residualSpaces.Add(residualSpace);
    139       }
    140       return residualSpaces;
    141     }
    142 
    143     protected Tuple<int, int, int> CalculateResidualSpaceOld(BinPacking3D binPacking, Vector3D pos) {
    144 
    145       if (pos == null) {
    146         return Tuple.Create(0, 0, 0);
    147       }
    148       var itemPos = binPacking.Items.Select(x => new {
     257    }
     258
     259    /// <summary>
     260    /// Returns true if any item in the bin packing encapsulates the given point
     261    /// </summary>
     262    /// <param name="binPacking"></param>
     263    /// <param name="point"></param>
     264    /// <returns></returns>
     265    private bool PointIsInAnyItem(BinPacking3D binPacking, Vector3D point) {
     266      foreach (var item in binPacking.Items) {
     267        PackingPosition position = binPacking.Positions[item.Key];
     268        var depth = item.Value.Depth;
     269        var width = item.Value.Width;
     270        if (position.X <= point.X && point.X < position.X + width &&
     271            position.Y <= point.Y && point.Y < position.Y + item.Value.Height &&
     272            position.Z <= point.Z && point.Z < position.Z + depth) {
     273          return true;
     274        }
     275      }
     276      return false;
     277    }
     278
     279    /// <summary>
     280    /// Returns true if an item is in the residual space of a given extrem point
     281    /// </summary>
     282    /// <param name="rs">KeyValuePair with the position of the extreme point and the size of the residual space</param>
     283    /// <param name="item">Given Item</param>
     284    /// <param name="position">Given position</param>
     285    /// <returns></returns>
     286    private bool ItemIsInRs(KeyValuePair<PackingPosition, ResidualSpace> rs, PackingItem item, PackingPosition position) {
     287      return GetVertices(item, position).Where(pos => pos.IsInside(rs.Key, rs.Value)).Any();
     288    }
     289
     290    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
     291      return binPacking.Items.Select(x => new {
    149292        Item = x.Value,
    150293        Position = binPacking.Positions[x.Key]
    151       });
    152       Vector3D limit = new Vector3D() {
    153         X = binPacking.BinShape.Width,
    154         Y = binPacking.BinShape.Height,
    155         Z = binPacking.BinShape.Depth
     294      }).Where(x => x.Position.Y < position.Y)
     295          .Select(x => Tuple.Create(x.Position, x.Item));
     296    }
     297
     298    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
     299      return binPacking.Items.Select(x => new {
     300        Item = x.Value,
     301        Position = binPacking.Positions[x.Key]
     302      }).Where(x => x.Position.Z < position.Z)
     303          .Select(x => Tuple.Create(x.Position, x.Item));
     304    }
     305
     306    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
     307      return binPacking.Items.Select(x => new {
     308        Item = x.Value,
     309        Position = binPacking.Positions[x.Key]
     310      }).Where(x => x.Position.X < position.X)
     311          .Select(x => Tuple.Create(x.Position, x.Item));
     312    }
     313
     314    /// <summary>
     315    /// Returns the extreme points and its related residual spaces on the left side of an given item.
     316    /// This extreme points are being created by intersecting two edges on the left side of the given item
     317    /// (left - in front, left - on top) with all edges on the right side of all other items int the bin packing.
     318    /// </summary>
     319    /// <param name="item"></param>
     320    /// <param name="position"></param>
     321    /// <returns></returns>
     322    private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
     323      var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
     324      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsOnLeft(binPacking, item, position);
     325      var edges = GetProjectionEdgesOnLeft(item, position);
     326
     327      foreach (var otherItem in items) {
     328        if (position.Equals(otherItem.Item1)) {
     329          continue;
     330        }
     331
     332        var otherItemEdges = GetEdgesOnRight(otherItem.Item2, otherItem.Item1);
     333        // left - in front
     334        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(1, 0, 0))) {
     335          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
     336            // As this edge has a vertical direction, every point of intersection won't have an item below.
     337            // So finally it is being projected down.
     338            var point = ProjectDown(binPacking, ProjectLeft(binPacking, ep));
     339            var residualSpaces = CalculateResidualSpace(binPacking, point);
     340            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
     341            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
     342              eps.Add(newExtremePoint, residualSpaces);
     343            }
     344          }
     345        }
     346
     347        // left - on top
     348        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(1, 0, 0))) {
     349          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
     350            var point = ProjectLeft(binPacking, ep);
     351            var residualSpaces = CalculateResidualSpace(binPacking, point);
     352            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
     353            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
     354              eps.Add(newExtremePoint, residualSpaces);
     355            }
     356          }
     357        }
     358      }
     359      return eps;
     360    }
     361
     362
     363    /// <summary>
     364    /// Returns the extreme points and its related residual spaces below of an given item.
     365    /// This extreme points are being created by intersecting two edges below of the given item
     366    /// (below - in front, below - right) with all edges on top side of all other items int the bin packing.
     367    /// </summary>
     368    /// <param name="item"></param>
     369    /// <param name="position"></param>
     370    /// <returns></returns>
     371    private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
     372      var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
     373      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBelow(binPacking, position);
     374      var edges = GetProjectionEdgesBelow(item, position);
     375
     376      foreach (var otherItem in items) {
     377        if (position.Equals(otherItem.Item1)) {
     378          continue;
     379        }
     380
     381        var otherItemEdges = GetEdgesOnTop(otherItem.Item2, otherItem.Item1);
     382        // below - in front
     383        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 1, 0))) {
     384          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
     385            var point = ProjectDown(binPacking, ep);
     386            var residualSpaces = CalculateResidualSpace(binPacking, point);
     387            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
     388            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
     389              eps.Add(newExtremePoint, residualSpaces);
     390            }
     391          }
     392        }
     393
     394        // below - right
     395        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 1, 0))) {
     396          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
     397            var point = ProjectDown(binPacking, ep);
     398            var residualSpaces = CalculateResidualSpace(binPacking, point);
     399            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
     400            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
     401              eps.Add(newExtremePoint, residualSpaces);
     402            }
     403          }
     404        }
     405      }
     406      return eps;
     407    }
     408
     409    /// <summary>
     410    /// Returns the extreme points and its related residual spaces below of an given item.
     411    /// This extreme points are being created by intersecting two edges below of the given item
     412    /// (right - behind, on top - behind) with all edges on top side of all other items int the bin packing.
     413    /// </summary>
     414    /// <param name="item"></param>
     415    /// <param name="position"></param>
     416    /// <returns></returns>
     417    private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
     418      var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
     419      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBehind(binPacking, position);
     420      var edges = GetProjectionEdgesBehind(item, position);
     421
     422      foreach (var otherItem in items) {
     423        if (position.Equals(otherItem.Item1)) {
     424          continue;
     425        }
     426
     427        var otherItemEdges = GetEdgesInFront(otherItem.Item2, otherItem.Item1);
     428        // right - behind
     429        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 0, 1))) {
     430          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
     431            // As this edge has a vertical direction, every point of intersection won't have an item below.
     432            // So finally it is being projected down.
     433            var point = ProjectDown(binPacking, ProjectBackward(binPacking, ep));
     434            var residualSpaces = CalculateResidualSpace(binPacking, point);
     435            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
     436            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
     437              eps.Add(newExtremePoint, residualSpaces);
     438            }
     439          }
     440        }
     441
     442        // on top - behind
     443        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 0, 1))) {
     444          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
     445            var point = ProjectBackward(binPacking, ep);
     446            var residualSpaces = CalculateResidualSpace(binPacking, point);
     447            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
     448            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
     449              eps.Add(newExtremePoint, residualSpaces);
     450            }
     451          }
     452        }
     453      }
     454      return eps;
     455    }
     456
     457    #region Methods for getting the edges for items
     458
     459    /// <summary>
     460    /// Returns an array of packing position which represents the vertices of an item.
     461    /// The position of a vertex in the array is mapped to an item as followed:
     462    ///      4----------5
     463    ///     /|         /|
     464    ///    / |        / |
     465    ///   /  0-------/--1
     466    ///  6--/-------7  /
     467    ///  | /        | /
     468    ///  |/         |/
     469    ///  2----------3
     470    /// 
     471    ///  0 = (0,0,0)
     472    /// </summary>
     473    /// <param name="item"></param>
     474    /// <param name="position"></param>
     475    /// <returns></returns>
     476    private Vector3D[] GetVertices(PackingItem item, PackingPosition position) {
     477      int width = item.Width;
     478      int depth = item.Depth;
     479      return new Vector3D[] {
     480        new Vector3D(position.X + 0,     position.Y + 0,           position.Z + 0), // (0,0,0)
     481        new Vector3D(position.X + width, position.Y + 0,           position.Z + 0), // (x,0,0)
     482        new Vector3D(position.X + 0,     position.Y + 0,           position.Z + depth), // (0,0,z)
     483        new Vector3D(position.X + width, position.Y + 0,           position.Z + depth), // (x,0,z)
     484
     485        new Vector3D(position.X + 0,     position.Y + item.Height, position.Z + 0), // (0,y,0)
     486        new Vector3D(position.X + width, position.Y + item.Height, position.Z + 0), // (x,y,0)
     487        new Vector3D(position.X + 0,     position.Y + item.Height, position.Z + depth), // (0,y,z)
     488        new Vector3D(position.X + width, position.Y + item.Height, position.Z + depth), //(x,y,z)
    156489      };
    157 
    158       if (pos.X < limit.X && pos.Y < limit.Y && pos.Z < limit.Z) {
    159         var rightLimit = ProjectRight(binPacking, pos);
    160         var upLimit = ProjectUp(binPacking, pos);
    161         var forwardLimit = ProjectForward(binPacking, pos);
    162         if (rightLimit.X > 0) {
    163           limit.X = rightLimit.X;
    164         }
    165         if (upLimit.Y > 0) {
    166           limit.Y = upLimit.Y;
    167         }
    168         if (forwardLimit.Z > 0) {
    169           limit.Z = forwardLimit.Z;
    170         }
    171       }
    172 
    173       if (limit.X - pos.X <= 0 || limit.Y - pos.Y <= 0 || limit.Z - pos.Z <= 0) {
    174         return Tuple.Create(0, 0, 0);
    175       }
    176       return Tuple.Create(limit.X - pos.X, limit.Y - pos.Y, limit.Z - pos.Z);
     490    }
     491
     492    private Edge3D[] GetProjectionEdgesOnLeft(PackingItem item, PackingPosition position) {
     493      Vector3D[] points = GetVertices(item, position);
     494
     495      return new Edge3D[] {
     496        new Edge3D(points[2], points[6]),
     497        new Edge3D(points[6], points[4])
     498      };
     499    }
     500
     501    private Edge3D[] GetProjectionEdgesBelow(PackingItem item, PackingPosition position) {
     502      Vector3D[] points = GetVertices(item, position);
     503
     504      return new Edge3D[] {
     505        new Edge3D(points[2], points[3]),
     506        new Edge3D(points[3], points[1])
     507      };
     508    }
     509
     510    private Edge3D[] GetProjectionEdgesBehind(PackingItem item, PackingPosition position) {
     511      Vector3D[] points = GetVertices(item, position);
     512
     513      return new Edge3D[] {
     514        new Edge3D(points[1], points[5]),
     515        new Edge3D(points[5], points[4])
     516      };
     517    }
     518
     519    /// <summary>
     520    /// Returns an array of edges which contains all edges of the rigth side of an given item.
     521    /// </summary>
     522    /// <param name="item"></param>
     523    /// <param name="position"></param>
     524    /// <returns></returns>
     525    private Edge3D[] GetEdgesOnRight(PackingItem item, PackingPosition position) {
     526      Vector3D[] points = GetVertices(item, position);
     527
     528      return new Edge3D[] {
     529        new Edge3D(points[1], points[5]),
     530        new Edge3D(points[5], points[7]),
     531        new Edge3D(points[7], points[3]),
     532        new Edge3D(points[3], points[1])
     533      };
     534    }
     535
     536    /// <summary>
     537    /// Returns an array of edges which contains all edges on the top of an given item.
     538    /// </summary>
     539    /// <param name="item"></param>
     540    /// <param name="position"></param>
     541    /// <returns></returns>
     542    private Edge3D[] GetEdgesOnTop(PackingItem item, PackingPosition position) {
     543      Vector3D[] points = GetVertices(item, position);
     544
     545      return new Edge3D[] {
     546        new Edge3D(points[4], points[5]),
     547        new Edge3D(points[5], points[7]),
     548        new Edge3D(points[7], points[6]),
     549        new Edge3D(points[6], points[4])
     550      };
     551    }
     552
     553    /// <summary>
     554    /// Returns an array of edges which contains all edges in front of an given item.
     555    /// </summary>
     556    /// <param name="item"></param>
     557    /// <param name="position"></param>
     558    /// <returns></returns>
     559    private Edge3D[] GetEdgesInFront(PackingItem item, PackingPosition position) {
     560      Vector3D[] points = GetVertices(item, position);
     561
     562      return new Edge3D[] {
     563        new Edge3D(points[2], points[3]),
     564        new Edge3D(points[3], points[7]),
     565        new Edge3D(points[7], points[6]),
     566        new Edge3D(points[6], points[2])
     567      };
     568    }
     569
     570    #endregion
     571
     572
     573    #region Intersections
     574
     575    /// <summary>
     576    /// Returns a collection of points where a given edge (projectedEdge) intersects with other edges.
     577    /// The given edge (projectedEdge) will be projected by using the given vector direction
     578    /// and a edge of the given edge collection.
     579    /// The returned collecten can be empty.
     580    /// </summary>
     581    /// <param name="projectedEdge"></param>
     582    /// <param name="edges"></param>
     583    /// <param name="direction"></param>
     584    /// <returns></returns>
     585    private IEnumerable<Vector3D> IntersectionsForItem(Edge3D projectedEdge, Edge3D[] edges, Vector3D direction = null) {
     586      IList<Vector3D> eps = new List<Vector3D>();
     587      foreach (var edge in edges) {
     588        Edge3D e = projectedEdge;
     589        if (direction != null) {
     590          if (direction.X != 0) {
     591            e.Start.X = edge.Start.X;
     592            e.End.X = edge.End.X;
     593          } else if (direction.Y != 0) {
     594            e.Start.Y = edge.Start.Y;
     595            e.End.Y = edge.End.Y;
     596          } else if (direction.Z != 0) {
     597            e.Start.Z = edge.Start.Z;
     598            e.End.Z = edge.End.Z;
     599          }
     600        }
     601
     602        var ep = edge.Intersects(e);
     603        if (ep != null) {
     604          eps.Add(ep);
     605        }
     606      }
     607
     608      return eps as IEnumerable<Vector3D>;
     609    }
     610
     611
     612
     613    #endregion
     614
     615    /// <summary>
     616    /// Calculates the residual spaces for an extreme point.
     617    /// </summary>
     618    /// <param name="binPacking"></param>
     619    /// <param name="pos"></param>
     620    /// <returns></returns>
     621    protected override IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
     622      return ResidualSpaceCalculatorFactory.CreateCalculator().CalculateResidualSpaces(binPacking, pos);
    177623    }
    178624  }

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Material/MaterialType.cs

    r15646 r15705  
    66
    77namespace HeuristicLab.Problems.BinPacking3D.Material {
     8 
    89  public enum MaterialType {
    9     Wooden,
     10    EuroPallet,
     11    Wood,
    1012    Steel,
    1113    Paperboard

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPacker.cs

    r15652 r15705  
    9494        packingItem.Height,
    9595        packingItem.Depth,
    96         packingItem.TargetBin, packingItem.Weight, packingItem.Material);
     96        packingItem.TargetBin, packingItem.Weight, packingItem.Layer);
    9797
    9898      // The extremepoints are sortet by Y / Z / X

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerMinRSLeft.cs

    r15652 r15705  
    6363          BinPacking3D packingBin = new BinPacking3D(binShape);
    6464          PackRemainingItems(ref remainingIds, ref packingBin, workingItems, epCreationMethod, useStackingConstraints);
    65           packingList.Add(packingBin);         
     65          packingList.Add(packingBin);
    6666        }
    6767      } catch (BinPacking3DException e) {
    … …  
    105105    protected void PackRemainingItems(ref IList<int> remainingIds, ref BinPacking3D packingBin, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, bool useStackingConstraints) {
    106106      IExtremePointCreator extremePointCreator = ExtremePointCreatorFactory.CreateExtremePointCreator(epCreationMethod, useStackingConstraints);
    107       var remainingNotStackableItems = new List<int>();
     107      var remainingNotWeightSupportedItems = new List<int>();
    108108      foreach (var itemId in new List<int>(remainingIds)) {
    109109        var item = items[itemId];
    110110
    111         // If an item is not stackable it should have a minimum waste of the residual space.
    112         // As long as there are stackable items left, put the non stackable items into a collection
     111        // If an item doesn't support any weight it should have a minimum waste of the residual space.
     112        // As long as there are weight supporting items left, put the non supporting items into a collection
    113113        // and try to find positions where they don't waste too much space.
    114         // If there are no stackable items left the non stackable have to be treated as a stackable one.
    115         if (!item.IsStackabel && useStackingConstraints && remainingIds.Where(x => items[x].IsStackabel).Any()) {
    116           remainingNotStackableItems.Add(itemId);         
    117         } else {
     114        // If there are no weight supporting items left the non supporting ones have to be treated as a supporting one.
     115        if (item.SupportedWeight <= 0 && useStackingConstraints && remainingIds.Any(x => items[x].SupportedWeight > 0)) {
     116          remainingNotWeightSupportedItems.Add(itemId);
     117        } else if (!item.IsStackabel) {
     118          PackingPosition position = FindPackingPositionForNotStackableItem(packingBin, item, useStackingConstraints);
     119          // if a valid packing position could be found, the current item can be added to the given bin
     120          if (position != null) {
     121            PackItem(packingBin, itemId, item, position, extremePointCreator, useStackingConstraints);
     122            remainingIds.Remove(itemId);
     123          }
     124        } else  {
    118125          PackingPosition position = FindPackingPositionForItem(packingBin, item, useStackingConstraints);
    119126          // if a valid packing position could be found, the current item can be added to the given bin
    120           if (position != null) {           
     127          if (position != null) {
    121128            PackItem(packingBin, itemId, item, position, extremePointCreator, useStackingConstraints);
    122129            remainingIds.Remove(itemId);
    … …  
    124131        }
    125132
    126         // try to find a valid position for a non stackable item
    127         var stackableLeft = remainingIds.Where(x => items[x].IsStackabel).Any();
    128         foreach (var saId in new List<int>(remainingNotStackableItems)) {
     133        // try to find a valid position for a non weight supporting item
     134        var weightSupportedLeft = remainingIds.Any(x => items[x].SupportedWeight > 0);
     135        foreach (var saId in new List<int>(remainingNotWeightSupportedItems)) {
    129136          item = items[saId];
    130137          PackingPosition position = null;
    131           if (stackableLeft) {
    132             position  = FindPackingPositionForNotStackableItem(packingBin, item, useStackingConstraints);
     138          if (weightSupportedLeft) {
     139            position = FindPackingPositionForWeightUnsupportedItem(packingBin, item, useStackingConstraints);
    133140          } else {
    134141            position = FindPackingPositionForItem(packingBin, item, useStackingConstraints);
    135142          }
    136          
    137           if (position != null) {           
     143
     144          if (position != null) {
    138145            PackItem(packingBin, saId, item, position, extremePointCreator, useStackingConstraints);
    139146            remainingIds.Remove(saId);
    140             remainingNotStackableItems.Remove(saId);
    141           }
    142         }
    143        
    144       }
     147            remainingNotWeightSupportedItems.Remove(saId);
     148          }
     149        }
     150
     151      }
     152    }
     153
     154    /// <summary>
     155    /// Finds a valid packing position for a not stackable item.
     156    /// Not stackable means that an item can't be placed on another one and no other item can be placed on it.
     157    /// The item will be rotated and tilted so it needs the minimum area.
     158    /// </summary>
     159    /// <param name="packingBin"></param>
     160    /// <param name="packingItem"></param>
     161    /// <param name="useStackingConstraints"></param>
     162    /// <returns></returns>
     163    private PackingPosition FindPackingPositionForNotStackableItem(BinPacking3D packingBin, PackingItem packingItem, bool useStackingConstraints) {
     164      if (!useStackingConstraints) {
     165        return FindPackingPositionForItem(packingBin, packingItem, useStackingConstraints);
     166      }
     167      var areas = new List<Tuple<double, bool, bool>>();
     168      areas.Add(CalculateArea(packingItem, false, false));
     169      if (packingItem.TiltEnabled) {
     170        areas.Add(CalculateArea(packingItem, false, true));
     171      }
     172      if (packingItem.RotateEnabled) {
     173        areas.Add(CalculateArea(packingItem, true, false));
     174      }
     175      if (packingItem.RotateEnabled && packingItem.TiltEnabled) {
     176        areas.Add(CalculateArea(packingItem, true, true));
     177      }
     178
     179      areas.Sort((x1, x2) => (int)(x1.Item1 - x2.Item1));
     180      var orientation = areas.FirstOrDefault();
     181      if (orientation == null) {
     182        return null;
     183      }
     184
     185
     186      PackingItem newItem = new PackingItem(packingItem) {
     187        Rotated = orientation.Item2,
     188        Tilted = orientation.Item3
     189      };
     190
     191      var rsds = new SortedSet<ResidualSpaceDifference>();
     192      foreach (var ep in packingBin.ExtremePoints.Where(x => x.Key.Y == 0)) {
     193        var position = ep.Key;
     194        foreach (var rs in ep.Value) {
     195          var rsd = ResidualSpaceDifference.Create(position, newItem, rs);
     196          if (rsd != null) {
     197            rsds.Add(rsd);
     198          }
     199        }
     200      }
     201      var d =  rsds.Where(x => packingBin.IsPositionFeasible(x.Item, x.Position, useStackingConstraints)).FirstOrDefault();
     202
     203      if (d == null) {
     204        return null;
     205      }
     206
     207      packingItem.Rotated = orientation.Item2;
     208      packingItem.Tilted = orientation.Item3;
     209      return d.Position;
     210    }
     211
     212    Tuple<double, bool, bool> CalculateArea(PackingItem packingItem, bool rotated, bool tilted) {
     213      var item = new PackingItem(packingItem) {
     214        Rotated = rotated,
     215        Tilted = tilted
     216      };
     217      return Tuple.Create<double, bool, bool>(item.Width * item.Depth, rotated, tilted);
    145218    }
    146219
    … …  
    153226    /// <param name="useStackingConstraints"></param>
    154227    /// <returns></returns>
    155     private PackingPosition FindPackingPositionForNotStackableItem(BinPacking3D packingBin, PackingItem packingItem, bool useStackingConstraints) {
     228    private PackingPosition FindPackingPositionForWeightUnsupportedItem(BinPacking3D packingBin, PackingItem packingItem, bool useStackingConstraints) {
    156229      if (!CheckItemDimensions(packingBin, packingItem)) {
    157230        throw new BinPacking3DException($"The dimensions of the given item exceeds the bin dimensions. " +
    … …  
    227300        Tilted = tilted
    228301      };
    229      
     302
    230303      var rsds = new SortedSet<ResidualSpaceDifference>();
    231304      foreach (var ep in packingBin.ExtremePoints) {
    … …  
    240313      return rsds.Where(rsd => packingBin.IsPositionFeasible(rsd.Item, rsd.Position, useStackingConstraints)).FirstOrDefault();
    241314    }
    242        
     315
    243316    protected override bool CheckItemDimensions(BinPacking3D packingBin, PackingItem item) {
    244317      bool ok = false;
    … …  
    270343    }
    271344
    272    
     345
    273346    protected class ResidualSpaceDifference : IComparable {
    274347      public static ResidualSpaceDifference Create(PackingPosition position, PackingItem item, ResidualSpace rs) {
    … …  
    307380
    308381        var x = this.X - rsd.X;
    309         var y = rsd.Y - this.Y;
     382        var y = this.Y - rsd.Y;
    310383        var z = this.Z - rsd.Z;
    311384

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

    r15646 r15705  
    2626using HeuristicLab.Parameters;
    2727using HeuristicLab.Problems.BinPacking;
     28using HeuristicLab.Problems.BinPacking3D.Material;
    2829
    2930namespace HeuristicLab.Problems.BinPacking3D {
    … …  
    4041      get { return (IFixedValueParameter<DoubleValue>)Parameters["Weight"]; }
    4142    }
    42     public IFixedValueParameter<IntValue> MaterialParameter {
    43       get { return (IFixedValueParameter<IntValue>)Parameters["Material"]; }
     43    public IFixedValueParameter<IntValue> LayerParameter {
     44      get { return (IFixedValueParameter<IntValue>)Parameters["Layer"]; }
    4445    }
    4546
    … …  
    5455    }
    5556
    56     public int Material {
    57       get { return MaterialParameter.Value.Value; }
    58       set { MaterialParameter.Value.Value = value; }
    59     }
    60 
     57    public int Layer {
     58      get { return LayerParameter.Value.Value; }
     59      set { LayerParameter.Value.Value = value; }
     60    }
     61
     62    #region Material
     63    public IFixedValueParameter<EnumValue<MaterialType>> MaterialBottomParameter {
     64      get { return (IFixedValueParameter<EnumValue<MaterialType>>)Parameters["MaterialBottom"]; }
     65    }
     66    public MaterialType MaterialBottom {
     67      get { return MaterialBottomParameter.Value.Value; }
     68      set { MaterialBottomParameter.Value.Value = value; }
     69    }
     70
     71    public IFixedValueParameter<EnumValue<MaterialType>> MaterialTopParameter {
     72      get { return (IFixedValueParameter<EnumValue<MaterialType>>)Parameters["MaterialTop"]; }
     73    }
     74    public MaterialType MaterialTop {
     75      get { return MaterialTopParameter.Value.Value; }
     76      set { MaterialTopParameter.Value.Value = value; }
     77    }
     78    #endregion
    6179
    6280    public IFixedValueParameter<DoubleValue> SupportedWeightParameter {
    … …  
    277295
    278296    public bool SupportsStacking(IPackingItem other) {
    279       return ((other.Material < this.Material) || (other.Material.Equals(this.Material) && other.Weight <= this.Weight));
     297      return ((other.Layer < this.Layer) || (other.Layer.Equals(this.Layer) && other.Weight <= this.Weight));
    280298    }
    281299    #endregion
    … …  
    292310      Parameters.Add(new ValueParameter<PackingShape>("TargetBin"));
    293311      Parameters.Add(new FixedValueParameter<DoubleValue>("Weight"));
    294       Parameters.Add(new FixedValueParameter<IntValue>("Material"));
    295 
    296       Parameters.Add(new FixedValueParameter<DoubleValue>("SupportedWeight"));     
     312      Parameters.Add(new FixedValueParameter<IntValue>("Layer"));
     313
     314
     315      Parameters.Add(new FixedValueParameter<EnumValue<MaterialType>>("MaterialTop"));
     316      Parameters.Add(new FixedValueParameter<EnumValue<MaterialType>>("MaterialBottom"));
     317
     318      Parameters.Add(new FixedValueParameter<DoubleValue>("SupportedWeight"));
    297319
    298320      Parameters.Add(new FixedValueParameter<BoolValue>("RotateEnabled"));
    … …  
    319341    }
    320342
    321     public PackingItem(int width, int height, int depth, PackingShape targetBin, double weight, int material)
     343    public PackingItem(int width, int height, int depth, PackingShape targetBin, double weight, int layer)
    322344      : this(width, height, depth, targetBin) {
    323345      this.Weight = weight;
    324       this.Material = material;
     346      this.Layer = layer;
    325347    }
    326348
    … …  
    333355      TargetBin = (PackingShape)packingItem.TargetBin.Clone();
    334356      Weight = packingItem.Weight;
    335       Material = packingItem.Material;
     357      Layer = packingItem.Layer;
    336358      Rotated = packingItem.Rotated;
    337359      Tilted = packingItem.Tilted;
    338360      IsStackabel = packingItem.IsStackabel;
     361      MaterialTop = packingItem.MaterialTop;
     362      MaterialBottom = packingItem.MaterialBottom;
    339363
    340364      LoadSecuringDepth = packingItem.LoadSecuringDepth;
    … …  
    355379      // NOTE: only because of ToString override
    356380      WeightParameter.Value.ValueChanged += (sender, args) => OnToStringChanged();
    357       MaterialParameter.Value.ValueChanged += (sender, args) => OnToStringChanged();
     381      LayerParameter.Value.ValueChanged += (sender, args) => OnToStringChanged();
    358382
    359383      // target bin does not occur in ToString()
    … …  
    361385
    362386    public override string ToString() {
    363       return string.Format("CuboidPackingItem ({0}, {1}, {2}; weight={3}, mat={4})", this.Width, this.Height, this.Depth, this.Weight, this.Material);
     387      return string.Format("CuboidPackingItem ({0}, {1}, {2}; weight={3}, layer={4})", this.Width, this.Height, this.Depth, this.Weight, this.Layer);
    364388    }
    365389

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

    r15617 r15705  
    4040    public int Y { get { return y; } }
    4141    public int Z { get { return z; } }
     42       
    4243
    4344    [StorableConstructor]
    … …  
    6970      if (tdp != null)
    7071        return (tdp.X == this.X && tdp.Y == this.Y && tdp.Z == this.Z);
    71       else return false;
     72      else
     73        return false;
    7274    }
    7375
    … …  
    7577      return base.GetHashCode() + 13 * X + 17 * Y + 23 * Z;
    7678    }
    77    
     79
    7880    #region IComparable<PackingPosition> Members
    7981

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Sorting/PermutationPackingItemSorter.cs

    r15646 r15705  
    136136      return new Permutation(PermutationTypes.Absolute,
    137137                    items.Select((v, i) => new { Index = i, Item = v })
    138                          ./*OrderByDescending(x => x.Item.IsStackabel ? 1 : 0)
    139                          .*/OrderByDescending(x => x.Item.Material)
     138                         .OrderByDescending(x => x.Item.Layer)
    140139                         .ThenByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height)
    141140                         .ThenByDescending(x => x.Item.Height)
    … …  
    151150      return new Permutation(PermutationTypes.Absolute,
    152151                    items.Select((v, i) => new { Index = i, Item = v })
    153                          ./*OrderByDescending(x => x.Item.IsStackabel ? 1 : 0)
    154                          .*/OrderByDescending(x => x.Item.Material)
     152                         .OrderByDescending(x => x.Item.Layer)
    155153                         .ThenByDescending(x => x.Item.Height)
    156154                         .ThenByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height)
    … …  
    166164      return new Permutation(PermutationTypes.Absolute,
    167165                    items.Select((v, i) => new { Index = i, Item = v })
    168                          ./*OrderByDescending(x => x.Item.IsStackabel ? 1 : 0)
    169                          .*/OrderByDescending(x => x.Item.Material)
     166                         .OrderByDescending(x => x.Item.Layer)
    170167                         .ThenByDescending(x => x.Item.Depth * x.Item.Width)
    171168                         .ThenByDescending(x => x.Item.Height)
    … …  
    181178      return new Permutation(PermutationTypes.Absolute,
    182179                    items.Select((v, i) => new { Index = i, Item = v })
    183                          ./*OrderByDescending(x => x.Item.IsStackabel ? 1 : 0)
    184                          .*/OrderByDescending(x => x.Item.Material)
     180                         .OrderByDescending(x => x.Item.Layer)
    185181                         .ThenByDescending(x => x.Item.Height)
    186182                         .ThenByDescending(x => x.Item.Depth * x.Item.Width)
    … …  
    202198                items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Width * v.Depth / clusterRange)) })
    203199                    .GroupBy(x => x.ClusterId)
    204                     .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(z => z.Item.Material).ThenByDescending(y => y.Item.Height).ToList() })
     200                    .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(z => z.Item.Layer).ThenByDescending(y => y.Item.Height).ToList() })
    205201                    .OrderByDescending(x => x.Cluster)
    206202                    .SelectMany(x => x.Items)
    … …  
    222218                items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Height / clusterRange2)) })
    223219                    .GroupBy(x => x.ClusterId)
    224                     .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(z => z.Item.Material).ThenByDescending(y => y.Item.Depth * y.Item.Width).ToList() })
     220                    .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(z => z.Item.Layer).ThenByDescending(y => y.Item.Depth * y.Item.Width).ToList() })
    225221                    .OrderByDescending(x => x.Cluster)
    226222                    .SelectMany(x => x.Items)

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/Interfaces/IPackingItem.cs

    r14163 r15705  
    2424  public interface IPackingItem : IPackingShape {
    2525    double Weight { get; set; }
    26     int Material { get; set; }
     26    int Layer { get; set; }
    2727    /// <summary>
    2828    /// Returns true if the "other" item can be stacked on this item.
Note: See TracChangeset for help on using the changeset viewer.