Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml	(revision 15730)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml	(revision 15731)
@@ -48,9 +48,15 @@
                       Unchecked="ShowResidualSpacesCheckBoxOnUnchecked" 
                       Checked="ShowResidualSpacesCheckBoxOnChecked"/>
+            <TextBlock Name="selectedItemTextBlock" 
+                       Margin="10,6,0,0"
+                       VerticalAlignment="Top" 
+                       HorizontalAlignment="Left" 
+                       Text="Gegenstand:"/>
         </StackPanel>
-        <Border BorderThickness="1" Background="{DynamicResource {x:Static SystemColors.ControlBrushKey}}" Margin="0,52,0,0">
+        <Border BorderThickness="1" Background="{DynamicResource {x:Static SystemColors.ControlBrushKey}}" Margin="0,70,0,0">
             <Viewport3D Name="viewport3D1" Margin="0,-1,0,0" >
                 <Viewport3D.Camera>
-                    <PerspectiveCamera x:Name="camMain" Position="0.5 8 8" LookDirection="0 -1 -1"> <!-- camera position for design time-->
+                    <PerspectiveCamera x:Name="camMain" Position="0.5 8 8" LookDirection="0 -1 -1">
+                        <!-- camera position for design time-->
                     </PerspectiveCamera>
                 </Viewport3D.Camera>
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml.cs	(revision 15730)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml.cs	(revision 15731)
@@ -119,4 +119,20 @@
     }
 
+    private void DisplaySelectedItemText() {
+      string text = "";
+      if (selectedItemKey < 0) {
+        text = $"{packing.BinShape.ToString()}";
+      } else {
+        var packingItem = packing.Items.Single(x => selectedItemKey == x.Key);
+        var position = packing.Positions.Single(x => x.Key == packingItem.Key);
+        text = $"{packingItem.Value.ToString()}, {position.ToString()}";
+        if (packing is BinPacking3D.BinPacking3D) {
+          var stackedWeight = ((BinPacking3D.BinPacking3D)packing).GetStackedWeightForItemId(packingItem.Key);
+          text += $", stacked weight: {stackedWeight}";
+        }
+      }
+      selectedItemTextBlock.Text = text;
+    }
+
     private void UpdateVisualization() {
       Clear();
@@ -126,4 +142,6 @@
       var modelGroup = (Model3DGroup)MyModel.Content;
       var hiddenMaterial = new DiffuseMaterial(new SolidColorBrush(hiddenColor));
+
+      DisplaySelectedItemText();
 
       if (selectedItemKey >= 0) {
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Algorithms/ExtremePointAlgorithm.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Algorithms/ExtremePointAlgorithm.cs	(revision 15730)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Algorithms/ExtremePointAlgorithm.cs	(revision 15731)
@@ -40,5 +40,5 @@
 
   public enum SortingMethod { All, Given, VolumeHeight, HeightVolume, AreaHeight, HeightArea, ClusteredAreaHeight, ClusteredHeightArea }
-  public enum FittingMethod { All, FirstFit, ResidualSpaceBestFit, FreeVolumeBestFit, MinimumResidualSpaceLeft }
+  public enum FittingMethod { All, FirstFit, ResidualSpaceBestFit, FreeVolumeBestFit, MinimumResidualSpaceLeft, FormClosure }
 
   public enum ExtremePointCreationMethod { All, PointProjection, LineProjection }
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs	(revision 15730)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs	(revision 15731)
@@ -29,4 +29,5 @@
 using HeuristicLab.Problems.BinPacking3D.Geometry;
 using HeuristicLab.Collections;
+using HeuristicLab.Problems.BinPacking3D.Graph;
 
 namespace HeuristicLab.Problems.BinPacking3D {
@@ -37,11 +38,14 @@
     [Storable]
     public IDictionary<PackingPosition, IEnumerable<ResidualSpace>> ExtremePoints { get; protected set; }
-    
+
+    [Storable]
+    public IDirectedGraph WeightDistirbution { get; protected set; }
 
     public BinPacking3D(PackingShape binShape)
       : base(binShape) {
       ExtremePoints = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
-
       ExtremePoints.Add(binShape.Origin, new List<ResidualSpace>() { ResidualSpace.Create(binShape.Width, binShape.Height, binShape.Depth) });
+
+      WeightDistirbution = new DirectedGraph();
     }
 
@@ -58,5 +62,7 @@
         }
         ExtremePoints.Add(cloner.Clone(extremePoint.Key), residualSpaces);
-      }      
+      }
+
+      // todo clone WeightDistirbution graph
     }
 
@@ -77,5 +83,74 @@
       Positions[itemID] = position;
       ExtremePoints.Remove(position);
-    }
+
+      AddToGraph(itemID, item, position);
+    }
+
+
+    #region Graph for the calculating the weight distirbution        
+    private void AddToGraph(int itemId, PackingItem item, PackingPosition position) {
+      var sourceVertex = new VertexWithItemId(itemId);
+      WeightDistirbution.AddVertex(sourceVertex);
+
+      var itemsBelow = GetItemsUnderAnItem(position, item);
+      foreach (var itemBelow in itemsBelow) {
+        var targetVertex = GetVertexForItemBelow(itemBelow);
+        if (targetVertex == null) {
+          continue;
+        }
+
+        double overlay = CalculateOverlay(itemBelow, Tuple.Create<PackingPosition, PackingItem>(position, item));
+        double area = (item.Width * item.Depth);
+        var arc = new Arc(sourceVertex, targetVertex) {
+          Weight = overlay / area
+        };
+        WeightDistirbution.AddArc(arc);
+      }
+    }
+
+    /// <summary>
+    /// Returns a vertex related to the given tuple of an item and packing position.
+    /// If there is no related vertex the method returns null.
+    /// </summary>
+    /// <param name="itemBelow"></param>
+    /// <returns></returns>
+    private IVertex GetVertexForItemBelow(Tuple<PackingPosition, PackingItem> itemBelow) {
+      var filteredItems = Items.Where(x => x.Value == itemBelow.Item2);
+      if (filteredItems.Count() <= 0) {
+        return null;
+      }
+      var itemIdBelow = filteredItems.First().Key;
+
+      var targetVertex = WeightDistirbution.Vertices.Where(x => {
+        if (x is VertexWithItemId) {
+          return ((VertexWithItemId)x).ItemId == itemIdBelow;
+        }
+        return false;
+      }).FirstOrDefault();
+
+      return targetVertex;
+    }
+
+
+    #endregion
+
+    #region Calculation of the stacked weight
+    public double GetStackedWeightForItemId(int itemId) {
+      return GetStackedWeightForItemIdRec(itemId);
+    }
+
+    private double GetStackedWeightForItemIdRec(int itemId) {
+      var arcs = WeightDistirbution.Arcs.Where(x => ((VertexWithItemId)x.Target).ItemId == itemId);
+      var stackedWeight = 0.0;
+      foreach (var arc in arcs) {
+        var sourceItemId = ((VertexWithItemId)arc.Source).ItemId;
+        var sourceItem = Items[sourceItemId];
+        stackedWeight += (GetStackedWeightForItemIdRec(sourceItemId) + sourceItem.Weight) * arc.Weight;
+      }
+
+      return stackedWeight;
+    }
+
+    #endregion
 
     #region MassPoint
