Changeset 15488

Timestamp:

11/28/17 16:10:31 (6 years ago)

Author:

rhanghof

Message:

#2817:

• Added line projection based bin packing
• Added residual spaces to the view

Location:

branches/2817-BinPackingSpeedup

Files:

• HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml (modified) (1 diff)
• HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml.cs (modified) (14 diffs)
• HeuristicLab.Problems.BinPacking.Views/3.3/PackingPlan3DView.Designer.cs (modified) (6 diffs)
• HeuristicLab.Problems.BinPacking.Views/3.3/PackingPlan3DView.cs (modified) (4 diffs)
• HeuristicLab.Problems.BinPacking/3.3/3D/Algorithms/ExtremePointAlgorithm.cs (modified) (9 diffs)
• HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs (modified) (14 diffs)
• HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3DException.cs (added)
• HeuristicLab.Problems.BinPacking/3.3/3D/Encoding/ExtremePointPermutationDecoder.cs (modified) (5 diffs)
• HeuristicLab.Problems.BinPacking/3.3/3D/Encoding/PermutationProblem.cs (modified) (1 diff)
• HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation (added)
• HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/ExtremePointCreator.cs (added)
• HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/ExtremePointCreatorFactory.cs (added)
• HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/IExtremePointCreator.cs (added)
• HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/LineProjectionBasedEPCreator.cs (added)
• HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/PointProjectionBasedEPCreator.cs (added)
• HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Edge3D.cs (added)
• HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Line3D.cs (modified) (1 diff)
• HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Vector3D.cs (modified) (3 diffs)
• HeuristicLab.Problems.BinPacking/3.3/3D/IOperator.cs (deleted)
• HeuristicLab.Problems.BinPacking/3.3/3D/Instances/3D-TestLineProjection1.txt (added)
• HeuristicLab.Problems.BinPacking/3.3/3D/Instances/3D-TestLineProjection2.txt (added)
• HeuristicLab.Problems.BinPacking/3.3/3D/Instances/3D-TestLineProjection3.txt (added)
• HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPacker.cs (modified) (5 diffs)
• HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFirstFit.cs (modified) (6 diffs)
• HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFreeVolumeBestFit.cs (modified) (5 diffs)
• HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerResidualSpaceBestFit.cs (modified) (6 diffs)
• HeuristicLab.Problems.BinPacking/3.3/3D/Sorting/IOperator.cs (added)
• HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj (modified) (2 diffs)

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml

@@ -33 +33 @@
              >
     <Grid Margin="0,0,-64,-57">
-        <CheckBox Name="showExtremePointsCheckBox" Content="Show extreme points" VerticalAlignment="Top" HorizontalAlignment="Left" Margin="10,6,0,0" Unchecked="showExtremePointsCheckBoxOnUnchecked" Checked="showExtremePointsCheckBoxOnChecked"/>
-        <Border BorderThickness="1" Background="{DynamicResource {x:Static SystemColors.ControlBrushKey}}" Margin="0,30,0,0">
+        <StackPanel>
+            <CheckBox Name="showExtremePointsCheckBox" 
+                      Content="Show extreme points" 
+                      VerticalAlignment="Top" 
+                      HorizontalAlignment="Left" 
+                      Margin="10,6,0,0" 
+                      Unchecked="ShowExtremePointsCheckBoxOnUnchecked" 
+                      Checked="ShowExtremePointsCheckBoxOnChecked"/>
+            <CheckBox Name="showResidualSpaceCheckBox" 
+                      Content="Show residual spaces" 
+                      VerticalAlignment="Top" 
+                      HorizontalAlignment="Left" 
+                      Margin="10,6,0,0" 
+                      Unchecked="ShowResidualSpacesCheckBoxOnUnchecked" 
+                      Checked="ShowResidualSpacesCheckBoxOnChecked"/>
+        </StackPanel>
+        <Border BorderThickness="1" Background="{DynamicResource {x:Static SystemColors.ControlBrushKey}}" Margin="0,52,0,0">
             <Viewport3D Name="viewport3D1" Margin="0,-1,0,0" >
                 <Viewport3D.Camera>

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml.cs

@@ -27 +27 @@
 using System.Windows.Media.Media3D;
 using HeuristicLab.Problems.BinPacking3D;
+using HeuristicLab.Collections;
 
 namespace HeuristicLab.Problems.BinPacking.Views {
@@ -49 +50 @@
     private static readonly Color hiddenColor = Color.FromArgb(0x1A, 0xAA, 0xAA, 0xAA);
     private static readonly Color containerColor = Color.FromArgb(0x7F, 0xAA, 0xAA, 0xAA);
+    private static readonly Color residualSpaceColor = Color.FromArgb(0x7F, 0xAA, 0xAA, 0x00);
 
     private Point startPos;
@@ -55 +57 @@
     private double startAngleY;
     private int selectedItemKey;
+    private int selectedExtremePointIndex;
     private bool showExtremePoints;
+    private bool showResidualSpaces;
 
     private BinPacking<BinPacking3D.PackingPosition, PackingShape, PackingItem> packing;
@@ -70 +74 @@
     private Dictionary<int, DiffuseMaterial> materials;
 
+    public ObservableDictionary<BinPacking3D.PackingPosition, Tuple<int, int, int>> ResidualSpaces { get; set; }
+    public ObservableCollection<BinPacking3D.PackingPosition> ExtremePoints { get; set; }
+
     public Container3DView() {
       InitializeComponent();
       camMain.Position = new Point3D(0.5, 3, 3); // for design time we use a different camera position 
       materials = new Dictionary<int, DiffuseMaterial>();
+      ResidualSpaces = new ObservableDictionary<BinPacking3D.PackingPosition, Tuple<int, int, int>>();
+      ExtremePoints = new ObservableCollection<BinPacking3D.PackingPosition>();
+      selectedExtremePointIndex = -1;
       Clear();
     }
@@ -85 +95 @@
     }
 
+    /// <summary>
+    /// Selects another extreme point
+    /// </summary>
+    /// <param name="index"></param>
+    public void SelectExtremePoint(int index) {
+      selectedExtremePointIndex = index;
+      UpdateVisualization();
+    }
+
     public void SelectItem(int itemKey) {
       // selection of an item should make all other items semi-transparent
@@ -90 +109 @@
       UpdateVisualization();
     }
+
     public void ClearSelection() {
       // remove all transparency
       selectedItemKey = -1;
+      selectedExtremePointIndex = -1;
       UpdateVisualization();
     }
@@ -98 +119 @@
     private void UpdateVisualization() {
       Clear();
-      if (packing == null) return; // nothing to display
+      if (packing == null)
+        return; // nothing to display
 
       var modelGroup = (Model3DGroup)MyModel.Content;
@@ -108 +130 @@
 
         var colorIdx = selectedItem.Value.Material;
-        while (colorIdx < 0) colorIdx += colors.Length;
+        while (colorIdx < 0)
+          colorIdx += colors.Length;
         colorIdx = colorIdx % colors.Length;
         var color = colors[colorIdx];
@@ -132 +155 @@
           modelGroup.Children.Add(model);
         }
+
+
       } else {
         foreach (var item in packing.Items) {
@@ -144 +169 @@
           if (!materials.TryGetValue(item.Value.Material, out material)) {
             var colorIdx = item.Value.Material;
-            while (colorIdx < 0) colorIdx += colors.Length;
+            while (colorIdx < 0)
+              colorIdx += colors.Length;
             colorIdx = colorIdx % colors.Length;
             var color = colors[colorIdx];
@@ -156 +182 @@
       }
 
-      if (showExtremePoints) {
-        // draw extreme-points
-        var maxMag = (int)Math.Log10(Math.Max(packing.BinShape.Depth, Math.Max(packing.BinShape.Height, packing.BinShape.Width)));
-        var cubeSize = (int)Math.Max(Math.Pow(10, maxMag - 2), 1);
-        foreach (var ep in packing.ExtremePoints) {
-          var epModel = new GeometryModel3D { Geometry = new MeshGeometry3D(), Material = new DiffuseMaterial() { Brush = new SolidColorBrush(Colors.Red) } };
-          AddSolidCube((MeshGeometry3D)epModel.Geometry, ep.X, ep.Y, ep.Z, cubeSize, cubeSize, cubeSize);
-          modelGroup.Children.Add(epModel);
-        }
-      }
+
+      AddExtremePoints(modelGroup);
 
       var container = packing.BinShape;
@@ -191 +209 @@
     }
 
+    private void AddExtremePoints(Model3DGroup modelGroup) {
+      if (showExtremePoints) {
+        // draw extreme-points
+        var maxMag = (int)Math.Log10(Math.Max(packing.BinShape.Depth, Math.Max(packing.BinShape.Height, packing.BinShape.Width)));
+        var cubeSize = (int)Math.Max(Math.Pow(10, maxMag - 2), 1);
+        BinPacking3D.PackingPosition selectedExtremePoint = null;
+        if (selectedExtremePointIndex < 0) {
+          foreach (var ep in ExtremePoints) {
+            AddResidualSpacesForExtremePoint(modelGroup, ep);
+          }
+        } else {
+          selectedExtremePoint = ExtremePoints.ToList()[selectedExtremePointIndex];
+          AddResidualSpacesForExtremePoint(modelGroup, selectedExtremePoint);
+        }
+
+        foreach (var ep in ExtremePoints) {
+          Color color;
+          if (ep.Equals(selectedExtremePoint)) {
+            color = Colors.Yellow;
+          } else {
+            color = Colors.Red;
+          }
+          var epModel = new GeometryModel3D { Geometry = new MeshGeometry3D(), Material = new DiffuseMaterial() { Brush = new SolidColorBrush(color) } };
+          AddSolidCube((MeshGeometry3D)epModel.Geometry, ep.X, ep.Y, ep.Z, cubeSize, cubeSize, cubeSize);
+          modelGroup.Children.Add(epModel);
+        }
+      }
+    }
+
+    private void AddResidualSpacesForExtremePoint(Model3DGroup modelGroup, BinPacking3D.PackingPosition extremePoint) {
+      if (showResidualSpaces) {
+        var rs = ResidualSpaces[extremePoint];
+        var containerModel1 = new GeometryModel3D(new MeshGeometry3D(), new DiffuseMaterial(new SolidColorBrush(residualSpaceColor)));
+
+        modelGroup.Children.Add(containerModel1);
+        AddWireframeCube((MeshGeometry3D)containerModel1.Geometry,
+          extremePoint.X,
+          extremePoint.Y,
+          extremePoint.Z,
+          rs.Item1,
+          rs.Item2,
+          rs.Item3);
+
+      }
+    }
+
 
     private void Clear() {
@@ -202 +266 @@
 
     private void Container3DView_MouseMove(object sender, MouseEventArgs e) {
-      if (!mouseDown) return;
+      if (!mouseDown)
+        return;
       var pos = e.GetPosition((IInputElement)this);
 
@@ -235 +300 @@
       Focus(); // for mouse wheel events
     }
-    private void showExtremePointsCheckBoxOnChecked(object sender, RoutedEventArgs e) {
+    private void ShowExtremePointsCheckBoxOnChecked(object sender, RoutedEventArgs e) {
       showExtremePoints = true;
       UpdateVisualization();
     }
-    private void showExtremePointsCheckBoxOnUnchecked(object sender, RoutedEventArgs e) {
+    private void ShowExtremePointsCheckBoxOnUnchecked(object sender, RoutedEventArgs e) {
       showExtremePoints = false;
+      UpdateVisualization();
+    }
+
+    private void ShowResidualSpacesCheckBoxOnChecked(object sender, RoutedEventArgs e) {
+      showResidualSpaces = true;
+      UpdateVisualization();
+    }
+    private void ShowResidualSpacesCheckBoxOnUnchecked(object sender, RoutedEventArgs e) {
+      showResidualSpaces = false;
       UpdateVisualization();
     }

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/PackingPlan3DView.Designer.cs

@@ -49 +49 @@
       this.elementHost = new System.Windows.Forms.Integration.ElementHost();
       this.packingPlan3D = new HeuristicLab.Problems.BinPacking.Views.Container3DView();
+      this.extremePointsSelection = new System.Windows.Forms.ListBox();
       this.SuspendLayout();
       // 
@@ -58 +59 @@
       this.binSelection.Location = new System.Drawing.Point(3, 3);
       this.binSelection.Name = "binSelection";
-      this.binSelection.Size = new System.Drawing.Size(54, 290);
+      this.binSelection.Size = new System.Drawing.Size(54, 264);
       this.binSelection.TabIndex = 4;
       this.binSelection.SelectedIndexChanged += new System.EventHandler(this.binSelection_SelectedIndexChanged);
@@ -69 +70 @@
       this.itemSelection.Location = new System.Drawing.Point(58, 3);
       this.itemSelection.Name = "itemSelection";
-      this.itemSelection.Size = new System.Drawing.Size(55, 290);
+      this.itemSelection.Size = new System.Drawing.Size(55, 264);
       this.itemSelection.TabIndex = 5;
       this.itemSelection.SelectedIndexChanged += new System.EventHandler(this.itemSelection_SelectedIndexChanged);
@@ -78 +79 @@
             | System.Windows.Forms.AnchorStyles.Left) 
             | System.Windows.Forms.AnchorStyles.Right)));
-      this.elementHost.Location = new System.Drawing.Point(119, 3);
+      this.elementHost.Location = new System.Drawing.Point(198, 3);
       this.elementHost.Name = "elementHost";
-      this.elementHost.Size = new System.Drawing.Size(229, 290);
+      this.elementHost.Size = new System.Drawing.Size(273, 264);
       this.elementHost.TabIndex = 6;
       this.elementHost.Text = "elementHost";
       this.elementHost.Child = this.packingPlan3D;
+      // 
+      // extremePointsSelection
+      // 
+      this.extremePointsSelection.Anchor = ((System.Windows.Forms.AnchorStyles)(((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Bottom) 
+            | System.Windows.Forms.AnchorStyles.Left)));
+      this.extremePointsSelection.FormattingEnabled = true;
+      this.extremePointsSelection.Location = new System.Drawing.Point(115, 3);
+      this.extremePointsSelection.Name = "extremePointsSelection";
+      this.extremePointsSelection.Size = new System.Drawing.Size(77, 264);
+      this.extremePointsSelection.TabIndex = 7;
+      this.extremePointsSelection.SelectedIndexChanged += new System.EventHandler(this.extremePointsSelection_SelectedIndexChanged);
       // 
       // PackingPlan3DView
@@ -89 +101 @@
       this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
       this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
+      this.Controls.Add(this.extremePointsSelection);
       this.Controls.Add(this.elementHost);
       this.Controls.Add(this.itemSelection);
       this.Controls.Add(this.binSelection);
       this.Name = "PackingPlan3DView";
-      this.Size = new System.Drawing.Size(351, 299);
+      this.Size = new System.Drawing.Size(489, 278);
       this.ResumeLayout(false);
 
@@ -104 +117 @@
     private System.Windows.Forms.Integration.ElementHost elementHost;
     private Container3DView packingPlan3D;
+    private System.Windows.Forms.ListBox extremePointsSelection;
   }
 }

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/PackingPlan3DView.cs

@@ -47 +47 @@
       } else {
         int i = 0;
-        foreach (var bp in Content.Bins)
+        foreach (var bp in Content.Bins) {
           binSelection.Items.Add(i++ + " (" + Math.Round(bp.PackingDensity * 100, 2) + "%)");
+        }
+
 
         binSelection.SelectedIndex = 0;
@@ -63 +65 @@
       itemSelection.SelectedIndex = -1;
       itemSelection.Items.Clear();
+      extremePointsSelection.Items.Clear();
+      packingPlan3D.ResidualSpaces.Clear();
+      packingPlan3D.ExtremePoints.Clear();
 
       // add items of this container
@@ -69 +74 @@
       foreach (var item in packing.Items) {
         itemSelection.Items.Add(item.Key);
+      }
+      foreach (var ep in packing.ExtremePoints) {
+        var rs = ((BinPacking3D.BinPacking3D)packing).ResidualSpace[ep];
+        extremePointsSelection.Items.Add($"({ep.X}, {ep.Y}, {ep.Z})");
+        packingPlan3D.ExtremePoints.Add(ep);
+        packingPlan3D.ResidualSpaces.Add(ep, rs);
       }
 
@@ -81 +92 @@
         packingPlan3D.ClearSelection();
     }