@@ -316,7 +391,7 @@
       }
 
-      var overlayZ = inFront.Item2.Width;
-      if (behind.Item1.X + behind.Item2.Width < inFront.Item1.X + inFront.Item2.Width) {
-        overlayZ = behind.Item1.X + behind.Item2.Width - inFront.Item1.X;
+      var overlayZ = inFront.Item2.Depth;
+      if (behind.Item1.Z + behind.Item2.Depth < inFront.Item1.Z + inFront.Item2.Depth) {
+        overlayZ = behind.Item1.Z + behind.Item2.Depth - inFront.Item1.Z;
       }
 
@@ -337,4 +412,10 @@
     }
 
+    /// <summary>
+    /// Returns a collection of items and its position which have contact to an given item below
+    /// </summary>
+    /// <param name="position"></param>
+    /// <param name="item"></param>
+    /// <returns></returns>
     private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsUnderAnItem(PackingPosition position, PackingItem item) {
       var selected = Items.Select(x => new {
@@ -344,6 +425,6 @@
         .Where(x => x.Position.X <= position.X && x.Position.X + x.Item.Width > position.X ||
                     x.Position.X > position.X && x.Position.X < position.X + item.Width)
-        .Where(x => x.Position.Z <= position.Z && x.Position.Z + x.Item.Height > position.Z ||
-                    x.Position.Z > position.Z && x.Position.Z < position.Z + item.Height);
+        .Where(x => x.Position.Z <= position.Z && x.Position.Z + x.Item.Depth > position.Z ||
+                    x.Position.Z > position.Z && x.Position.Z < position.Z + item.Depth);
 
       return selected.Select(x => Tuple.Create(x.Position, x.Item));
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Evaluators/BinUtilizationEvaluator.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Evaluators/BinUtilizationEvaluator.cs	(revision 15730)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Evaluators/BinUtilizationEvaluator.cs	(revision 15731)
@@ -81,11 +81,12 @@
     }
 
-    public Tuple<int, double, int> Evaluate1(Solution solution) {
+    public Tuple<int, double, int, int> Evaluate1(Solution solution) {
 
 
-      var res = Tuple.Create<int, double, int>(
+      var res = Tuple.Create<int, double, int, int>(
         GetBinCount(solution),
         CalculateBinUtilizationFirstBin(solution),
-        GetNumberOfResidualSpaces(solution)
+        GetNumberOfResidualSpaces(solution),
+        CalculateMaxDepth(solution)
         );
 
@@ -107,4 +108,13 @@
     }
 
+    private static int CalculateMaxDepth(Solution solution) {
+      var packing = solution.Bins.Last();
+      if (packing == null) {
+        return Int32.MaxValue;
+      }
+
+      return packing.Positions.Select(x => x.Value.Z + packing.Items[x.Key].Depth).Max();
+    }
+
 
     #endregion
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Evaluators/IEvaluator.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Evaluators/IEvaluator.cs	(revision 15730)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Evaluators/IEvaluator.cs	(revision 15731)
@@ -41,5 +41,5 @@
     /// <param name="solution"></param>
     /// <returns></returns>
-    Tuple<int, double, int> Evaluate1(Solution solution);
+    Tuple<int, double, int, int> Evaluate1(Solution solution);
   }
 }
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Evaluators/PackingRatioEvaluator.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Evaluators/PackingRatioEvaluator.cs	(revision 15730)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Evaluators/PackingRatioEvaluator.cs	(revision 15731)
@@ -98,11 +98,12 @@
     }
 
-    public Tuple<int, double, int> Evaluate1(Solution solution) {
+    public Tuple<int, double, int, int> Evaluate1(Solution solution) {
 
 
-      var res = Tuple.Create<int, double, int>(
+      var res = Tuple.Create<int, double, int, int>(
         GetBinCount(solution),
         CalculateBinUtilizationFirstBin(solution),
-        GetNumberOfResidualSpaces(solution)
+        GetNumberOfResidualSpaces(solution),
+        CalculateMaxDepth(solution)
         );
 
@@ -124,4 +125,13 @@
     }
 
+    private static int CalculateMaxDepth(Solution solution) {
+      var packing = solution.Bins.Last();
+      if (packing == null) {
+        return Int32.MaxValue;
+      }
+
+      return packing.Positions.Select(x => x.Value.Z + packing.Items[x.Key].Depth).Max();
+    }
+
     #endregion
   }
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/LineProjectionBasedEPCreator.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/LineProjectionBasedEPCreator.cs	(revision 15730)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/LineProjectionBasedEPCreator.cs	(revision 15731)
@@ -35,124 +35,7 @@
   /// This projection method enhances the point based projection method by creating extra extreme points on the intersection points of two items.
   /// </summary>
-  public class LineProjectionBasedEPCreator : ExtremePointCreator {
-
-    /// <summary>
-    /// This lock object is needed because of creating the extreme points in an parallel for loop.
-    /// </summary>
-    object _lockAddExtremePoint = new object();
-
-    protected override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
-      binPacking.ExtremePoints.Clear();
-
-      // generate all new extreme points parallel. This speeds up the creator.
-      Parallel.ForEach(binPacking.Items, i => {
-        PackingItem it = i.Value;
-        PackingPosition p = binPacking.Positions[i.Key];
-        GenerateNewExtremePointsForItem(binPacking, it, p);
-      });
-
-      // remove not needed extreme points.
-      foreach (var extremePoint in binPacking.ExtremePoints.ToList()) {
-        // check if a residual space can be removed
-        foreach (var rs in extremePoint.Value.ToList()) {
-          if (ResidualSpaceCanBeRemoved(binPacking, extremePoint.Key, rs)) {
-            ((IList<ResidualSpace>)extremePoint.Value).Remove(rs);
-          }
-        }
-        // if the current extreme point has no more residual spaces, it can be removed.
-        if (((IList<ResidualSpace>)extremePoint.Value).Count <= 0) {
-          binPacking.ExtremePoints.Remove(extremePoint);
-        }
-      }
-      
-    }
-
-    /// <summary>
-    /// Returns true if a given residual space can be removed.
-    /// The given residual space can be removed if it is within another residual space and
-    /// - neither the position of the other residual space and the current extreme point have an item below or
-    /// - the current extreme point has an item below.
-    /// </summary>
-    /// <param name="binPacking"></param>
-    /// <param name="position"></param>
-    /// <param name="rs"></param>
-    /// <returns></returns>
-    private bool ResidualSpaceCanBeRemoved(BinPacking3D binPacking, PackingPosition position, ResidualSpace rs) {
-      foreach (var extremePoint in binPacking.ExtremePoints) {
-        if (position.Equals(extremePoint.Key)) {
-          continue;
-        }
-        if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(position), rs, extremePoint.Key, extremePoint.Value)) {
-          var itemBelowEp = LiesOnAnyItem(binPacking, extremePoint.Key);
-          var itemBelowPos = LiesOnAnyItem(binPacking, position);
-
-          if (itemBelowEp || !itemBelowEp && !itemBelowPos) {
-            return true;
-          }
-        }
-      }
-      return false;
-    }
-
-    /// <summary>
-    /// Returns true if the given position lies on an item or an the ground.
-    /// </summary>
-    /// <param name="binPacking"></param>
-    /// <param name="position"></param>
-    /// <returns></returns>
-    private bool LiesOnAnyItem(BinPacking3D binPacking, PackingPosition position) {
-      if (position.Y == 0) {
-        return true;
-      }
-
-      var items = binPacking.Items.Where(x => {
-        var itemPosition = binPacking.Positions[x.Key];
-        var item = x.Value;
-        int width = item.Width;
-        int depth = item.Depth;
-
-        return itemPosition.Y + item.Height == position.Y &&
-               itemPosition.X <= position.X && position.X < itemPosition.X + width &&
-               itemPosition.Z <= position.Z && position.Z < itemPosition.Z + depth;
-      });
-
-      return items.Count() > 0;
-    }
-
-
-    /// <summary>
-    /// Adds a new extreme point an the related residual spaces to a given bin packing.
-    /// - The given position has to be valid.
-    /// - The extreme point does not exist in the bin packing.
-    /// - There must be at minimum one valid residual space. A residual space is invalid if the space is zero.
-    /// </summary>
-    /// <param name="binPacking"></param>
-    /// <param name="position"></param>
-    /// <returns>True = the given point and its related residual spaces were successfully added to the bin packing</returns>
-    protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
-      if (position == null) {
-        return false;
-      }
-
-      if (PointIsInAnyItem(binPacking, new Vector3D(position))) {
-        return false;
-      }
-
-      // this is necessary if the extreme points are being created in a parallel loop.
-      lock (_lockAddExtremePoint) {
-        if (binPacking.ExtremePoints.ContainsKey(position)) {
-          return false;
-        }
-
-        var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
-
-        if (rs.Count() <= 0) {
-          return false;
-        }
-
-        binPacking.ExtremePoints.Add(position, rs);
-        return true;
-      }
-    }
+  public class LineProjectionBasedEPCreator : PointProjectionBasedEPCreator {
+    
+
 
     /// <summary>
@@ -168,50 +51,5 @@
       EdgeProjectionForNewItem(binPacking, newItem, position);
     }