+
+    private void extremePointsSelection_SelectedIndexChanged(object sender, EventArgs e) {
+      if (extremePointsSelection != null && extremePointsSelection.SelectedIndex >= 0) {
+        packingPlan3D.SelectExtremePoint(extremePointsSelection.SelectedIndex);
+      } else {
+        packingPlan3D.ClearSelection();
+      }
+    }
   }
 }

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Algorithms/ExtremePointAlgorithm.cs

@@ -42 +42 @@
   public enum FittingMethod { All, FirstFit, ResidualSpaceBestFit, FreeVolumeBestFit }
 
+  public enum ExtremePointCreationMethod { All, PointProjection, LineProjection }
+
   [Item("Extreme-point-based Bin Packing (3d)", "An implementation of the extreme-point based packing described in Crainic, T. G., Perboli, G., & Tadei, R. (2008). Extreme point-based heuristics for three-dimensional bin packing. Informs Journal on computing, 20(3), 368-384.")]
   [StorableClass]
@@ -83 +85 @@
     public IValueParameter<BoolValue> SortByMaterialParameter {
       get { return sortByMaterialParameter; }
-    }    
+    }
+
+    [Storable]
+    private readonly IValueParameter<EnumValue<ExtremePointCreationMethod>> extremePointCreationMethodParameter;
+    public IValueParameter<EnumValue<ExtremePointCreationMethod>> ExtremePointCreationMethodParameter {
+      get { return extremePointCreationMethodParameter; }
+    }
 
     [StorableConstructor]
@@ -100 +108 @@
         "FittingMethod", "Which method to fit should be used.", new EnumValue<FittingMethod>(FittingMethod.All)));
 
+      Parameters.Add(extremePointCreationMethodParameter = new ValueParameter<EnumValue<ExtremePointCreationMethod>>(
+        "ExtremePointCreationMethod", "Which method should be used for creatomg extreme points.", new EnumValue<ExtremePointCreationMethod>(ExtremePointCreationMethod.All)));
+
       Parameters.Add(deltaParameter = new ValueParameter<PercentValue>(
         "Delta", "[1;100]% Clustered sorting methods use a delta parameter to determine the clusters.", new PercentValue(.1)));
@@ -124 +135 @@
       var items = Problem.Items;
       var bin = Problem.BinShape;
+
       var sorting = new[] { SortingMethodParameter.Value.Value };
       if (sorting[0] == SortingMethod.All) {
         sorting = Enum.GetValues(typeof(SortingMethod)).Cast<SortingMethod>().Where(x => x != SortingMethod.All).ToArray();
       }
+
       var fitting = new[] { fittingMethodParameter.Value.Value };
       if (fitting[0] == FittingMethod.All) {
@@ -133 +146 @@
       }
 
+      var extremePointCreation = new[] { ExtremePointCreationMethodParameter.Value.Value };
+      if (extremePointCreation[0] == ExtremePointCreationMethod.All) {
+        extremePointCreation = Enum.GetValues(typeof(ExtremePointCreationMethod))
+                                     .Cast<ExtremePointCreationMethod>()
+                                     .Where(x => x != ExtremePointCreationMethod.All)
+                                     .ToArray();
+      }
+
       //
-      var result = GetBest(bin, items, sorting, fitting, token);
+      var result = GetBest(bin, items, sorting, fitting, extremePointCreation, token);
       if (result == null) {
         throw new InvalidOperationException("No result obtained!");
@@ -162 +183 @@
           new EnumValue<FittingMethod>(result.Item4.Value)));
       }
+
+      if (result.Item5.HasValue && extremePointCreation.Length > 1) {
+        Results.Add(new Result("Best extreme point creation method",
+          "The extreme point creation method that found the best solution",
+          new EnumValue<ExtremePointCreationMethod>(result.Item5.Value)));
+      }
     }
 
@@ -173 +200 @@
     /// <param name="token"></param>
     /// <returns></returns>
-    private Tuple<Solution, double, SortingMethod?, FittingMethod?> GetBest(PackingShape bin, IList<PackingItem> items, SortingMethod[] sortings, FittingMethod[] fittings, CancellationToken token) {
+    private Tuple<Solution, double, SortingMethod?, FittingMethod?, ExtremePointCreationMethod?> 
+          GetBest(PackingShape bin, 
+                  IList<PackingItem> items, 
+                  SortingMethod[] sortings, 
+                  FittingMethod[] fittings,
+                  ExtremePointCreationMethod[] ePGeneration,
+                  CancellationToken token) {
       SortingMethod? bestSorting = null;
       FittingMethod? bestFitting = null;
+      ExtremePointCreationMethod? bestEPCreation = null;
       var best = double.NaN;
       Solution bestSolution = null;
       foreach (var fit in fittings) {
         foreach (var sort in sortings) {
-          IDecoder<Permutation> decoder = new ExtremePointPermutationDecoder(BinPackerFactory.CreateBinPacker(fit));
-          Permutation sortedItems;
+          foreach (var epCreation in ePGeneration) {
+            IDecoder<Permutation> decoder = new ExtremePointPermutationDecoder() {
+              FittingMethod = fit,
+              ExtremePointCreationMethod = epCreation
+            };
+            Permutation sortedItems;
                     
-          if (SortByMaterialParameter.Value.Value) {
-            sortedItems = SortItemsByMaterialAndSortingMethod(bin, items, sort, DeltaParameter.Value.Value);
-          } else {
-            sortedItems = SortItemsBySortingMethod(bin, items, sort, DeltaParameter.Value.Value);
-          }
+            if (SortByMaterialParameter.Value.Value) {
+              sortedItems = SortItemsByMaterialAndSortingMethod(bin, items, sort, DeltaParameter.Value.Value);
+            } else {
+              sortedItems = SortItemsBySortingMethod(bin, items, sort, DeltaParameter.Value.Value);
+            }
+
+            var result = Optimize(new OptimaizationParamters() {
+              SortedItems = sortedItems,
+              Bin = bin,
+              Items = items,
+              StackingConstraints = Problem.UseStackingConstraints,
+              Decoder = decoder,
+              Evaluator = Problem.SolutionEvaluator,
+              ExtremePointGeneration = epCreation
+            });
           
-          var result = Optimize(sortedItems, bin, items, Problem.UseStackingConstraints, decoder, Problem.SolutionEvaluator);
-          
-          if (double.IsNaN(result.Item2) || double.IsInfinity(result.Item2)) {
-            continue;
-          }
-
-          if (double.IsNaN(best) || Problem.Maximization && result.Item2 > best || !Problem.Maximization && result.Item2 < best) {
-            bestSolution = result.Item1;
-            best = result.Item2;
-            bestSorting = sort;
-            bestFitting = fit;
-          }
-          if (token.IsCancellationRequested) {
-            return Tuple.Create(bestSolution, best, bestSorting, bestFitting);
+            if (double.IsNaN(result.Item2) || double.IsInfinity(result.Item2)) {
+              continue;
+            }
+
+            if (double.IsNaN(best) || Problem.Maximization && result.Item2 > best || !Problem.Maximization && result.Item2 < best) {
+              bestSolution = result.Item1;
+              best = result.Item2;
+              bestSorting = sort;
+              bestFitting = fit;
+              bestEPCreation = epCreation;
+            }
+            if (token.IsCancellationRequested) {
+              return Tuple.Create(bestSolution, best, bestSorting, bestFitting, bestEPCreation);
+            }
           }
         }
@@ -209 +257 @@
         return null;
       }
-      return Tuple.Create(bestSolution, best, bestSorting, bestFitting);
+      return Tuple.Create(bestSolution, best, bestSorting, bestFitting, bestEPCreation);
     }
 
@@ -215 +263 @@
     /// Returns a tuple with the solution and the packing ratio depending on the given parameters
     /// </summary>
-    /// <param name="sortedItems"></param>
-    /// <param name="bin"></param>
-    /// <param name="items"></param>
-    /// <param name="stackingConstraints"></param>
-    /// <param name="decoder"></param>
-    /// <param name="evaluator"></param>
+    /// <param name="parameters"></param>
     /// <returns></returns>
-    private static Tuple<Solution, double> Optimize(Permutation sortedItems, PackingShape bin, IList<PackingItem> items, bool stackingConstraints, IDecoder<Permutation> decoder, IEvaluator evaluator) { 
+    private static Tuple<Solution, double> Optimize(OptimaizationParamters parameters) { 
       
-      var sol = decoder.Decode(sortedItems, bin, items, stackingConstraints);
-      var fit = evaluator.Evaluate(sol);
+      var sol = parameters.Decoder.Decode(parameters.SortedItems, parameters.Bin, parameters.Items, parameters.StackingConstraints);
+      var fit = parameters.Evaluator.Evaluate(sol);
 
       return Tuple.Create(sol, fit);
+    }
+
+    private class OptimaizationParamters {
+      public Permutation SortedItems { get; set; }
+      public PackingShape Bin { get; set; }
+      public IList<PackingItem> Items { get; set; }
+      public bool StackingConstraints { get; set; }
+      public IDecoder<Permutation> Decoder { get; set; }
+      public IEvaluator Evaluator { get; set; }
+      public ExtremePointCreationMethod ExtremePointGeneration { get; set; }
     }
     

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

@@ -28 +28 @@
 using HeuristicLab.Problems.BinPacking;
 using HeuristicLab.Problems.BinPacking3D.Geometry;
+using HeuristicLab.Collections;
 
 namespace HeuristicLab.Problems.BinPacking3D {
@@ -35 +36 @@
 
     [Storable]
-    public Dictionary<PackingPosition, Tuple<int, int, int>> ResidualSpace { get; protected set; }
+    public Dictionary<PackingPosition, Tuple<int, int, int>> ResidualSpace { get; set; }
+
+
+
 
     public BinPacking3D(PackingShape binShape)
       : base(binShape) {
       ResidualSpace = new Dictionary<PackingPosition, Tuple<int, int, int>>();
-      AddExtremePoint(binShape.Origin);
+      
+      ExtremePoints.Add(binShape.Origin);
+      ResidualSpace.Add(binShape.Origin, new Tuple<int, int, int>(BinShape.Width, BinShape.Height, BinShape.Depth));
+
+//      AddExtremePoint(binShape.Origin);
     }
     [StorableConstructor]
@@ -63 +71 @@
       #endregion
     }
+
+
+
 
     /// <summary>
@@ -77 +88 @@
     }
 
+    /*
     /// <summary>
     /// Updates the extreme points of the bin
@@ -89 +101 @@
         UpdateExtremePointsWithoutStackingConstriants(item, position);
       }
-    }
-
+    }*/
+
+
+      /*
     /// <summary>
     /// Updates the extreme points of the bin. 
@@ -98 +112 @@
     /// <param name="position"></param>
     private void UpdateExtremePointsWithStackingConstriants(PackingItem newItem, PackingPosition position) {
-
-      //UpdateExtremePointsWithoutStackingConstriants(newItem, position);
-      //return;
-
       int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
       int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
@@ -110 +120 @@
       AddExtremePoint(ep2);
       AddExtremePoint(ep3);
-    }
-
-    private Tuple<int, int, int> CalculateResidualSpace(Vector3D pos) {
-      var itemPos = Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] });
-      Vector3D limit = new Vector3D() { X = BinShape.Width, Y = BinShape.Height, Z = BinShape.Depth };
-      if (pos.X < limit.X && pos.Y < limit.Y && pos.Z < limit.Z) {
-        var rightLimit = ProjectRight(pos);
-        var upLimit = ProjectUp(pos);
-        var forwardLimit = ProjectForward(pos);
-        if (rightLimit.X > 0) {
-          limit.X = rightLimit.X;
-        }
-        if (upLimit.Y > 0) {
-          limit.Y = upLimit.Y;
-        }
-        if (forwardLimit.Z > 0) {
-          limit.Z = forwardLimit.Z;
-        }
-      }
-
-      if (limit.X - pos.X <= 0 || limit.Y - pos.Y <= 0 || limit.Z - pos.Z <= 0) {
-        return Tuple.Create(0, 0, 0);
-      }
-      return Tuple.Create(limit.X - pos.X, limit.Y - pos.Y, limit.Z - pos.Z);
-    }
-
-
-    private Vector3D CreateRs(PackingPosition position) {
-      return new Vector3D() { X = position.X, Y = position.Y, Z = position.Z };
-    }
-
-    private void UpdateExtremePointsWithoutStackingConstriants(PackingItem item, PackingPosition position) {
-      GenerateNewExtremePointsForNewItem(item, position);
-
-      // if an item is fit in below, before, or left of another its extreme points have to be regenerated
-      foreach (var above in GetItemsAbove(position)) {
-        GenerateNewExtremePointsForNewItem(above.Item2, above.Item1);
-      }
-      foreach (var front in GetItemsInfront(position)) {
-        GenerateNewExtremePointsForNewItem(front.Item2, front.Item1);
-      }
-      foreach (var right in GetItemsOnRight(position)) {
-        GenerateNewExtremePointsForNewItem(right.Item2, right.Item1);
-      }
-    }
-
-
+    }*/
+
+     
+
+    #region Position feasability
 
     /// <summary>
     /// In this case feasability is defined as following: 
-    /// 1. the item fits into the bin-borders; 
-    /// 2. the point is supported by something; 
-    /// 3. the item does not collide with another already packed item
-    /// 
-    /// Unfortunatelly this method does not support item rotation
+    /// 1. the point is supported by something; 
+    /// 2. the item does not collide with another already packed item
     /// </summary>
     /// <param name="item"></param>
@@ -171 +136 @@
     /// <returns></returns>
     public override bool IsPositionFeasible(PackingItem item, PackingPosition position, bool stackingConstraints) {
-      var b1 = CheckItemDimensions(item);
+      //var b1 = CheckItemDimensions(item, position);
       var b2 = ItemCanBePlaced(item, position);
       var b3 = CheckStackingConstraints(item, position, stackingConstraints);
 
-      return b1 && b2 && b3;
-    }
-
-    /// <summary>
-    /// Compares the dimensions of a given item and the current bin. 
-    /// </summary>
-    /// <param name="item"></param>
-    /// <returns>Returns true if the dimensions of an given item are less or equal to the bin.</returns>
-    private bool CheckItemDimensions(PackingItem item) {
-      return BinShape.Width >= item.Width && BinShape.Height >= item.Height && BinShape.Depth >= item.Depth;
+      return b2 && b3;
     }
 
@@ -194 +150 @@
     /// <returns></returns>
     private bool ItemCanBePlaced(PackingItem givenItem, PackingPosition givenItemPosition) {
+      var width = givenItemPosition.Rotated ? givenItem.Depth : givenItem.Width;
+      var depth = givenItemPosition.Rotated ? givenItem.Width : givenItem.Depth;
       // Check if the boundings of the bin would injured
-      if (givenItemPosition.X + givenItem.Width > BinShape.Width ||
+      if (givenItemPosition.X + width > BinShape.Width ||
           givenItemPosition.Y + givenItem.Height > BinShape.Height ||
-          givenItemPosition.Z + givenItem.Depth > BinShape.Depth) {
+          givenItemPosition.Z + depth > BinShape.Depth) {
         return false;
       }
@@ -242 +200 @@
       return IsStaticStable(item, position) && IsWeightSupported(item, position);
     }
-
 
     /// <summary>
@@ -298 +255 @@
       p4 = itemsP4.Where(x => position.X < x.Item1.X + x.Item2.Width && position.Z + item.Depth > x.Item1.Z).Any();
     }
-
 
     /// <summary>
@@ -337 +293 @@
     }
 
-
     /// <summary>
     /// Checks if a given the weight of an given item is supportet by the items below.
@@ -360 +315 @@
         itemsP4.Where(x => x.Item2.SupportsStacking(item)).Any();
     }