-
-    #region Extreme point creation by using a point projection based method
-
-    /// <summary>
-    /// This method creates extreme points by using a point projection based method.
-    /// For each item there will be created three points and each of the points will be projected twice.
-    /// The direction of the projection depends on position of the point.
-    /// </summary>
-    /// <param name="binPacking"></param>
-    /// <param name="newItem"></param>
-    /// <param name="position"></param>
-    private void PointProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
-      int newWidth = newItem.Width;
-      int newDepth = newItem.Depth;
-      var binShape = binPacking.BinShape;
-      var sourcePoint = new PackingPosition(position.AssignedBin, position.X + newWidth, position.Y, position.Z);
-      PointProjection(binPacking, sourcePoint, ProjectDown);
-      PointProjection(binPacking, sourcePoint, ProjectBackward);
-
-      sourcePoint = new PackingPosition(position.AssignedBin, position.X, position.Y + newItem.Height, position.Z);
-      PointProjection(binPacking, sourcePoint, ProjectLeft);
-      PointProjection(binPacking, sourcePoint, ProjectBackward);
-
-      sourcePoint = new PackingPosition(position.AssignedBin, position.X, position.Y, position.Z + newDepth);
-      PointProjection(binPacking, sourcePoint, ProjectDown);
-      PointProjection(binPacking, sourcePoint, ProjectLeft);
-    }
-
-
-    /// <summary>
-    /// Projects a given point by using the given projection method to the neares item.
-    /// The given projection method returns a point which lies on a side of the nearest item in the direction. 
-    /// </summary>
-    /// <param name="binPacking"></param>
-    /// <param name="position"></param>
-    /// <param name="projectionMethod"></param>
-    private void PointProjection(BinPacking3D binPacking, PackingPosition position, Func<BinPacking3D, Vector3D, Vector3D> projectionMethod) {
-      Vector3D sourcePoint = new Vector3D(position);
-      if (sourcePoint.X < binPacking.BinShape.Width && sourcePoint.Y < binPacking.BinShape.Height && sourcePoint.Z < binPacking.BinShape.Depth) {
-        Vector3D point = projectionMethod?.Invoke(binPacking, sourcePoint);
-        if (point != null) {
-          AddExtremePoint(binPacking, new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
-        }
-      }
-    }
-    #endregion
+    
 
     #region Extreme point creation by using an edge projection based method
@@ -245,16 +83,5 @@
     }
     #endregion
-
-    /// <summary>
-    /// Updates the residual spaces.
-    /// It removes not needed ones.
-    /// A residual space will be removed if the space is a subspace of another one and 
-    /// the current one has no item below or both have an item below. 
-    /// </summary>
-    /// <param name="binPacking"></param>
-    /// <param name="item"></param>
-    /// <param name="position"></param>
-    protected override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
-    }
+    
 
     /// <summary>
@@ -609,20 +436,6 @@
       return eps as IEnumerable<Vector3D>;
     }
-
-
-
     #endregion
-
-    /// <summary>
-    /// Calculates the residual spaces for an extreme point.
-    /// </summary>
-    /// <param name="binPacking"></param>
-    /// <param name="pos"></param>
-    /// <returns></returns>
-    protected override IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
-      return ResidualSpaceCalculatorFactory.CreateCalculator().CalculateResidualSpaces(binPacking, pos);
-    }
+    
   }
-
-
 }
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/PointProjectionBasedEPCreator.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/PointProjectionBasedEPCreator.cs	(revision 15730)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/PointProjectionBasedEPCreator.cs	(revision 15731)
@@ -21,4 +21,5 @@
 
 using HeuristicLab.Common;
+using HeuristicLab.Problems.BinPacking3D.ExtremePointPruning;
 using HeuristicLab.Problems.BinPacking3D.Geometry;
 using HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation;
@@ -40,16 +41,28 @@
     /// This lock object is needed because of creating the extreme points in an parallel for loop.
     /// </summary>
-    object _lockAddExtremePoint = new object();
+    protected object _lockAddExtremePoint = new object();
 
     protected override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
       binPacking.ExtremePoints.Clear();
 
+      if (binPacking.Items.Count <= 0) {
+        return;
+      }
+
       // generate all new extreme points parallel. This speeds up the creator.
-      Parallel.ForEach(binPacking.Items, i => {
+      var items = binPacking.Items.OrderBy(x => x.Value.Layer);
+      Parallel.ForEach(items.Where(x => x.Value.Layer < item.Layer), i => {
         PackingItem it = i.Value;
-        PackingPosition p = binPacking.Positions[i.Key];
-        GenerateNewExtremePointsForItem(binPacking, it, p);
+        PackingPosition pos = binPacking.Positions[i.Key];
+        GenerateNewExtremePointsForItem(binPacking, it, pos);
       });
-
+      ExtremePointPruningFactory.CreatePruning().PruneExtremePoints(ExtremePointPruningMethod.PruneBehind, new List<BinPacking3D>() { binPacking });
+
+      Parallel.ForEach(items.Where(x => x.Value.Layer >= item.Layer), i => {
+        PackingItem it = i.Value;
+        PackingPosition pos = binPacking.Positions[i.Key];
+        GenerateNewExtremePointsForItem(binPacking, it, pos);
+      });
+      
       // remove not needed extreme points.
       foreach (var extremePoint in binPacking.ExtremePoints.ToList()) {
@@ -178,5 +191,5 @@
     /// <param name="newItem"></param>
     /// <param name="position"></param>
-    private void PointProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
+    protected void PointProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
       int newWidth = newItem.Width;
       int newDepth = newItem.Depth;
@@ -210,35 +223,4 @@
           AddExtremePoint(binPacking, new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
         }
-      }
-    }
-    #endregion
-
-    #region Extreme point creation by using an edge projection based method
-
-    /// <summary>
-    /// This method creates extreme points be projecting the edges of a given item 
-    ///   - left
-    ///   - back
-    ///   - down.
-    /// A extreme point will be created, if an edge instersects with an edge of another item.
-    /// </summary>
-    /// <param name="binPacking"></param>
-    /// <param name="newItem"></param>
-    /// <param name="position"></param>
-    private void EdgeProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
-      int newWidth = newItem.Width;
-      int newDepth = newItem.Depth;
-      var binShape = binPacking.BinShape;
-
-      foreach (var ep in GetEpsOnLeft(binPacking, newItem, position)) {
-        AddExtremePoint(binPacking, ep.Key);
-      }
-
-      foreach (var ep in GetEpsBelow(binPacking, newItem, position)) {
-        AddExtremePoint(binPacking, ep.Key);
-      }
-
-      foreach (var ep in GetEpsBehind(binPacking, newItem, position)) {
-        AddExtremePoint(binPacking, ep.Key);
       }
     }
@@ -277,339 +259,4 @@
     }
 