+
+    #endregion
+
+    protected override void GenerateNewExtremePointsForNewItem(PackingItem newItem, PackingPosition position) {
+      throw new NotImplementedException();
+    }
+
+    #region Get items
     
-
-    /// <summary>
-    /// Generates new extreme points for a given item and its position.
-    /// It also recalcualtes the residual space and removes the extreme points which are not needed any more.
-    /// </summary>
-    /// <param name="newItem"></param>
-    /// <param name="position"></param>
-    protected override void GenerateNewExtremePointsForNewItem(PackingItem newItem, PackingPosition position) {
-      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
-      int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
-
-      var itemPlacement = Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] }).ToList();
-      // Find ExtremePoints beginning from sourcepointX
-      var sourcePoint = new Vector3D() { X = position.X + newWidth, Y = position.Y, Z = position.Z };
-      if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) {
-        // Projecting onto the XZ-plane
-        var below = ProjectDown(sourcePoint);
-        var residualSpace = CalculateResidualSpace(below);
-        if (IsNonZero(residualSpace)
-          && !IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) {
-          // add only if the projected point's residual space is not a sub-space
-          // of another extreme point's residual space
-          var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z);
-          AddExtremePoint(belowPoint);
-        }
-        // Projecting onto the XY-plane
-        var back = ProjectBackward(sourcePoint);
-        residualSpace = CalculateResidualSpace(back);
-        if (IsNonZero(residualSpace)
-          && !IsWithinResidualSpaceOfAnotherExtremePoint(back, residualSpace)) {
-          // add only if the projected point's residual space is not a sub-space
-          // of another extreme point's residual space
-          var backPoint = new PackingPosition(position.AssignedBin, back.X, back.Y, back.Z);
-          AddExtremePoint(backPoint);
-        }
-      }
-
-      //Find ExtremePoints beginning from sourcepointY
-      sourcePoint = new Vector3D(position.X, position.Y + newItem.Height, position.Z);
-      if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) {
-        // Projecting onto the YZ-plane
-        var left = ProjectLeft(sourcePoint);
-        var residualSpace = CalculateResidualSpace(left);
-        if (IsNonZero(residualSpace)
-          && !IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) {
-          // add only if the projected point's residual space is not a sub-space
-          // of another extreme point's residual space
-          var leftPoint = new PackingPosition(position.AssignedBin, left.X, left.Y, left.Z);
-          AddExtremePoint(leftPoint);
-        }
-        // Projecting onto the XY-plane
-        var back = ProjectBackward(sourcePoint);
-        residualSpace = CalculateResidualSpace(back);
-        if (IsNonZero(residualSpace)
-          && !IsWithinResidualSpaceOfAnotherExtremePoint(back, residualSpace)) {
-          // add only if the projected point's residual space is not a sub-space
-          // of another extreme point's residual space
-          var backPoint = new PackingPosition(position.AssignedBin, back.X, back.Y, back.Z);
-          AddExtremePoint(backPoint);
-        }
-      }
-
-      //Find ExtremePoints beginning from sourcepointZ
-      sourcePoint = new Vector3D(position.X, position.Y, position.Z + newDepth);
-      if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) {
-        // Projecting onto the XZ-plane
-        var below = ProjectDown(sourcePoint);
-        var residualSpace = CalculateResidualSpace(below);
-        if (IsNonZero(residualSpace)
-          && !IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) {
-          // add only if the projected point's residual space is not a sub-space
-          // of another extreme point's residual space
-          var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z);
-          AddExtremePoint(belowPoint);
-        }
-        // Projecting onto the YZ-plane
-        var left = ProjectLeft(sourcePoint);
-        residualSpace = CalculateResidualSpace(left);
-        if (IsNonZero(residualSpace)
-          && !IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) {
-          // add only if the projected point's residual space is not a sub-space
-          // of another extreme point's residual space
-          var leftPoint = new PackingPosition(position.AssignedBin, left.X, left.Y, left.Z);
-          AddExtremePoint(leftPoint);
-        }
-      }
-    }
-
-    /// <summary>
-    /// Returns true if all values of a given tuple are not zero
-    /// </summary>
-    /// <param name="rs">Tuple with three integer values which represents a residual space</param>
-    /// <returns></returns>
-    private bool IsNonZero(Tuple<int, int, int> rs) {
-      return rs.Item1 > 0 && rs.Item2 > 0 && rs.Item3 > 0;
-    }
-
-    /// <summary>
-    /// 
-    /// </summary>
-    /// <param name="pos"></param>
-    /// <param name="residualSpace"></param>
-    /// <returns></returns>
-    private bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> residualSpace) {
-      var eps = ExtremePoints.Where(x => !pos.Equals(x) && pos.IsInside(x, ResidualSpace[x]));
-      return eps.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, residualSpace, x, ResidualSpace[x]));
-    }
-    private bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> rsPos, PackingPosition ep, Tuple<int, int, int> rsEp) {
-      return rsEp.Item1 >= pos.X - ep.X + rsPos.Item1
-          && rsEp.Item2 >= pos.Y - ep.Y + rsPos.Item2
-          && rsEp.Item3 >= pos.Z - ep.Z + rsPos.Item3;
-    }
-
-    /// <summary>
-    /// Adds an extrem point to the extreme point collection of the bin packing.
-    /// </summary>
-    /// <param name="pos">Position of the new extreme point</param>
-    /// <returns>Retruns true if the extreme point could be added</returns>
-    private bool AddExtremePoint(PackingPosition pos) {
-      if (ExtremePoints.Add(pos)) {
-        var rs = CalculateResidualSpace(new Vector3D(pos));
-        ResidualSpace.Add(pos, rs);
-        // Check if the existing extreme points are shadowed by the new point
-        // This is, their residual space fit entirely into the residual space of the new point
-        foreach (var ep in ExtremePoints.Where(x => x != pos && new Vector3D(x).IsInside(pos, rs)).ToList()) {
-          if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), ResidualSpace[ep], pos, rs)) {
-            ExtremePoints.Remove(ep);
-            ResidualSpace.Remove(ep);
-          }
-        }
-        return true;
-      }
-      return false;
-    }
-
-    #region Projections
-
-    private Vector3D ProjectBackward(Vector3D pos) {
-      var line = new Line3D(pos, new Vector3D(0, 0, -1));
-      return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })
-                  .Select(x => new Plane3D(x.Position, x.Item, Side.Front))
-                  .Concat(new[] { new Plane3D(BinShape, Side.Back) })
-                  .Select(x => x.Intersect(line))
-                  .Where(x => x != null && x.Z <= pos.Z)
-                  .MaxItems(x => x.Z).First();
-    }
-
-    private Vector3D ProjectLeft(Vector3D pos) {
-      var line = new Line3D(pos, new Vector3D(-1, 0, 0));
-      return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })
-                  .Select(x => new Plane3D(x.Position, x.Item, Side.Right))
-                  .Concat(new[] { new Plane3D(BinShape, Side.Left) })
-                  .Select(x => x.Intersect(line))
-                  .Where(x => x != null && x.X <= pos.X)
-                  .MaxItems(x => x.X).First();
-    }
-
-    private Vector3D ProjectDown(Vector3D pos) {
-      var line = new Line3D(pos, new Vector3D(0, -1, 0));
-      return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })
-                  .Select(x => new Plane3D(x.Position, x.Item, Side.Top))
-                  .Concat(new[] { new Plane3D(BinShape, Side.Bottom) })
-                  .Select(x => x.Intersect(line))
-                  .Where(x => x != null && x.Y <= pos.Y)
-                  .MaxItems(x => x.Y).First();
-    }
-
-    private Vector3D ProjectForward(Vector3D pos) {
-      var line = new Line3D(pos, new Vector3D(0, 0, 1));
-      return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })
-                  .Select(x => new Plane3D(x.Position, x.Item, Side.Back))
-                  .Concat(new[] { new Plane3D(BinShape, Side.Front) })
-                  .Select(x => x.Intersect(line))
-                  .Where(x => x != null && x.Z >= pos.Z)
-                  .MinItems(x => x.Z).First();
-    }
-
-    private Vector3D ProjectRight(Vector3D pos) {
-      var line = new Line3D(pos, new Vector3D(1, 0, 0));
-      return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })
-                  .Select(x => new Plane3D(x.Position, x.Item, Side.Left))
-                  .Concat(new[] { new Plane3D(BinShape, Side.Right) })
-                  .Select(x => x.Intersect(line))
-                  .Where(x => x != null && x.X >= pos.X)
-                  .MinItems(x => x.X).First();
-    }
-
-    private Vector3D ProjectUp(Vector3D pos) {
-      var line = new Line3D(pos, new Vector3D(0, 1, 0));
-      return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })
-                  .Select(x => new Plane3D(x.Position, x.Item, Side.Bottom))
-                  .Concat(new[] { new Plane3D(BinShape, Side.Top) })
-                  .Select(x => x.Intersect(line))
-                  .Where(x => x != null && x.Y >= pos.Y)
-                  .MinItems(x => x.Y).First();
-    }
-    #endregion
-
-    #region Get items
-
-    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsAbove(PackingPosition pos) {
-      var line = new Line3D(pos, new Vector3D(0, 1, 0));
-      return Items.Select(x => new {
-        Item = x.Value,
-        Position = Positions[x.Key],
-        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Bottom))
-      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
-        .Select(x => Tuple.Create(x.Position, x.Item));
-    }
-
-    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsInfront(PackingPosition pos) {
-      var line = new Line3D(pos, new Vector3D(0, 0, 1));
-      return Items.Select(x => new {
-        Item = x.Value,
-        Position = Positions[x.Key],
-        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Back))
-      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
-        .Select(x => Tuple.Create(x.Position, x.Item));
-    }
-
-    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnRight(PackingPosition pos) {
-      var line = new Line3D(pos, new Vector3D(1, 0, 0));
-      return Items.Select(x => new {
-        Item = x.Value,
-        Position = Positions[x.Key],
-        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Left))
-      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
-        .Select(x => Tuple.Create(x.Position, x.Item));
-    }
-
     private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(PackingPosition pos) {
       var line = new Line3D(pos, new Vector3D(0, 1, 0));
@@ -601 +334 @@
     }
 