-    /// <summary>
-    /// Returns true if an item is in the residual space of a given extrem point
-    /// </summary>
-    /// <param name="rs">KeyValuePair with the position of the extreme point and the size of the residual space</param>
-    /// <param name="item">Given Item</param>
-    /// <param name="position">Given position</param>
-    /// <returns></returns>
-    private bool ItemIsInRs(KeyValuePair<PackingPosition, ResidualSpace> rs, PackingItem item, PackingPosition position) {
-      return GetVertices(item, position).Where(pos => pos.IsInside(rs.Key, rs.Value)).Any();
-    }
-
-    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
-      return binPacking.Items.Select(x => new {
-        Item = x.Value,
-        Position = binPacking.Positions[x.Key]
-      }).Where(x => x.Position.Y < position.Y)
-          .Select(x => Tuple.Create(x.Position, x.Item));
-    }
-
-    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
-      return binPacking.Items.Select(x => new {
-        Item = x.Value,
-        Position = binPacking.Positions[x.Key]
-      }).Where(x => x.Position.Z < position.Z)
-          .Select(x => Tuple.Create(x.Position, x.Item));
-    }
-
-    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
-      return binPacking.Items.Select(x => new {
-        Item = x.Value,
-        Position = binPacking.Positions[x.Key]
-      }).Where(x => x.Position.X < position.X)
-          .Select(x => Tuple.Create(x.Position, x.Item));
-    }
-
-    /// <summary>
-    /// Returns the extreme points and its related residual spaces on the left side of an given item.
-    /// This extreme points are being created by intersecting two edges on the left side of the given item 
-    /// (left - in front, left - on top) with all edges on the right side of all other items int the bin packing.
-    /// </summary>
-    /// <param name="item"></param>
-    /// <param name="position"></param>
-    /// <returns></returns>
-    private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
-      var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
-      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsOnLeft(binPacking, item, position);
-      var edges = GetProjectionEdgesOnLeft(item, position);
-
-      foreach (var otherItem in items) {
-        if (position.Equals(otherItem.Item1)) {
-          continue;
-        }
-
-        var otherItemEdges = GetEdgesOnRight(otherItem.Item2, otherItem.Item1);
-        // left - in front
-        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(1, 0, 0))) {
-          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
-            // As this edge has a vertical direction, every point of intersection won't have an item below.
-            // So finally it is being projected down.
-            var point = ProjectDown(binPacking, ProjectLeft(binPacking, ep));
-            var residualSpaces = CalculateResidualSpace(binPacking, point);
-            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
-            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
-              eps.Add(newExtremePoint, residualSpaces);
-            }
-          }
-        }
-
-        // left - on top
-        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(1, 0, 0))) {
-          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
-            var point = ProjectLeft(binPacking, ep);
-            var residualSpaces = CalculateResidualSpace(binPacking, point);
-            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
-            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
-              eps.Add(newExtremePoint, residualSpaces);
-            }
-          }
-        }
-      }
-      return eps;
-    }
-
-
-    /// <summary>
-    /// Returns the extreme points and its related residual spaces below of an given item.
-    /// This extreme points are being created by intersecting two edges below of the given item 
-    /// (below - in front, below - right) with all edges on top side of all other items int the bin packing.
-    /// </summary>
-    /// <param name="item"></param>
-    /// <param name="position"></param>
-    /// <returns></returns>
-    private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
-      var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
-      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBelow(binPacking, position);
-      var edges = GetProjectionEdgesBelow(item, position);
-
-      foreach (var otherItem in items) {
-        if (position.Equals(otherItem.Item1)) {
-          continue;
-        }
-
-        var otherItemEdges = GetEdgesOnTop(otherItem.Item2, otherItem.Item1);
-        // below - in front
-        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 1, 0))) {
-          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
-            var point = ProjectDown(binPacking, ep);
-            var residualSpaces = CalculateResidualSpace(binPacking, point);
-            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
-            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
-              eps.Add(newExtremePoint, residualSpaces);
-            }
-          }
-        }
-
-        // below - right
-        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 1, 0))) {
-          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
-            var point = ProjectDown(binPacking, ep);
-            var residualSpaces = CalculateResidualSpace(binPacking, point);
-            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
-            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
-              eps.Add(newExtremePoint, residualSpaces);
-            }
-          }
-        }
-      }
-      return eps;
-    }
-
-    /// <summary>
-    /// Returns the extreme points and its related residual spaces below of an given item.
-    /// This extreme points are being created by intersecting two edges below of the given item 
-    /// (right - behind, on top - behind) with all edges on top side of all other items int the bin packing.
-    /// </summary>
-    /// <param name="item"></param>
-    /// <param name="position"></param>
-    /// <returns></returns>
-    private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
-      var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
-      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBehind(binPacking, position);
-      var edges = GetProjectionEdgesBehind(item, position);
-
-      foreach (var otherItem in items) {
-        if (position.Equals(otherItem.Item1)) {
-          continue;
-        }
-
-        var otherItemEdges = GetEdgesInFront(otherItem.Item2, otherItem.Item1);
-        // right - behind
-        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 0, 1))) {
-          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
-            // As this edge has a vertical direction, every point of intersection won't have an item below.
-            // So finally it is being projected down.
-            var point = ProjectDown(binPacking, ProjectBackward(binPacking, ep));
-            var residualSpaces = CalculateResidualSpace(binPacking, point);
-            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
-            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
-              eps.Add(newExtremePoint, residualSpaces);
-            }
-          }
-        }
-
-        // on top - behind
-        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 0, 1))) {
-          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
-            var point = ProjectBackward(binPacking, ep);
-            var residualSpaces = CalculateResidualSpace(binPacking, point);
-            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
-            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
-              eps.Add(newExtremePoint, residualSpaces);
-            }
-          }
-        }
-      }
-      return eps;
-    }
-
-    #region Methods for getting the edges for items
-
-    /// <summary>
-    /// Returns an array of packing position which represents the vertices of an item.
-    /// The position of a vertex in the array is mapped to an item as followed:
-    ///      4----------5
-    ///     /|         /|
-    ///    / |        / |
-    ///   /  0-------/--1
-    ///  6--/-------7  /
-    ///  | /        | /
-    ///  |/         |/
-    ///  2----------3
-    ///  
-    ///  0 = (0,0,0)
-    /// </summary>
-    /// <param name="item"></param>
-    /// <param name="position"></param>
-    /// <returns></returns>
-    private Vector3D[] GetVertices(PackingItem item, PackingPosition position) {
-      int width = item.Width;
-      int depth = item.Depth;
-      return new Vector3D[] {
-        new Vector3D(position.X + 0,     position.Y + 0,           position.Z + 0), // (0,0,0)
-        new Vector3D(position.X + width, position.Y + 0,           position.Z + 0), // (x,0,0)
-        new Vector3D(position.X + 0,     position.Y + 0,           position.Z + depth), // (0,0,z)
-        new Vector3D(position.X + width, position.Y + 0,           position.Z + depth), // (x,0,z)
-
-        new Vector3D(position.X + 0,     position.Y + item.Height, position.Z + 0), // (0,y,0)
-        new Vector3D(position.X + width, position.Y + item.Height, position.Z + 0), // (x,y,0)
-        new Vector3D(position.X + 0,     position.Y + item.Height, position.Z + depth), // (0,y,z)
-        new Vector3D(position.X + width, position.Y + item.Height, position.Z + depth), //(x,y,z)
-      };
-    }
-
-    private Edge3D[] GetProjectionEdgesOnLeft(PackingItem item, PackingPosition position) {
-      Vector3D[] points = GetVertices(item, position);
-
-      return new Edge3D[] {
-        new Edge3D(points[2], points[6]),
-        new Edge3D(points[6], points[4])
-      };
-    }
-
-    private Edge3D[] GetProjectionEdgesBelow(PackingItem item, PackingPosition position) {
-      Vector3D[] points = GetVertices(item, position);
-
-      return new Edge3D[] {
-        new Edge3D(points[2], points[3]),
-        new Edge3D(points[3], points[1])
-      };
-    }
-
-    private Edge3D[] GetProjectionEdgesBehind(PackingItem item, PackingPosition position) {
-      Vector3D[] points = GetVertices(item, position);
-
-      return new Edge3D[] {
-        new Edge3D(points[1], points[5]),
-        new Edge3D(points[5], points[4])
-      };
-    }
-
-    /// <summary>
-    /// Returns an array of edges which contains all edges of the rigth side of an given item.
-    /// </summary>
-    /// <param name="item"></param>
-    /// <param name="position"></param>
-    /// <returns></returns>
-    private Edge3D[] GetEdgesOnRight(PackingItem item, PackingPosition position) {
-      Vector3D[] points = GetVertices(item, position);
-
-      return new Edge3D[] {
-        new Edge3D(points[1], points[5]),
-        new Edge3D(points[5], points[7]),
-        new Edge3D(points[7], points[3]),
-        new Edge3D(points[3], points[1])
-      };
-    }
-
-    /// <summary>
-    /// Returns an array of edges which contains all edges on the top of an given item.
-    /// </summary>
-    /// <param name="item"></param>
-    /// <param name="position"></param>
-    /// <returns></returns>
-    private Edge3D[] GetEdgesOnTop(PackingItem item, PackingPosition position) {
-      Vector3D[] points = GetVertices(item, position);
-
-      return new Edge3D[] {
-        new Edge3D(points[4], points[5]),
-        new Edge3D(points[5], points[7]),
-        new Edge3D(points[7], points[6]),
-        new Edge3D(points[6], points[4])
-      };
-    }
-
-    /// <summary>
-    /// Returns an array of edges which contains all edges in front of an given item.
-    /// </summary>
-    /// <param name="item"></param>
-    /// <param name="position"></param>
-    /// <returns></returns>
-    private Edge3D[] GetEdgesInFront(PackingItem item, PackingPosition position) {
-      Vector3D[] points = GetVertices(item, position);
-
-      return new Edge3D[] {
-        new Edge3D(points[2], points[3]),
-        new Edge3D(points[3], points[7]),
-        new Edge3D(points[7], points[6]),
-        new Edge3D(points[6], points[2])
-      };
-    }
-
-    #endregion
-
-
-    #region Intersections
-
-    /// <summary>
-    /// Returns a collection of points where a given edge (projectedEdge) intersects with other edges.
-    /// The given edge (projectedEdge) will be projected by using the given vector direction
-    /// and a edge of the given edge collection.
-    /// The returned collecten can be empty.
-    /// </summary>
-    /// <param name="projectedEdge"></param>
-    /// <param name="edges"></param>
-    /// <param name="direction"></param>
-    /// <returns></returns>
-    private IEnumerable<Vector3D> IntersectionsForItem(Edge3D projectedEdge, Edge3D[] edges, Vector3D direction = null) {
-      IList<Vector3D> eps = new List<Vector3D>();
-      foreach (var edge in edges) {
-        Edge3D e = projectedEdge;
-        if (direction != null) {
-          if (direction.X != 0) {
-            e.Start.X = edge.Start.X;
-            e.End.X = edge.End.X;
-          } else if (direction.Y != 0) {
-            e.Start.Y = edge.Start.Y;
-            e.End.Y = edge.End.Y;
-          } else if (direction.Z != 0) {
-            e.Start.Z = edge.Start.Z;
-            e.End.Z = edge.End.Z;
-          }
-        }
-
-        var ep = edge.Intersects(e);
-        if (ep != null) {
-          eps.Add(ep);
-        }
-      }
-
-      return eps as IEnumerable<Vector3D>;
-    }
-
-
-
-    #endregion
 
     /// <summary>
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointPruning/ExtremePointPruning.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointPruning/ExtremePointPruning.cs	(revision 15730)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointPruning/ExtremePointPruning.cs	(revision 15731)
@@ -73,5 +73,4 @@
       }
     }