-    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBehind(PackingPosition pos) {
-      var line = new Line3D(pos, new Vector3D(0, 0, 1));
-      return Items.Select(x => new {
-        Item = x.Value,
-        Position = Positions[x.Key],
-        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Front))
-      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
-        .Select(x => Tuple.Create(x.Position, x.Item));
-    }
-
-    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnLeft(PackingPosition pos) {
-      var line = new Line3D(pos, new Vector3D(1, 0, 0));
-      return Items.Select(x => new {
-        Item = x.Value,
-        Position = Positions[x.Key],
-        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Right))
-      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
-        .Select(x => Tuple.Create(x.Position, x.Item));
-    }
-
     #endregion
-
-
-
-    /// <summary>
-    /// Updates the resiual space for a packing item.
-    /// </summary>
-    /// <param name="item"></param>
-    /// <param name="pos"></param>
-    public void UpdateResidualSpace(PackingItem item, PackingPosition pos) {
-      foreach (var ep in ExtremePoints.ToList()) {
-        var rs = ResidualSpace[ep];
-        var depth = pos.Rotated ? item.Width : item.Depth;
-        var width = pos.Rotated ? item.Depth : item.Width;
-        var changed = false;
-        if (ep.Z >= pos.Z && ep.Z < pos.Z + depth) {
-          if (ep.X <= pos.X && ep.Y >= pos.Y && ep.Y < pos.Y + item.Height) {
-            var diff = pos.X - ep.X;
-            var newRSX = Math.Min(rs.Item1, diff);
-            rs = Tuple.Create(newRSX, rs.Item2, rs.Item3);
-            changed = true;
-          }
-          if (ep.Y <= pos.Y && ep.X >= pos.X && ep.X < pos.X + width) {
-            var diff = pos.Y - ep.Y;
-            var newRSY = Math.Min(rs.Item2, diff);
-            rs = Tuple.Create(rs.Item1, newRSY, rs.Item3);
-            changed = true;
-          }
-        }
-
-        if (ep.Z <= pos.Z &&
-            ep.Y >= pos.Y && ep.Y < pos.Y + item.Height &&
-            ep.X >= pos.X && ep.X < pos.X + width) {
-          var diff = pos.Z - ep.Z;
-          var newRSZ = Math.Min(rs.Item3, diff);
-          rs = Tuple.Create(rs.Item1, rs.Item2, newRSZ);
-          changed = true;
-        }
-
-        if (changed) {
-          if (IsNonZero(rs) && !IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), rs)) {
-            ResidualSpace[ep] = rs;
-          } else {
-            ExtremePoints.Remove(ep);
-            ResidualSpace.Remove(ep);
-          }
-        }
-      }
-      return;
-    }
   }
 }

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Encoding/ExtremePointPermutationDecoder.cs

@@ -30 +30 @@
 using HeuristicLab.Common;
 using HeuristicLab.Problems.BinPacking3D.Packer;