-    
   }
 }
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Graph/VertexWithItemId.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Graph/VertexWithItemId.cs	(revision 15731)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Graph/VertexWithItemId.cs	(revision 15731)
@@ -0,0 +1,48 @@
+﻿using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Problems.BinPacking3D.Graph {
+  [Item("Vertex", "An object representing a vertex in the graph. It can have a text label, a weight, and an additional data object.")]
+  [StorableClass]
+  public class VertexWithItemId : Vertex {
+    [Storable]
+    private int _itemId;
+
+    public int ItemId {
+      get { return _itemId; }
+      protected set { _itemId = value; }
+    }
+
+    [StorableConstructor]
+    public VertexWithItemId(bool deserializing) : base(deserializing) { }
+
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() { }
+
+    public VertexWithItemId(int itemId)
+      : base() {
+      _itemId = itemId;
+    }
+        
+    protected VertexWithItemId(Vertex original, Cloner cloner)
+      : base(original, cloner) {
+      if (original is VertexWithItemId) {
+        _itemId = ((VertexWithItemId)original).ItemId;
+      }
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new VertexWithItemId(this, cloner);
+    }
+
+    public override string ToString() {
+      return $"Vertex: {ItemId}";
+    }
+  }
+}
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/ThreeDInstanceParser.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/ThreeDInstanceParser.cs	(revision 15730)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/ThreeDInstanceParser.cs	(revision 15731)
@@ -59,5 +59,6 @@
                 RotateEnabled = rotate == 0 ? false : true,
                 TiltEnabled = tilt == 0 ? false : true,
-                IsStackabel = stack == 0 ? false : true
+                IsStackabel = stack == 0 ? false : true,
+                SupportedWeight = weight
               };
               Items.Add(item);
Index: anches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Material/FrictionalCoefficientTable.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Material/FrictionalCoefficientTable.cs	(revision 15730)
+++ 	(revision )
@@ -1,30 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Linq;
-using System.Text;
-using System.Threading.Tasks;
-
-namespace HeuristicLab.Problems.BinPacking3D.Material {
-  public class FrictionalCoefficientTable {
-    private FrictionalCoefficientTable _instance;
-
-    //private MaterialType 
-
-    private FrictionalCoefficientTable() {
-
-    }
-
-    public FrictionalCoefficientTable Instance {
-      get {
-        if (_instance == null) {
-          _instance = new FrictionalCoefficientTable();
-        }
-        return _instance;
-      }
-    }
-
-
-
-
-  }
-}
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Material/MaterialType.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Material/MaterialType.cs	(revision 15730)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Material/MaterialType.cs	(revision 15731)
@@ -8,8 +8,12 @@
   
   public enum MaterialType {
-    EuroPallet,
+    EuroPallet = 0,
+    IncaPallet,
     Wood,
+    Paperboard,
     Steel,
-    Paperboard
+    ScreenPrintingPlate,
+    NonSlipMat,
+    Carriage
   }
 }
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPacker.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPacker.cs	(revision 15730)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPacker.cs	(revision 15731)
@@ -125,5 +125,5 @@
       return clonedItems;
     }
-
+    
   }
 }
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFactory.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFactory.cs	(revision 15730)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFactory.cs	(revision 15731)
@@ -53,4 +53,7 @@
           binPacker = new BinPackerMinRSLeft();
           break;
+        case FittingMethod.FormClosure:
+          binPacker = new BinPackerFormClosure();
+          break;
         default:
           throw new ArgumentException("Unknown fitting method: " + fittingMethod);
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFormClosure.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFormClosure.cs	(revision 15731)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFormClosure.cs	(revision 15731)
@@ -0,0 +1,148 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Problems.BinPacking3D.ExtremePointCreation;
+
+namespace HeuristicLab.Problems.BinPacking3D.Packer {
+  internal class BinPackerFormClosure : BinPacker {
+
+    #region Constructors for HEAL
+    [StorableConstructor]
+    protected BinPackerFormClosure(bool deserializing) : base(deserializing) { }
+
+    public BinPackerFormClosure(BinPackerMinRSLeft original, Cloner cloner) : base(original, cloner) {
+    }
+    public override IDeepCloneable Clone(Cloner cloner) {
+      throw new NotImplementedException();
+    }
+    #endregion
+
+    public BinPackerFormClosure() : base() { }
+
+    /// <summary>
+    /// 
+    /// </summary>
+    /// <param name="sortedItems"></param>
+    /// <param name="binShape"></param>
+    /// <param name="items"></param>
+    /// <param name="epCreationMethod"></param>
+    /// <param name="epPruningMethod"></param>
+    /// <param name="useStackingConstraints"></param>
+    /// <returns></returns>
+    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, ExtremePointPruningMethod epPruningMethod, bool useStackingConstraints) {
+      var workingItems = CloneItems(items);
+      IList<BinPacking3D> packingList = new List<BinPacking3D>();
+      IList<int> remainingIds = new List<int>(sortedItems);
+      IExtremePointCreator extremePointCreator = ExtremePointCreatorFactory.CreateExtremePointCreator(epCreationMethod, useStackingConstraints);
+
+      try {
+        var groupedItems = items.Select((x, index) => new { Item = x, Id = index })
+                                .GroupBy(x => x.Item.Layer)
+                                .OrderBy(x => x.Key);
+
+        BinPacking3D packingBin = new BinPacking3D(binShape);
+        packingList.Add(packingBin);
+        foreach (var grouping in groupedItems) {
+          var notPacked = new List<KeyValuePair<int, PackingItem>>();
+          var gr = grouping.ToList();
+          var selectedItems = gr.Where(x => ItemBinWidth(x.Item, binShape))
+                                .OrderByDescending(x => x.Item.Width)
+                                .ThenByDescending(x => x.Item.Height)
+                                .ThenByDescending(x => x.Item.Depth);
+          var otherItems = gr.Except(selectedItems).OrderByDescending(x => x.Item.Width * x.Item.Height);
+          foreach (var item in selectedItems) {
+            if (TryToPack(packingBin, item.Item, item.Id, extremePointCreator, useStackingConstraints)) {
+              remainingIds.Remove(item.Id);
+            } else {
+              notPacked.Add(new KeyValuePair<int, PackingItem>(item.Id, item.Item));
+            }
+          }
+          foreach (var item in otherItems) {
+            if (TryToPack(packingBin, item.Item, item.Id, extremePointCreator, useStackingConstraints)) {
+              remainingIds.Remove(item.Id);
+            } else {
+              notPacked.Add(new KeyValuePair<int, PackingItem>(item.Id, item.Item));
+            }
+          }
+
+          while (notPacked.Count > 0) {
+            packingBin = new BinPacking3D(binShape);
+            packingList.Add(packingBin);
+
+            foreach (var item in notPacked.ToList()) {
+              if (TryToPack(packingBin, item.Value, item.Key, extremePointCreator, useStackingConstraints)) {
+                remainingIds.Remove(item.Key);
+                notPacked.Remove(item);
+              }
+            }
+          }
+        }
+      } catch { }
+
+
+      return packingList;
+    }
+
+    private bool TryToPack(BinPacking3D packingBin, PackingItem item, int itemId, IExtremePointCreator extremePointCreator, bool useStackingConstraints) {
+      var position = FindPackingPositionForItem(packingBin, item, useStackingConstraints);
+      if (position != null) {
+        PackItem(packingBin, itemId, item, position, extremePointCreator, useStackingConstraints);
+        packingBin.PackItem(itemId, item, position);
+        return true;
+      }
+      return false;
+    }
+
+    protected override PackingPosition FindPackingPositionForItem(BinPacking3D packingBin, PackingItem packingItem, bool useStackingConstraints) {
+      if (!CheckItemDimensions(packingBin, packingItem)) {
+        throw new BinPacking3DException($"The dimensions of the given item exceeds the bin dimensions. " +
+          $"Bin: ({packingBin.BinShape.Width} {packingBin.BinShape.Depth} {packingBin.BinShape.Height})" +
+          $"Item: ({packingItem.Width} {packingItem.Depth} {packingItem.Height})");
+      }
+
+      var newPosition = packingBin.ExtremePoints.Where(x => packingBin.IsPositionFeasible(packingItem, x.Key, useStackingConstraints)).FirstOrDefault();
+
+      return newPosition.Key;
+    }
+
+
+    private static bool ItemBinWidth(PackingItem item, PackingShape bin) {
+      var itemCopy = item.Clone() as PackingItem;
+      int binWith = bin.Width;
+      if (itemCopy.Width <= binWith && binWith % itemCopy.Width == 0) {
+        return true;
+      }
+
+      itemCopy.Rotated = true;
+      if (itemCopy.Width <= binWith && binWith % itemCopy.Width == 0) {
+        item.Rotated = true;
+        return true;
+      }
+
+      itemCopy.Rotated = false;
+      itemCopy.Tilted = true;
+      if (itemCopy.Width <= binWith && binWith % itemCopy.Width == 0) {
+        item.Tilted = true;
+        return true;
+      }
+
+      itemCopy.Rotated = true;
+      itemCopy.Tilted = true;
+      if (itemCopy.Width <= binWith && binWith % itemCopy.Width == 0) {
+        item.Rotated = true;
+        item.Tilted = true;
+        return true;
+      }
+      return false;
+    }
+
+    public override void PackItemsToPackingList(IList<BinPacking3D> packingList, Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, ExtremePointPruningMethod epPruningMethod, bool useStackingConstraints) {
+      throw new NotImplementedException();
+    }
+  }
+}
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerMinRSLeft.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerMinRSLeft.cs	(revision 15730)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerMinRSLeft.cs	(revision 15731)
@@ -94,4 +94,5 @@
       ExtremePointPruningFactory.CreatePruning().PruneExtremePoints(epPruningMethod, packingList);
     }