+using HeuristicLab.Parameters;
+using HeuristicLab.Data;
 
 namespace HeuristicLab.Problems.BinPacking3D.Encoding {
@@ -38 +40 @@
   [Item("Extreme-point Permutation Decoder (3d) Base", "Base class for 3d decoders")]
   [StorableClass]
-  public class ExtremePointPermutationDecoder : Item, IDecoder<Permutation>
-    //where TBinPacker : BinPacker, new ()
-    {
+  public class ExtremePointPermutationDecoder : ParameterizedNamedItem, IDecoder<Permutation> {
+
+    [Storable]
+    private IValueParameter<EnumValue<FittingMethod>> fittingMethodParameter;
+    public IValueParameter<EnumValue<FittingMethod>> FittingMethodParameter {
+      get { return fittingMethodParameter; }
+    }
+
+    public FittingMethod FittingMethod {
+      get { return fittingMethodParameter.Value.Value; }
+      set { fittingMethodParameter.Value.Value = value; }
+    }
+
+    [Storable]
+    private readonly IValueParameter<EnumValue<ExtremePointCreationMethod>> extremePointCreationMethodParameter;
+    public IValueParameter<EnumValue<ExtremePointCreationMethod>> ExtremePointCreationMethodParameter {
+      get { return extremePointCreationMethodParameter; }
+    }
+
+    public ExtremePointCreationMethod ExtremePointCreationMethod {
+      get { return extremePointCreationMethodParameter.Value.Value; }
+      set { extremePointCreationMethodParameter.Value.Value = value; }
+    }
 
     [StorableConstructor]
@@ -46 +68 @@
     protected ExtremePointPermutationDecoder(ExtremePointPermutationDecoder original, Cloner cloner)
       : base(original, cloner) {
+      fittingMethodParameter = cloner.Clone(original.fittingMethodParameter);
+      //_binPacker = cloner.Clone(original._binPacker);
     }
+    public ExtremePointPermutationDecoder() {
+      Parameters.Add(fittingMethodParameter = 
+            new ValueParameter<EnumValue<FittingMethod>>("Fitting Method", 
+                                                         "The fitting method that the decoder uses.", 
+                                                         new EnumValue<FittingMethod>(FittingMethod.FirstFit)));
 
-    /// <summary>
-    /// Creates an extrem point based permutation decoder
-    /// </summary>
-    /// <param name="binPacker">Contains the packing algorithm for packing the items</param>
-    public ExtremePointPermutationDecoder(BinPacker binPacker) : base() {
-      _binPacker = binPacker;
+      Parameters.Add(extremePointCreationMethodParameter =
+            new ValueParameter<EnumValue<ExtremePointCreationMethod>>("Extreme Point Generation Method",
+                                                         "The Extreme point generation method that the decoder uses.",
+                                                         new EnumValue<ExtremePointCreationMethod>(ExtremePointCreationMethod.PointProjection)));
     }
 
@@ -60 +87 @@
     }
 
+    /*[Storable]
     BinPacker _binPacker;
-
+    */
     /// <summary>
     /// Creates a solution for displaying it on the HEAL gui
@@ -70 +98 @@
     /// <param name="useStackingConstraints"></param>
     /// <returns></returns>
-    public Solution Decode(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
+    public Solution Decode(Permutation permutation, PackingShape binShape, IList<PackingItem> items,bool useStackingConstraints) {
+      var binPacker = BinPackerFactory.CreateBinPacker(FittingMethod);
       Solution solution = new Solution(binShape, useExtremePoints: true, stackingConstraints: useStackingConstraints);
-      foreach (var packedBin in _binPacker.PackItems(permutation, binShape, items, useStackingConstraints)) {
+      foreach (var packedBin in binPacker.PackItems(permutation, binShape, items, ExtremePointCreationMethod, useStackingConstraints)) {
         solution.Bins.Add(packedBin);
       }

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Encoding/PermutationProblem.cs

@@ -50 +50 @@
     public PermutationProblem()
       : base() {
-      Decoder = new ExtremePointPermutationDecoder(new BinPackerFirstFit()); // default decoder
+      Decoder = new ExtremePointPermutationDecoder(); // default decoder
 
       Encoding = new Encodings.PermutationEncoding.PermutationEncoding(EncodedSolutionName, Items.Count, PermutationTypes.Absolute);

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Line3D.cs

@@ -29 +29 @@
       return plane.Intersect(this);
     }
+
+    public Vector3D Intersect(Line3D line) {
+      double r = 0;
+      double s = 0;
+
+      if (Direction.X != 0) {
+        r = (line.Point.X - this.Point.X) / (double)Direction.X;
+      } else if (Direction.Y != 0) {
+        r = (line.Point.Y - this.Point.Y) / (double)Direction.Y;
+      } else if (Direction.Z != 0) {
+        r = (line.Point.Z - this.Point.Z) / (double)Direction.Z;
+      }
+
+      if (line.Direction.X != 0) {
+        s = (this.Point.X - line.Point.X) / (double)line.Direction.X;
+      } else if (line.Direction.Y != 0) {
+        s = (this.Point.Y - line.Point.Y) / (double)line.Direction.Y;
+      } else if (line.Direction.Z != 0) {
+        s = (this.Point.Z - line.Point.Z) / (double)line.Direction.Z;
+      }
+
+      var a = r * this.Direction + this.Point;
+      var b = s * line.Direction + line.Point;
+      var c = a.Equals(b);
+      if (s!=0 && r!=0 && a.Equals(b)) {
+        
+        return a;
+      }
+
+      return null;
+    }
   }
 }

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Vector3D.cs

@@ -6 +6 @@
 
 namespace HeuristicLab.Problems.BinPacking3D.Geometry {
-  internal class Vector3D {
+  public class Vector3D {
 
     public int X { get; set; }
@@ -23 +23 @@
       Z = pos.Z;
     }
+
+    public PackingPosition ToPackingPosition(int assignedBin) {
+      return new PackingPosition(assignedBin, X, Y, Z);
+    }
+
     public static Vector3D AlongX(Vector3D pos, PackingItem item) {
       return new Vector3D(
@@ -86 +91 @@
       return new Vector3D(a * b.X, a * b.Y, a * b.Z);
     }
+
+    public static Vector3D operator *(double a, Vector3D b) {
+      return new Vector3D((int)(a * b.X), (int)(a * b.Y), (int)(a * b.Z));
+    }
+
     public static Vector3D operator *(Vector3D a, int b) {
       return new Vector3D(a.X * b, a.Y * b, a.Z * b);
     }
+
+    public static Vector3D operator *(Vector3D a, double b) {
+      return new Vector3D((int)(b * a.X), (int)(b * a.Y), (int)(b * a.Z));
+    }
+
     public static Vector3D operator +(Vector3D a, Vector3D b) {
       return new Vector3D(a.X + b.X, a.Y + b.Y, a.Z + b.Z);

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

@@ -20 +20 @@
 #endregion
 
+using HeuristicLab.Common;
 using HeuristicLab.Core;
 using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using HeuristicLab.Problems.BinPacking3D;
+using HeuristicLab.Problems.BinPacking3D.ExtremePointCreation;
 using System;
 using System.Collections.Generic;
@@ -31 +33 @@
 
 namespace HeuristicLab.Problems.BinPacking3D.Packer {
-  [Item("BinPacker", "A class for packing bins for the 3D bin-packer problem.")]
-  [StorableClass]
-  public abstract class BinPacker {
+  public abstract class BinPacker : Item {
+
+    /*
+    [Storable]
+    IPositionFinder PositionFinder
     
+    */
+
+    #region Constructors for HEAL
+
+    
+    [StorableConstructor]
+    protected BinPacker(bool deserializing) : base(deserializing) { }
+
+    protected BinPacker(BinPacker original, Cloner cloner) 
+      : base(original, cloner) {
+      //this.PositionFinder = original.PositionFinder;
+    }
+
+    #endregion
+
     public BinPacker() { }
 
@@ -45 +64 @@
     /// <param name="useStackingConstraints">Flag for using stacking constraints</param>
     /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
-    public abstract IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints);
+    public abstract IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, bool useStackingConstraints);
     
     /// <summary>
@@ -54 +73 @@
     /// <param name="packingItem"></param>
     /// <param name="position"></param>
-    protected virtual void PackItem(BinPacking3D packingBin, int itemId, PackingItem packingItem, PackingPosition position, bool useStackingConstraints) {
-
+    protected virtual void PackItem(BinPacking3D packingBin, int itemId, PackingItem packingItem, PackingPosition position, IExtremePointCreator extremePointCreator, bool useStackingConstraints) {
+      if (!CheckItemDimensions(packingBin, packingItem, position)) {
+        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})");
+      }
       packingBin.PackItem(itemId, packingItem, position);
-      packingBin.UpdateResidualSpace(packingItem, position);
-      packingBin.UpdateExtremePoints(packingItem, position, useStackingConstraints);
+      extremePointCreator.UpdateExtremePoints(packingBin, packingItem, position);
+      extremePointCreator.UpdateResidualSpace(packingBin, packingItem, position);
     }
 
@@ -79 +102 @@
       return packingBin.ExtremePoints.Where(x => packingBin.IsPositionFeasible(newItem, x, useStackingConstraints)).FirstOrDefault();
     }
+
+    /// <summary>
+    /// Compares the dimensions of a given item and the current bin. 
+    /// </summary>
+    /// <param name="item"></param>
+    /// <returns>Returns true if the dimensions of an given item are less or equal to the bin.</returns>
+    private bool CheckItemDimensions(BinPacking3D packingBin, PackingItem item, PackingPosition itemPosition) {
+      var width = itemPosition.Rotated ? item.Depth : item.Width;
+      var depth = itemPosition.Rotated ? item.Width : item.Depth;
+      return packingBin.BinShape.Width >= width && packingBin.BinShape.Height >= item.Height && packingBin.BinShape.Depth >= depth;
+    }
   }
 }

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

@@ -20 +20 @@
 #endregion
 
+using HeuristicLab.Common;
 using HeuristicLab.Core;
 using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Problems.BinPacking3D.ExtremePointCreation;
 using System;
 using System.Collections.Generic;
@@ -30 +32 @@
 
 namespace HeuristicLab.Problems.BinPacking3D.Packer {
+  public class BinPackerFirstFit : BinPacker {
+    #region Constructors for HEAL
+    [StorableConstructor]
+    protected BinPackerFirstFit(bool deserializing) : base(deserializing) { }
 
-  [Item("BinPackerFirstFit", "A class for packing bins for the 3D bin-packer problem. It uses a first fit algorithm")]
-  [StorableClass]
-  public class BinPackerFirstFit : BinPacker {
+    protected BinPackerFirstFit(BinPackerFirstFit original, Cloner cloner) 
+      : base(original, cloner) {
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new BinPackerFirstFit(this, cloner);
+    }
+    #endregion
 
     public BinPackerFirstFit() : base() { }    
@@ -41 +52 @@
     /// </summary>
     /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
-    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
+    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epGenerationMethod, bool useStackingConstraints) {
       IList<BinPacking3D> packingList = new List<BinPacking3D>();
       IList<int> remainingIds = new List<int>(sortedItems);
@@ -47 +58 @@
       while (remainingIds.Count > 0) {
         BinPacking3D packingBin = new BinPacking3D(binShape);
-        PackRemainingItems(ref remainingIds, ref packingBin, items, useStackingConstraints, null);
+        PackRemainingItems(ref remainingIds, ref packingBin, items, epGenerationMethod, useStackingConstraints, null);
         packingList.Add(packingBin);
       }
@@ -60 +71 @@
     /// <param name="items">List of packing items. Some of the items will be assigned to the BinPacking3D object</param>
     /// <param name="packingBin">This object will be filled with some of the given items</param>
-    protected void PackRemainingItems(ref IList<int> remainingIds, ref BinPacking3D packingBin, IList<PackingItem> items, bool useStackingConstraints, Dictionary<int, bool> rotationArray) {
-
+    protected void PackRemainingItems(ref IList<int> remainingIds, ref BinPacking3D packingBin, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, bool useStackingConstraints, Dictionary<int, bool> rotationArray) {
+      IExtremePointCreator extremePointCreator = ExtremePointCreatorFactory.CreateExtremePointCreator(epCreationMethod, useStackingConstraints);
       foreach (var itemId in new List<int>(remainingIds)) {
         bool rotated = rotationArray == null ? false : rotationArray[itemId];
@@ -67 +78 @@
         // if a valid packing position could be found, the current item can be added to the given bin
         if (position != null) {
-          PackItem(packingBin, itemId, items[itemId], position, useStackingConstraints);
+          PackItem(packingBin, itemId, items[itemId], position, extremePointCreator, useStackingConstraints);
           remainingIds.Remove(itemId);
         }

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

@@ -20 +20 @@
 #endregion
 
+using HeuristicLab.Common;
 using HeuristicLab.Core;
 using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Problems.BinPacking3D.ExtremePointCreation;
 using System;
 using System.Collections.Generic;
@@ -30 +32 @@
 
 namespace HeuristicLab.Problems.BinPacking3D.Packer {
-  [Item("BinPackerFreeVolumeBestFit", "A class for packing bins for the 3D bin-packer problem. It uses a best fit algortihm depending on the free volume.")]
-  [StorableClass]
   public class BinPackerFreeVolumeBestFit : BinPacker {
+    
+    #region Constructors for HEAL
+    [StorableConstructor]
+    protected BinPackerFreeVolumeBestFit(bool deserializing) : base(deserializing) { }
+
+    protected BinPackerFreeVolumeBestFit(BinPackerFreeVolumeBestFit original, Cloner cloner) 
+      : base(original, cloner) {
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new BinPackerFreeVolumeBestFit(this, cloner);
+    }
+    #endregion
 
     public BinPackerFreeVolumeBestFit() : base() { }
@@ -48 +61 @@
     /// <param name="useStackingConstraints"></param>
     /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
-    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
+    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epGenerationMethod, bool useStackingConstraints) {
       IList<BinPacking3D> packingList = new List<BinPacking3D>();
       IList<int> remainingIds = new List<int>(sortedItems);
-
+      IExtremePointCreator extremePointCreator = ExtremePointCreatorFactory.CreateExtremePointCreator(epGenerationMethod, useStackingConstraints);
       foreach (int remainingId in remainingIds) {
         var sortedBins = packingList.OrderBy(x => x.FreeVolume);
@@ -64 +77 @@
           var bin = packingBin;
           if (positionFound) {
-            PackItem(bin, remainingId, item, position, useStackingConstraints);
+            PackItem(bin, remainingId, item, position, extremePointCreator, useStackingConstraints);
             break;
           }
@@ -74 +87 @@
 
           if (position == null) {
-            throw new InvalidOperationException("Item " + remainingId + " cannot be packed in empty bin.");
+            throw new InvalidOperationException("Item " + remainingId + " cannot be packed into an empty bin.");
           }
 
-          PackItem(packingBin, remainingId, item, position, useStackingConstraints);
+          PackItem(packingBin, remainingId, item, position, extremePointCreator, useStackingConstraints);
           packingList.Add(packingBin);
         }

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

@@ -20 +20 @@
 #endregion
 
+using HeuristicLab.Common;
 using HeuristicLab.Core;
 using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Problems.BinPacking3D.ExtremePointCreation;
 using System;
 using System.Collections.Generic;
@@ -30 +32 @@
 
 namespace HeuristicLab.Problems.BinPacking3D.Packer {
-  [Item("BinPackerResidualSpaceBestFit", "A class for packing bins for the 3D bin-packer problem. It uses a best fit algortihm depending on the residual space.")]
-  [StorableClass]
   public class BinPackerResidualSpaceBestFit : BinPacker {
+
+    #region Constructors for HEAL
+    [StorableConstructor]
+    protected BinPackerResidualSpaceBestFit(bool deserializing) : base(deserializing) { }
+
+    protected BinPackerResidualSpaceBestFit(BinPackerResidualSpaceBestFit original, Cloner cloner) 
+      : base(original, cloner) {
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new BinPackerResidualSpaceBestFit(this, cloner);
+    }
+    #endregion
 
     public BinPackerResidualSpaceBestFit() : base() { }
@@ -42 +55 @@
     /// </summary>
     /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
-    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
+    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epGenerationMethod, bool useStackingConstraints) {
       IList<BinPacking3D> packingList = new List<BinPacking3D>();
       IList<int> remainingIds = new List<int>(sortedItems);
+      IExtremePointCreator extremePointCreator = ExtremePointCreatorFactory.CreateExtremePointCreator(epGenerationMethod, useStackingConstraints);
       bool rotated = false;
 
@@ -56 +70 @@
           if (point.Item1.IsPositionFeasible(item, point.Item2, useStackingConstraints)) {
             var binPacking = point.Item1;
-            PackItem(binPacking, remainingId, item, point.Item2, useStackingConstraints);
+            PackItem(binPacking, remainingId, item, point.Item2, extremePointCreator, useStackingConstraints);
             packed = true;
             break;
@@ -66 +80 @@
           var position = FindPackingPositionForItem(binPacking, item, useStackingConstraints, rotated);
           if (position != null) {
-            PackItem(binPacking, remainingId, item, position, useStackingConstraints);
+            PackItem(binPacking, remainingId, item, position, extremePointCreator, useStackingConstraints);
           } else {
-            throw new InvalidOperationException("Item " + remainingId + " cannot be packed in an empty bin.");
+            throw new InvalidOperationException("Item " + remainingId + " cannot be packed into an empty bin.");
           }
           packingList.Add(binPacking);
         }
       }
-
       return packingList;
     }
@@ -110 +123 @@
           (rs.Item3 - item.Depth));
     }
-
   }
 }

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj

@@ -103 +103 @@
     <Compile Include="2D\ProblemBase.cs" />
     <Compile Include="2D\Solution.cs" />
+    <Compile Include="3D\BinPacking3DException.cs" />
+    <Compile Include="3D\ExtremePointCreation\ExtremePointCreatorFactory.cs" />
+    <Compile Include="3D\ExtremePointCreation\ExtremePointCreator.cs" />
+    <Compile Include="3D\ExtremePointCreation\IExtremePointCreator.cs" />
+    <Compile Include="3D\ExtremePointCreation\LineProjectionBasedEPCreator.cs" />
+    <Compile Include="3D\ExtremePointCreation\PointProjectionBasedEPCreator.cs" />
+    <Compile Include="3D\Geometry\Edge3D.cs" />
     <Compile Include="3D\Packer\BinPacker.cs" />
     <Compile Include="3D\Packer\BinPackerFactory.cs" />
@@ -123 +130 @@
     <Compile Include="3D\Encoding\IDecoder.cs" />
     <Compile Include="3D\Evaluators\IEvaluator.cs" />
-    <Compile Include="3D\IOperator.cs" />
+    <Compile Include="3D\Sorting\IOperator.cs" />
     <Compile Include="3D\Evaluators\MoveEvaluatorBase.cs" />
     <Compile Include="3D\PackingItem.cs" />