+    
 
     /// <summary>
@@ -107,5 +108,5 @@
       var remainingNotWeightSupportedItems = new List<int>();
       foreach (var itemId in new List<int>(remainingIds)) {
-        var item = items[itemId];
+        var item = items[itemId];        
 
         // If an item doesn't support any weight it should have a minimum waste of the residual space.
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/PackingItem.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/PackingItem.cs	(revision 15730)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/PackingItem.cs	(revision 15731)
@@ -295,5 +295,5 @@
 
     public bool SupportsStacking(IPackingItem other) {
-      return ((other.Layer < this.Layer) || (other.Layer.Equals(this.Layer) && other.Weight <= this.Weight));
+      return other.Layer <= this.Layer && SupportedWeight > 0;
     }
     #endregion
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Solution.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Solution.cs	(revision 15730)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Solution.cs	(revision 15731)
@@ -66,4 +66,8 @@
       }
 
+      if (evaluatedThis.Item4 > evaluatedOther.Item4) {
+        return false;
+      }
+
       if (evaluatedThis.Item3 > evaluatedOther.Item3) {
         return false;
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Sorting/PermutationPackingItemSorter.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Sorting/PermutationPackingItemSorter.cs	(revision 15730)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Sorting/PermutationPackingItemSorter.cs	(revision 15731)
@@ -136,5 +136,5 @@
       return new Permutation(PermutationTypes.Absolute,
                     items.Select((v, i) => new { Index = i, Item = v })
-                         .OrderByDescending(x => x.Item.Layer)
+                         .OrderBy(x => x.Item.Layer)
                          .ThenByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height)
                          .ThenByDescending(x => x.Item.Height)
@@ -150,5 +150,5 @@
       return new Permutation(PermutationTypes.Absolute,
                     items.Select((v, i) => new { Index = i, Item = v })
-                         .OrderByDescending(x => x.Item.Layer)
+                         .OrderBy(x => x.Item.Layer)
                          .ThenByDescending(x => x.Item.Height)
                          .ThenByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height)
@@ -164,5 +164,5 @@
       return new Permutation(PermutationTypes.Absolute,
                     items.Select((v, i) => new { Index = i, Item = v })
-                         .OrderByDescending(x => x.Item.Layer)
+                         .OrderBy(x => x.Item.Layer)
                          .ThenByDescending(x => x.Item.Depth * x.Item.Width)
                          .ThenByDescending(x => x.Item.Height)
@@ -178,5 +178,5 @@
       return new Permutation(PermutationTypes.Absolute,
                     items.Select((v, i) => new { Index = i, Item = v })
-                         .OrderByDescending(x => x.Item.Layer)
+                         .OrderBy(x => x.Item.Layer)
                          .ThenByDescending(x => x.Item.Height)
                          .ThenByDescending(x => x.Item.Depth * x.Item.Width)
@@ -198,5 +198,5 @@
                 items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Width * v.Depth / clusterRange)) })
                     .GroupBy(x => x.ClusterId)
-                    .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(z => z.Item.Layer).ThenByDescending(y => y.Item.Height).ToList() })
+                    .Select(x => new { Cluster = x.Key, Items = x.OrderBy(z => z.Item.Layer).ThenByDescending(y => y.Item.Height).ToList() })
                     .OrderByDescending(x => x.Cluster)
                     .SelectMany(x => x.Items)
@@ -218,5 +218,5 @@
                 items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Height / clusterRange2)) })
                     .GroupBy(x => x.ClusterId)
-                    .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(z => z.Item.Layer).ThenByDescending(y => y.Item.Depth * y.Item.Width).ToList() })
+                    .Select(x => new { Cluster = x.Key, Items = x.OrderBy(z => z.Item.Layer).ThenByDescending(y => y.Item.Depth * y.Item.Width).ToList() })
                     .OrderByDescending(x => x.Cluster)
                     .SelectMany(x => x.Items)
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj	(revision 15730)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj	(revision 15731)
@@ -113,5 +113,5 @@
     <Compile Include="3D\ExtremePointPruning\IExtremePointPruning.cs" />
     <Compile Include="3D\Geometry\Edge3D.cs" />
-    <Compile Include="3D\Material\FrictionalCoefficientTable.cs" />
+    <Compile Include="3D\Graph\VertexWithItemId.cs" />
     <Compile Include="3D\Material\MaterialType.cs" />
     <Compile Include="3D\Packer\BinPacker.cs" />
@@ -128,4 +128,5 @@
     <Compile Include="3D\Packer\BinPackerFreeVolumeBestFit.cs" />
     <Compile Include="3D\Packer\BinPackerMinRSLeft.cs" />
+    <Compile Include="3D\Packer\BinPackerFormClosure.cs" />
     <Compile Include="3D\Packer\BinPackerResidualSpaceBestFit.cs" />
     <Compile Include="3D\Instances\ThreeDInstanceDescriptor.cs" />
Index: /branches/2817-BinPackingSpeedup/HeuristicLab.Tests/HeuristicLab.Problems.Bin-Packing-3.3/3D/Instances/ThreeDInstanceParserTest.cs
===================================================================
--- /branches/2817-BinPackingSpeedup/HeuristicLab.Tests/HeuristicLab.Problems.Bin-Packing-3.3/3D/Instances/ThreeDInstanceParserTest.cs	(revision 15730)
+++ /branches/2817-BinPackingSpeedup/HeuristicLab.Tests/HeuristicLab.Problems.Bin-Packing-3.3/3D/Instances/ThreeDInstanceParserTest.cs	(revision 15731)
@@ -67,5 +67,5 @@
         Assert.AreEqual(expected.Height, actual.Height);
         Assert.AreEqual(expected.Depth, actual.Depth);
-        Assert.AreEqual(expected.Material, actual.Material);
+        Assert.AreEqual(expected.Layer, actual.Layer);
         Assert.AreEqual(expected.Weight, actual.Weight);
       }
@@ -94,5 +94,5 @@
         Assert.AreEqual(expected.Height, actual.Height);
         Assert.AreEqual(expected.Depth, actual.Depth);
-        Assert.AreEqual(expected.Material, actual.Material);
+        Assert.AreEqual(expected.Layer, actual.Layer);
         Assert.AreEqual(expected.Weight, actual.Weight);
       }
