Changeset 15488


Ignore:
Timestamp:
11/28/17 16:10:31 (3 years ago)
Author:
rhanghof
Message:

#2817:

  • Added line projection based bin packing
  • Added residual spaces to the view
Location:
branches/2817-BinPackingSpeedup
Files:
12 added
1 deleted
15 edited

Legend:

Unmodified
Added
Removed
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml

    r15307 r15488  
    3333             >
    3434    <Grid Margin="0,0,-64,-57">
    35         <CheckBox Name="showExtremePointsCheckBox" Content="Show extreme points" VerticalAlignment="Top" HorizontalAlignment="Left" Margin="10,6,0,0" Unchecked="showExtremePointsCheckBoxOnUnchecked" Checked="showExtremePointsCheckBoxOnChecked"/>
    36         <Border BorderThickness="1" Background="{DynamicResource {x:Static SystemColors.ControlBrushKey}}" Margin="0,30,0,0">
     35        <StackPanel>
     36            <CheckBox Name="showExtremePointsCheckBox"
     37                      Content="Show extreme points"
     38                      VerticalAlignment="Top"
     39                      HorizontalAlignment="Left"
     40                      Margin="10,6,0,0"
     41                      Unchecked="ShowExtremePointsCheckBoxOnUnchecked"
     42                      Checked="ShowExtremePointsCheckBoxOnChecked"/>
     43            <CheckBox Name="showResidualSpaceCheckBox"
     44                      Content="Show residual spaces"
     45                      VerticalAlignment="Top"
     46                      HorizontalAlignment="Left"
     47                      Margin="10,6,0,0"
     48                      Unchecked="ShowResidualSpacesCheckBoxOnUnchecked"
     49                      Checked="ShowResidualSpacesCheckBoxOnChecked"/>
     50        </StackPanel>
     51        <Border BorderThickness="1" Background="{DynamicResource {x:Static SystemColors.ControlBrushKey}}" Margin="0,52,0,0">
    3752            <Viewport3D Name="viewport3D1" Margin="0,-1,0,0" >
    3853                <Viewport3D.Camera>
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml.cs

    r15307 r15488  
    2727using System.Windows.Media.Media3D;
    2828using HeuristicLab.Problems.BinPacking3D;
     29using HeuristicLab.Collections;
    2930
    3031namespace HeuristicLab.Problems.BinPacking.Views {
     
    4950    private static readonly Color hiddenColor = Color.FromArgb(0x1A, 0xAA, 0xAA, 0xAA);
    5051    private static readonly Color containerColor = Color.FromArgb(0x7F, 0xAA, 0xAA, 0xAA);
     52    private static readonly Color residualSpaceColor = Color.FromArgb(0x7F, 0xAA, 0xAA, 0x00);
    5153
    5254    private Point startPos;
     
    5557    private double startAngleY;
    5658    private int selectedItemKey;
     59    private int selectedExtremePointIndex;
    5760    private bool showExtremePoints;
     61    private bool showResidualSpaces;
    5862
    5963    private BinPacking<BinPacking3D.PackingPosition, PackingShape, PackingItem> packing;
     
    7074    private Dictionary<int, DiffuseMaterial> materials;
    7175
     76    public ObservableDictionary<BinPacking3D.PackingPosition, Tuple<int, int, int>> ResidualSpaces { get; set; }
     77    public ObservableCollection<BinPacking3D.PackingPosition> ExtremePoints { get; set; }
     78
    7279    public Container3DView() {
    7380      InitializeComponent();
    7481      camMain.Position = new Point3D(0.5, 3, 3); // for design time we use a different camera position
    7582      materials = new Dictionary<int, DiffuseMaterial>();
     83      ResidualSpaces = new ObservableDictionary<BinPacking3D.PackingPosition, Tuple<int, int, int>>();
     84      ExtremePoints = new ObservableCollection<BinPacking3D.PackingPosition>();
     85      selectedExtremePointIndex = -1;
    7686      Clear();
    7787    }
     
    8595    }
    8696
     97    /// <summary>
     98    /// Selects another extreme point
     99    /// </summary>
     100    /// <param name="index"></param>
     101    public void SelectExtremePoint(int index) {
     102      selectedExtremePointIndex = index;
     103      UpdateVisualization();
     104    }
     105
    87106    public void SelectItem(int itemKey) {
    88107      // selection of an item should make all other items semi-transparent
     
    90109      UpdateVisualization();
    91110    }
     111
    92112    public void ClearSelection() {
    93113      // remove all transparency
    94114      selectedItemKey = -1;
     115      selectedExtremePointIndex = -1;
    95116      UpdateVisualization();
    96117    }
     
    98119    private void UpdateVisualization() {
    99120      Clear();
    100       if (packing == null) return; // nothing to display
     121      if (packing == null)
     122        return; // nothing to display
    101123
    102124      var modelGroup = (Model3DGroup)MyModel.Content;
     
    108130
    109131        var colorIdx = selectedItem.Value.Material;
    110         while (colorIdx < 0) colorIdx += colors.Length;
     132        while (colorIdx < 0)
     133          colorIdx += colors.Length;
    111134        colorIdx = colorIdx % colors.Length;
    112135        var color = colors[colorIdx];
     
    132155          modelGroup.Children.Add(model);
    133156        }
     157
     158
    134159      } else {
    135160        foreach (var item in packing.Items) {
     
    144169          if (!materials.TryGetValue(item.Value.Material, out material)) {
    145170            var colorIdx = item.Value.Material;
    146             while (colorIdx < 0) colorIdx += colors.Length;
     171            while (colorIdx < 0)
     172              colorIdx += colors.Length;
    147173            colorIdx = colorIdx % colors.Length;
    148174            var color = colors[colorIdx];
     
    156182      }
    157183
    158       if (showExtremePoints) {
    159         // draw extreme-points
    160         var maxMag = (int)Math.Log10(Math.Max(packing.BinShape.Depth, Math.Max(packing.BinShape.Height, packing.BinShape.Width)));
    161         var cubeSize = (int)Math.Max(Math.Pow(10, maxMag - 2), 1);
    162         foreach (var ep in packing.ExtremePoints) {
    163           var epModel = new GeometryModel3D { Geometry = new MeshGeometry3D(), Material = new DiffuseMaterial() { Brush = new SolidColorBrush(Colors.Red) } };
    164           AddSolidCube((MeshGeometry3D)epModel.Geometry, ep.X, ep.Y, ep.Z, cubeSize, cubeSize, cubeSize);
    165           modelGroup.Children.Add(epModel);
    166         }
    167       }
     184
     185      AddExtremePoints(modelGroup);
    168186
    169187      var container = packing.BinShape;
     
    191209    }
    192210
     211    private void AddExtremePoints(Model3DGroup modelGroup) {
     212      if (showExtremePoints) {
     213        // draw extreme-points
     214        var maxMag = (int)Math.Log10(Math.Max(packing.BinShape.Depth, Math.Max(packing.BinShape.Height, packing.BinShape.Width)));
     215        var cubeSize = (int)Math.Max(Math.Pow(10, maxMag - 2), 1);
     216        BinPacking3D.PackingPosition selectedExtremePoint = null;
     217        if (selectedExtremePointIndex < 0) {
     218          foreach (var ep in ExtremePoints) {
     219            AddResidualSpacesForExtremePoint(modelGroup, ep);
     220          }
     221        } else {
     222          selectedExtremePoint = ExtremePoints.ToList()[selectedExtremePointIndex];
     223          AddResidualSpacesForExtremePoint(modelGroup, selectedExtremePoint);
     224        }
     225
     226        foreach (var ep in ExtremePoints) {
     227          Color color;
     228          if (ep.Equals(selectedExtremePoint)) {
     229            color = Colors.Yellow;
     230          } else {
     231            color = Colors.Red;
     232          }
     233          var epModel = new GeometryModel3D { Geometry = new MeshGeometry3D(), Material = new DiffuseMaterial() { Brush = new SolidColorBrush(color) } };
     234          AddSolidCube((MeshGeometry3D)epModel.Geometry, ep.X, ep.Y, ep.Z, cubeSize, cubeSize, cubeSize);
     235          modelGroup.Children.Add(epModel);
     236        }
     237      }
     238    }
     239
     240    private void AddResidualSpacesForExtremePoint(Model3DGroup modelGroup, BinPacking3D.PackingPosition extremePoint) {
     241      if (showResidualSpaces) {
     242        var rs = ResidualSpaces[extremePoint];
     243        var containerModel1 = new GeometryModel3D(new MeshGeometry3D(), new DiffuseMaterial(new SolidColorBrush(residualSpaceColor)));
     244
     245        modelGroup.Children.Add(containerModel1);
     246        AddWireframeCube((MeshGeometry3D)containerModel1.Geometry,
     247          extremePoint.X,
     248          extremePoint.Y,
     249          extremePoint.Z,
     250          rs.Item1,
     251          rs.Item2,
     252          rs.Item3);
     253
     254      }
     255    }
     256
    193257
    194258    private void Clear() {
     
    202266
    203267    private void Container3DView_MouseMove(object sender, MouseEventArgs e) {
    204       if (!mouseDown) return;
     268      if (!mouseDown)
     269        return;
    205270      var pos = e.GetPosition((IInputElement)this);
    206271
     
    235300      Focus(); // for mouse wheel events
    236301    }
    237     private void showExtremePointsCheckBoxOnChecked(object sender, RoutedEventArgs e) {
     302    private void ShowExtremePointsCheckBoxOnChecked(object sender, RoutedEventArgs e) {
    238303      showExtremePoints = true;
    239304      UpdateVisualization();
    240305    }
    241     private void showExtremePointsCheckBoxOnUnchecked(object sender, RoutedEventArgs e) {
     306    private void ShowExtremePointsCheckBoxOnUnchecked(object sender, RoutedEventArgs e) {
    242307      showExtremePoints = false;
     308      UpdateVisualization();
     309    }
     310
     311    private void ShowResidualSpacesCheckBoxOnChecked(object sender, RoutedEventArgs e) {
     312      showResidualSpaces = true;
     313      UpdateVisualization();
     314    }
     315    private void ShowResidualSpacesCheckBoxOnUnchecked(object sender, RoutedEventArgs e) {
     316      showResidualSpaces = false;
    243317      UpdateVisualization();
    244318    }
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/PackingPlan3DView.Designer.cs

    r14162 r15488  
    4949      this.elementHost = new System.Windows.Forms.Integration.ElementHost();
    5050      this.packingPlan3D = new HeuristicLab.Problems.BinPacking.Views.Container3DView();
     51      this.extremePointsSelection = new System.Windows.Forms.ListBox();
    5152      this.SuspendLayout();
    5253      //
     
    5859      this.binSelection.Location = new System.Drawing.Point(3, 3);
    5960      this.binSelection.Name = "binSelection";
    60       this.binSelection.Size = new System.Drawing.Size(54, 290);
     61      this.binSelection.Size = new System.Drawing.Size(54, 264);
    6162      this.binSelection.TabIndex = 4;
    6263      this.binSelection.SelectedIndexChanged += new System.EventHandler(this.binSelection_SelectedIndexChanged);
     
    6970      this.itemSelection.Location = new System.Drawing.Point(58, 3);
    7071      this.itemSelection.Name = "itemSelection";
    71       this.itemSelection.Size = new System.Drawing.Size(55, 290);
     72      this.itemSelection.Size = new System.Drawing.Size(55, 264);
    7273      this.itemSelection.TabIndex = 5;
    7374      this.itemSelection.SelectedIndexChanged += new System.EventHandler(this.itemSelection_SelectedIndexChanged);
     
    7879            | System.Windows.Forms.AnchorStyles.Left)
    7980            | System.Windows.Forms.AnchorStyles.Right)));
    80       this.elementHost.Location = new System.Drawing.Point(119, 3);
     81      this.elementHost.Location = new System.Drawing.Point(198, 3);
    8182      this.elementHost.Name = "elementHost";
    82       this.elementHost.Size = new System.Drawing.Size(229, 290);
     83      this.elementHost.Size = new System.Drawing.Size(273, 264);
    8384      this.elementHost.TabIndex = 6;
    8485      this.elementHost.Text = "elementHost";
    8586      this.elementHost.Child = this.packingPlan3D;
     87      //
     88      // extremePointsSelection
     89      //
     90      this.extremePointsSelection.Anchor = ((System.Windows.Forms.AnchorStyles)(((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Bottom)
     91            | System.Windows.Forms.AnchorStyles.Left)));
     92      this.extremePointsSelection.FormattingEnabled = true;
     93      this.extremePointsSelection.Location = new System.Drawing.Point(115, 3);
     94      this.extremePointsSelection.Name = "extremePointsSelection";
     95      this.extremePointsSelection.Size = new System.Drawing.Size(77, 264);
     96      this.extremePointsSelection.TabIndex = 7;
     97      this.extremePointsSelection.SelectedIndexChanged += new System.EventHandler(this.extremePointsSelection_SelectedIndexChanged);
    8698      //
    8799      // PackingPlan3DView
     
    89101      this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
    90102      this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
     103      this.Controls.Add(this.extremePointsSelection);
    91104      this.Controls.Add(this.elementHost);
    92105      this.Controls.Add(this.itemSelection);
    93106      this.Controls.Add(this.binSelection);
    94107      this.Name = "PackingPlan3DView";
    95       this.Size = new System.Drawing.Size(351, 299);
     108      this.Size = new System.Drawing.Size(489, 278);
    96109      this.ResumeLayout(false);
    97110
     
    104117    private System.Windows.Forms.Integration.ElementHost elementHost;
    105118    private Container3DView packingPlan3D;
     119    private System.Windows.Forms.ListBox extremePointsSelection;
    106120  }
    107121}
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/PackingPlan3DView.cs

    r14167 r15488  
    4747      } else {
    4848        int i = 0;
    49         foreach (var bp in Content.Bins)
     49        foreach (var bp in Content.Bins) {
    5050          binSelection.Items.Add(i++ + " (" + Math.Round(bp.PackingDensity * 100, 2) + "%)");
     51        }
     52
    5153
    5254        binSelection.SelectedIndex = 0;
     
    6365      itemSelection.SelectedIndex = -1;
    6466      itemSelection.Items.Clear();
     67      extremePointsSelection.Items.Clear();
     68      packingPlan3D.ResidualSpaces.Clear();
     69      packingPlan3D.ExtremePoints.Clear();
    6570
    6671      // add items of this container
     
    6974      foreach (var item in packing.Items) {
    7075        itemSelection.Items.Add(item.Key);
     76      }
     77      foreach (var ep in packing.ExtremePoints) {
     78        var rs = ((BinPacking3D.BinPacking3D)packing).ResidualSpace[ep];
     79        extremePointsSelection.Items.Add($"({ep.X}, {ep.Y}, {ep.Z})");
     80        packingPlan3D.ExtremePoints.Add(ep);
     81        packingPlan3D.ResidualSpaces.Add(ep, rs);
    7182      }
    7283
     
    8192        packingPlan3D.ClearSelection();
    8293    }
     94
     95    private void extremePointsSelection_SelectedIndexChanged(object sender, EventArgs e) {
     96      if (extremePointsSelection != null && extremePointsSelection.SelectedIndex >= 0) {
     97        packingPlan3D.SelectExtremePoint(extremePointsSelection.SelectedIndex);
     98      } else {
     99        packingPlan3D.ClearSelection();
     100      }
     101    }
    83102  }
    84103}
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Algorithms/ExtremePointAlgorithm.cs

    r15473 r15488  
    4242  public enum FittingMethod { All, FirstFit, ResidualSpaceBestFit, FreeVolumeBestFit }
    4343
     44  public enum ExtremePointCreationMethod { All, PointProjection, LineProjection }
     45
    4446  [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.")]
    4547  [StorableClass]
     
    8385    public IValueParameter<BoolValue> SortByMaterialParameter {
    8486      get { return sortByMaterialParameter; }
    85     }   
     87    }
     88
     89    [Storable]
     90    private readonly IValueParameter<EnumValue<ExtremePointCreationMethod>> extremePointCreationMethodParameter;
     91    public IValueParameter<EnumValue<ExtremePointCreationMethod>> ExtremePointCreationMethodParameter {
     92      get { return extremePointCreationMethodParameter; }
     93    }
    8694
    8795    [StorableConstructor]
     
    100108        "FittingMethod", "Which method to fit should be used.", new EnumValue<FittingMethod>(FittingMethod.All)));
    101109
     110      Parameters.Add(extremePointCreationMethodParameter = new ValueParameter<EnumValue<ExtremePointCreationMethod>>(
     111        "ExtremePointCreationMethod", "Which method should be used for creatomg extreme points.", new EnumValue<ExtremePointCreationMethod>(ExtremePointCreationMethod.All)));
     112
    102113      Parameters.Add(deltaParameter = new ValueParameter<PercentValue>(
    103114        "Delta", "[1;100]% Clustered sorting methods use a delta parameter to determine the clusters.", new PercentValue(.1)));
     
    124135      var items = Problem.Items;
    125136      var bin = Problem.BinShape;
     137
    126138      var sorting = new[] { SortingMethodParameter.Value.Value };
    127139      if (sorting[0] == SortingMethod.All) {
    128140        sorting = Enum.GetValues(typeof(SortingMethod)).Cast<SortingMethod>().Where(x => x != SortingMethod.All).ToArray();
    129141      }
     142
    130143      var fitting = new[] { fittingMethodParameter.Value.Value };
    131144      if (fitting[0] == FittingMethod.All) {
     
    133146      }
    134147
     148      var extremePointCreation = new[] { ExtremePointCreationMethodParameter.Value.Value };
     149      if (extremePointCreation[0] == ExtremePointCreationMethod.All) {
     150        extremePointCreation = Enum.GetValues(typeof(ExtremePointCreationMethod))
     151                                     .Cast<ExtremePointCreationMethod>()
     152                                     .Where(x => x != ExtremePointCreationMethod.All)
     153                                     .ToArray();
     154      }
     155
    135156      //
    136       var result = GetBest(bin, items, sorting, fitting, token);
     157      var result = GetBest(bin, items, sorting, fitting, extremePointCreation, token);
    137158      if (result == null) {
    138159        throw new InvalidOperationException("No result obtained!");
     
    162183          new EnumValue<FittingMethod>(result.Item4.Value)));
    163184      }
     185
     186      if (result.Item5.HasValue && extremePointCreation.Length > 1) {
     187        Results.Add(new Result("Best extreme point creation method",
     188          "The extreme point creation method that found the best solution",
     189          new EnumValue<ExtremePointCreationMethod>(result.Item5.Value)));
     190      }
    164191    }
    165192
     
    173200    /// <param name="token"></param>
    174201    /// <returns></returns>
    175     private Tuple<Solution, double, SortingMethod?, FittingMethod?> GetBest(PackingShape bin, IList<PackingItem> items, SortingMethod[] sortings, FittingMethod[] fittings, CancellationToken token) {
     202    private Tuple<Solution, double, SortingMethod?, FittingMethod?, ExtremePointCreationMethod?>
     203          GetBest(PackingShape bin,
     204                  IList<PackingItem> items,
     205                  SortingMethod[] sortings,
     206                  FittingMethod[] fittings,
     207                  ExtremePointCreationMethod[] ePGeneration,
     208                  CancellationToken token) {
    176209      SortingMethod? bestSorting = null;
    177210      FittingMethod? bestFitting = null;
     211      ExtremePointCreationMethod? bestEPCreation = null;
    178212      var best = double.NaN;
    179213      Solution bestSolution = null;
    180214      foreach (var fit in fittings) {
    181215        foreach (var sort in sortings) {
    182           IDecoder<Permutation> decoder = new ExtremePointPermutationDecoder(BinPackerFactory.CreateBinPacker(fit));
    183           Permutation sortedItems;
     216          foreach (var epCreation in ePGeneration) {
     217            IDecoder<Permutation> decoder = new ExtremePointPermutationDecoder() {
     218              FittingMethod = fit,
     219              ExtremePointCreationMethod = epCreation
     220            };
     221            Permutation sortedItems;
    184222                   
    185           if (SortByMaterialParameter.Value.Value) {
    186             sortedItems = SortItemsByMaterialAndSortingMethod(bin, items, sort, DeltaParameter.Value.Value);
    187           } else {
    188             sortedItems = SortItemsBySortingMethod(bin, items, sort, DeltaParameter.Value.Value);
    189           }
     223            if (SortByMaterialParameter.Value.Value) {
     224              sortedItems = SortItemsByMaterialAndSortingMethod(bin, items, sort, DeltaParameter.Value.Value);
     225            } else {
     226              sortedItems = SortItemsBySortingMethod(bin, items, sort, DeltaParameter.Value.Value);
     227            }
     228
     229            var result = Optimize(new OptimaizationParamters() {
     230              SortedItems = sortedItems,
     231              Bin = bin,
     232              Items = items,
     233              StackingConstraints = Problem.UseStackingConstraints,
     234              Decoder = decoder,
     235              Evaluator = Problem.SolutionEvaluator,
     236              ExtremePointGeneration = epCreation
     237            });
    190238         
    191           var result = Optimize(sortedItems, bin, items, Problem.UseStackingConstraints, decoder, Problem.SolutionEvaluator);
    192          
    193           if (double.IsNaN(result.Item2) || double.IsInfinity(result.Item2)) {
    194             continue;
    195           }
    196 
    197           if (double.IsNaN(best) || Problem.Maximization && result.Item2 > best || !Problem.Maximization && result.Item2 < best) {
    198             bestSolution = result.Item1;
    199             best = result.Item2;
    200             bestSorting = sort;
    201             bestFitting = fit;
    202           }
    203           if (token.IsCancellationRequested) {
    204             return Tuple.Create(bestSolution, best, bestSorting, bestFitting);
     239            if (double.IsNaN(result.Item2) || double.IsInfinity(result.Item2)) {
     240              continue;
     241            }
     242
     243            if (double.IsNaN(best) || Problem.Maximization && result.Item2 > best || !Problem.Maximization && result.Item2 < best) {
     244              bestSolution = result.Item1;
     245              best = result.Item2;
     246              bestSorting = sort;
     247              bestFitting = fit;
     248              bestEPCreation = epCreation;
     249            }
     250            if (token.IsCancellationRequested) {
     251              return Tuple.Create(bestSolution, best, bestSorting, bestFitting, bestEPCreation);
     252            }
    205253          }
    206254        }
     
    209257        return null;
    210258      }
    211       return Tuple.Create(bestSolution, best, bestSorting, bestFitting);
     259      return Tuple.Create(bestSolution, best, bestSorting, bestFitting, bestEPCreation);
    212260    }
    213261
     
    215263    /// Returns a tuple with the solution and the packing ratio depending on the given parameters
    216264    /// </summary>
    217     /// <param name="sortedItems"></param>
    218     /// <param name="bin"></param>
    219     /// <param name="items"></param>
    220     /// <param name="stackingConstraints"></param>
    221     /// <param name="decoder"></param>
    222     /// <param name="evaluator"></param>
     265    /// <param name="parameters"></param>
    223266    /// <returns></returns>
    224     private static Tuple<Solution, double> Optimize(Permutation sortedItems, PackingShape bin, IList<PackingItem> items, bool stackingConstraints, IDecoder<Permutation> decoder, IEvaluator evaluator) {
     267    private static Tuple<Solution, double> Optimize(OptimaizationParamters parameters) {
    225268     
    226       var sol = decoder.Decode(sortedItems, bin, items, stackingConstraints);
    227       var fit = evaluator.Evaluate(sol);
     269      var sol = parameters.Decoder.Decode(parameters.SortedItems, parameters.Bin, parameters.Items, parameters.StackingConstraints);
     270      var fit = parameters.Evaluator.Evaluate(sol);
    228271
    229272      return Tuple.Create(sol, fit);
     273    }
     274
     275    private class OptimaizationParamters {
     276      public Permutation SortedItems { get; set; }
     277      public PackingShape Bin { get; set; }
     278      public IList<PackingItem> Items { get; set; }
     279      public bool StackingConstraints { get; set; }
     280      public IDecoder<Permutation> Decoder { get; set; }
     281      public IEvaluator Evaluator { get; set; }
     282      public ExtremePointCreationMethod ExtremePointGeneration { get; set; }
    230283    }
    231284   
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs

    r15473 r15488  
    2828using HeuristicLab.Problems.BinPacking;
    2929using HeuristicLab.Problems.BinPacking3D.Geometry;
     30using HeuristicLab.Collections;
    3031
    3132namespace HeuristicLab.Problems.BinPacking3D {
     
    3536
    3637    [Storable]
    37     public Dictionary<PackingPosition, Tuple<int, int, int>> ResidualSpace { get; protected set; }
     38    public Dictionary<PackingPosition, Tuple<int, int, int>> ResidualSpace { get; set; }
     39
     40
     41
    3842
    3943    public BinPacking3D(PackingShape binShape)
    4044      : base(binShape) {
    4145      ResidualSpace = new Dictionary<PackingPosition, Tuple<int, int, int>>();
    42       AddExtremePoint(binShape.Origin);
     46     
     47      ExtremePoints.Add(binShape.Origin);
     48      ResidualSpace.Add(binShape.Origin, new Tuple<int, int, int>(BinShape.Width, BinShape.Height, BinShape.Depth));
     49
     50//      AddExtremePoint(binShape.Origin);
    4351    }
    4452    [StorableConstructor]
     
    6371      #endregion
    6472    }
     73
     74
     75
    6576
    6677    /// <summary>
     
    7788    }
    7889
     90    /*
    7991    /// <summary>
    8092    /// Updates the extreme points of the bin
     
    89101        UpdateExtremePointsWithoutStackingConstriants(item, position);
    90102      }
    91     }
    92 
     103    }*/
     104
     105
     106      /*
    93107    /// <summary>
    94108    /// Updates the extreme points of the bin.
     
    98112    /// <param name="position"></param>
    99113    private void UpdateExtremePointsWithStackingConstriants(PackingItem newItem, PackingPosition position) {
    100 
    101       //UpdateExtremePointsWithoutStackingConstriants(newItem, position);
    102       //return;
    103 
    104114      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
    105115      int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
     
    110120      AddExtremePoint(ep2);
    111121      AddExtremePoint(ep3);
    112     }
    113 
    114     private Tuple<int, int, int> CalculateResidualSpace(Vector3D pos) {
    115       var itemPos = Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] });
    116       Vector3D limit = new Vector3D() { X = BinShape.Width, Y = BinShape.Height, Z = BinShape.Depth };
    117       if (pos.X < limit.X && pos.Y < limit.Y && pos.Z < limit.Z) {
    118         var rightLimit = ProjectRight(pos);
    119         var upLimit = ProjectUp(pos);
    120         var forwardLimit = ProjectForward(pos);
    121         if (rightLimit.X > 0) {
    122           limit.X = rightLimit.X;
    123         }
    124         if (upLimit.Y > 0) {
    125           limit.Y = upLimit.Y;
    126         }
    127         if (forwardLimit.Z > 0) {
    128           limit.Z = forwardLimit.Z;
    129         }
    130       }
    131 
    132       if (limit.X - pos.X <= 0 || limit.Y - pos.Y <= 0 || limit.Z - pos.Z <= 0) {
    133         return Tuple.Create(0, 0, 0);
    134       }
    135       return Tuple.Create(limit.X - pos.X, limit.Y - pos.Y, limit.Z - pos.Z);
    136     }
    137 
    138 
    139     private Vector3D CreateRs(PackingPosition position) {
    140       return new Vector3D() { X = position.X, Y = position.Y, Z = position.Z };
    141     }
    142 
    143     private void UpdateExtremePointsWithoutStackingConstriants(PackingItem item, PackingPosition position) {
    144       GenerateNewExtremePointsForNewItem(item, position);
    145 
    146       // if an item is fit in below, before, or left of another its extreme points have to be regenerated
    147       foreach (var above in GetItemsAbove(position)) {
    148         GenerateNewExtremePointsForNewItem(above.Item2, above.Item1);
    149       }
    150       foreach (var front in GetItemsInfront(position)) {
    151         GenerateNewExtremePointsForNewItem(front.Item2, front.Item1);
    152       }
    153       foreach (var right in GetItemsOnRight(position)) {
    154         GenerateNewExtremePointsForNewItem(right.Item2, right.Item1);
    155       }
    156     }
    157 
    158 
     122    }*/
     123
     124     
     125
     126    #region Position feasability
    159127
    160128    /// <summary>
    161129    /// In this case feasability is defined as following:
    162     /// 1. the item fits into the bin-borders;
    163     /// 2. the point is supported by something;
    164     /// 3. the item does not collide with another already packed item
    165     ///
    166     /// Unfortunatelly this method does not support item rotation
     130    /// 1. the point is supported by something;
     131    /// 2. the item does not collide with another already packed item
    167132    /// </summary>
    168133    /// <param name="item"></param>
     
    171136    /// <returns></returns>
    172137    public override bool IsPositionFeasible(PackingItem item, PackingPosition position, bool stackingConstraints) {
    173       var b1 = CheckItemDimensions(item);
     138      //var b1 = CheckItemDimensions(item, position);
    174139      var b2 = ItemCanBePlaced(item, position);
    175140      var b3 = CheckStackingConstraints(item, position, stackingConstraints);
    176141
    177       return b1 && b2 && b3;
    178     }
    179 
    180     /// <summary>
    181     /// Compares the dimensions of a given item and the current bin.
    182     /// </summary>
    183     /// <param name="item"></param>
    184     /// <returns>Returns true if the dimensions of an given item are less or equal to the bin.</returns>
    185     private bool CheckItemDimensions(PackingItem item) {
    186       return BinShape.Width >= item.Width && BinShape.Height >= item.Height && BinShape.Depth >= item.Depth;
     142      return b2 && b3;
    187143    }
    188144
     
    194150    /// <returns></returns>
    195151    private bool ItemCanBePlaced(PackingItem givenItem, PackingPosition givenItemPosition) {
     152      var width = givenItemPosition.Rotated ? givenItem.Depth : givenItem.Width;
     153      var depth = givenItemPosition.Rotated ? givenItem.Width : givenItem.Depth;
    196154      // Check if the boundings of the bin would injured
    197       if (givenItemPosition.X + givenItem.Width > BinShape.Width ||
     155      if (givenItemPosition.X + width > BinShape.Width ||
    198156          givenItemPosition.Y + givenItem.Height > BinShape.Height ||
    199           givenItemPosition.Z + givenItem.Depth > BinShape.Depth) {
     157          givenItemPosition.Z + depth > BinShape.Depth) {
    200158        return false;
    201159      }
     
    242200      return IsStaticStable(item, position) && IsWeightSupported(item, position);
    243201    }
    244 
    245202
    246203    /// <summary>
     
    298255      p4 = itemsP4.Where(x => position.X < x.Item1.X + x.Item2.Width && position.Z + item.Depth > x.Item1.Z).Any();
    299256    }
    300 
    301257
    302258    /// <summary>
     
    337293    }
    338294
    339 
    340295    /// <summary>
    341296    /// Checks if a given the weight of an given item is supportet by the items below.
     
    360315        itemsP4.Where(x => x.Item2.SupportsStacking(item)).Any();
    361316    }
     317
     318    #endregion
     319
     320    protected override void GenerateNewExtremePointsForNewItem(PackingItem newItem, PackingPosition position) {
     321      throw new NotImplementedException();
     322    }
     323
     324    #region Get items
    362325   
    363 
    364     /// <summary>
    365     /// Generates new extreme points for a given item and its position.
    366     /// It also recalcualtes the residual space and removes the extreme points which are not needed any more.
    367     /// </summary>
    368     /// <param name="newItem"></param>
    369     /// <param name="position"></param>
    370     protected override void GenerateNewExtremePointsForNewItem(PackingItem newItem, PackingPosition position) {
    371       int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
    372       int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
    373 
    374       var itemPlacement = Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] }).ToList();
    375       // Find ExtremePoints beginning from sourcepointX
    376       var sourcePoint = new Vector3D() { X = position.X + newWidth, Y = position.Y, Z = position.Z };
    377       if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) {
    378         // Projecting onto the XZ-plane
    379         var below = ProjectDown(sourcePoint);
    380         var residualSpace = CalculateResidualSpace(below);
    381         if (IsNonZero(residualSpace)
    382           && !IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) {
    383           // add only if the projected point's residual space is not a sub-space
    384           // of another extreme point's residual space
    385           var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z);
    386           AddExtremePoint(belowPoint);
    387         }
    388         // Projecting onto the XY-plane
    389         var back = ProjectBackward(sourcePoint);
    390         residualSpace = CalculateResidualSpace(back);
    391         if (IsNonZero(residualSpace)
    392           && !IsWithinResidualSpaceOfAnotherExtremePoint(back, residualSpace)) {
    393           // add only if the projected point's residual space is not a sub-space
    394           // of another extreme point's residual space
    395           var backPoint = new PackingPosition(position.AssignedBin, back.X, back.Y, back.Z);
    396           AddExtremePoint(backPoint);
    397         }
    398       }
    399 
    400       //Find ExtremePoints beginning from sourcepointY
    401       sourcePoint = new Vector3D(position.X, position.Y + newItem.Height, position.Z);
    402       if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) {
    403         // Projecting onto the YZ-plane
    404         var left = ProjectLeft(sourcePoint);
    405         var residualSpace = CalculateResidualSpace(left);
    406         if (IsNonZero(residualSpace)
    407           && !IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) {
    408           // add only if the projected point's residual space is not a sub-space
    409           // of another extreme point's residual space
    410           var leftPoint = new PackingPosition(position.AssignedBin, left.X, left.Y, left.Z);
    411           AddExtremePoint(leftPoint);
    412         }
    413         // Projecting onto the XY-plane
    414         var back = ProjectBackward(sourcePoint);
    415         residualSpace = CalculateResidualSpace(back);
    416         if (IsNonZero(residualSpace)
    417           && !IsWithinResidualSpaceOfAnotherExtremePoint(back, residualSpace)) {
    418           // add only if the projected point's residual space is not a sub-space
    419           // of another extreme point's residual space
    420           var backPoint = new PackingPosition(position.AssignedBin, back.X, back.Y, back.Z);
    421           AddExtremePoint(backPoint);
    422         }
    423       }
    424 
    425       //Find ExtremePoints beginning from sourcepointZ
    426       sourcePoint = new Vector3D(position.X, position.Y, position.Z + newDepth);
    427       if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) {
    428         // Projecting onto the XZ-plane
    429         var below = ProjectDown(sourcePoint);
    430         var residualSpace = CalculateResidualSpace(below);
    431         if (IsNonZero(residualSpace)
    432           && !IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) {
    433           // add only if the projected point's residual space is not a sub-space
    434           // of another extreme point's residual space
    435           var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z);
    436           AddExtremePoint(belowPoint);
    437         }
    438         // Projecting onto the YZ-plane
    439         var left = ProjectLeft(sourcePoint);
    440         residualSpace = CalculateResidualSpace(left);
    441         if (IsNonZero(residualSpace)
    442           && !IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) {
    443           // add only if the projected point's residual space is not a sub-space
    444           // of another extreme point's residual space
    445           var leftPoint = new PackingPosition(position.AssignedBin, left.X, left.Y, left.Z);
    446           AddExtremePoint(leftPoint);
    447         }
    448       }
    449     }
    450 
    451     /// <summary>
    452     /// Returns true if all values of a given tuple are not zero
    453     /// </summary>
    454     /// <param name="rs">Tuple with three integer values which represents a residual space</param>
    455     /// <returns></returns>
    456     private bool IsNonZero(Tuple<int, int, int> rs) {
    457       return rs.Item1 > 0 && rs.Item2 > 0 && rs.Item3 > 0;
    458     }
    459 
    460     /// <summary>
    461     ///
    462     /// </summary>
    463     /// <param name="pos"></param>
    464     /// <param name="residualSpace"></param>
    465     /// <returns></returns>
    466     private bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> residualSpace) {
    467       var eps = ExtremePoints.Where(x => !pos.Equals(x) && pos.IsInside(x, ResidualSpace[x]));
    468       return eps.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, residualSpace, x, ResidualSpace[x]));
    469     }
    470     private bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> rsPos, PackingPosition ep, Tuple<int, int, int> rsEp) {
    471       return rsEp.Item1 >= pos.X - ep.X + rsPos.Item1
    472           && rsEp.Item2 >= pos.Y - ep.Y + rsPos.Item2
    473           && rsEp.Item3 >= pos.Z - ep.Z + rsPos.Item3;
    474     }
    475 
    476     /// <summary>
    477     /// Adds an extrem point to the extreme point collection of the bin packing.
    478     /// </summary>
    479     /// <param name="pos">Position of the new extreme point</param>
    480     /// <returns>Retruns true if the extreme point could be added</returns>
    481     private bool AddExtremePoint(PackingPosition pos) {
    482       if (ExtremePoints.Add(pos)) {
    483         var rs = CalculateResidualSpace(new Vector3D(pos));
    484         ResidualSpace.Add(pos, rs);
    485         // Check if the existing extreme points are shadowed by the new point
    486         // This is, their residual space fit entirely into the residual space of the new point
    487         foreach (var ep in ExtremePoints.Where(x => x != pos && new Vector3D(x).IsInside(pos, rs)).ToList()) {
    488           if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), ResidualSpace[ep], pos, rs)) {
    489             ExtremePoints.Remove(ep);
    490             ResidualSpace.Remove(ep);
    491           }
    492         }
    493         return true;
    494       }
    495       return false;
    496     }
    497 
    498     #region Projections
    499 
    500     private Vector3D ProjectBackward(Vector3D pos) {
    501       var line = new Line3D(pos, new Vector3D(0, 0, -1));
    502       return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })
    503                   .Select(x => new Plane3D(x.Position, x.Item, Side.Front))
    504                   .Concat(new[] { new Plane3D(BinShape, Side.Back) })
    505                   .Select(x => x.Intersect(line))
    506                   .Where(x => x != null && x.Z <= pos.Z)
    507                   .MaxItems(x => x.Z).First();
    508     }
    509 
    510     private Vector3D ProjectLeft(Vector3D pos) {
    511       var line = new Line3D(pos, new Vector3D(-1, 0, 0));
    512       return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })
    513                   .Select(x => new Plane3D(x.Position, x.Item, Side.Right))
    514                   .Concat(new[] { new Plane3D(BinShape, Side.Left) })
    515                   .Select(x => x.Intersect(line))
    516                   .Where(x => x != null && x.X <= pos.X)
    517                   .MaxItems(x => x.X).First();
    518     }
    519 
    520     private Vector3D ProjectDown(Vector3D pos) {
    521       var line = new Line3D(pos, new Vector3D(0, -1, 0));
    522       return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })
    523                   .Select(x => new Plane3D(x.Position, x.Item, Side.Top))
    524                   .Concat(new[] { new Plane3D(BinShape, Side.Bottom) })
    525                   .Select(x => x.Intersect(line))
    526                   .Where(x => x != null && x.Y <= pos.Y)
    527                   .MaxItems(x => x.Y).First();
    528     }
    529 
    530     private Vector3D ProjectForward(Vector3D pos) {
    531       var line = new Line3D(pos, new Vector3D(0, 0, 1));
    532       return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })
    533                   .Select(x => new Plane3D(x.Position, x.Item, Side.Back))
    534                   .Concat(new[] { new Plane3D(BinShape, Side.Front) })
    535                   .Select(x => x.Intersect(line))
    536                   .Where(x => x != null && x.Z >= pos.Z)
    537                   .MinItems(x => x.Z).First();
    538     }
    539 
    540     private Vector3D ProjectRight(Vector3D pos) {
    541       var line = new Line3D(pos, new Vector3D(1, 0, 0));
    542       return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })
    543                   .Select(x => new Plane3D(x.Position, x.Item, Side.Left))
    544                   .Concat(new[] { new Plane3D(BinShape, Side.Right) })
    545                   .Select(x => x.Intersect(line))
    546                   .Where(x => x != null && x.X >= pos.X)
    547                   .MinItems(x => x.X).First();
    548     }
    549 
    550     private Vector3D ProjectUp(Vector3D pos) {
    551       var line = new Line3D(pos, new Vector3D(0, 1, 0));
    552       return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })
    553                   .Select(x => new Plane3D(x.Position, x.Item, Side.Bottom))
    554                   .Concat(new[] { new Plane3D(BinShape, Side.Top) })
    555                   .Select(x => x.Intersect(line))
    556                   .Where(x => x != null && x.Y >= pos.Y)
    557                   .MinItems(x => x.Y).First();
    558     }
    559     #endregion
    560 
    561     #region Get items
    562 
    563     private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsAbove(PackingPosition pos) {
    564       var line = new Line3D(pos, new Vector3D(0, 1, 0));
    565       return Items.Select(x => new {
    566         Item = x.Value,
    567         Position = Positions[x.Key],
    568         Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Bottom))
    569       }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
    570         .Select(x => Tuple.Create(x.Position, x.Item));
    571     }
    572 
    573     private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsInfront(PackingPosition pos) {
    574       var line = new Line3D(pos, new Vector3D(0, 0, 1));
    575       return Items.Select(x => new {
    576         Item = x.Value,
    577         Position = Positions[x.Key],
    578         Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Back))
    579       }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
    580         .Select(x => Tuple.Create(x.Position, x.Item));
    581     }
    582 
    583     private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnRight(PackingPosition pos) {
    584       var line = new Line3D(pos, new Vector3D(1, 0, 0));
    585       return Items.Select(x => new {
    586         Item = x.Value,
    587         Position = Positions[x.Key],
    588         Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Left))
    589       }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
    590         .Select(x => Tuple.Create(x.Position, x.Item));
    591     }
    592 
    593326    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(PackingPosition pos) {
    594327      var line = new Line3D(pos, new Vector3D(0, 1, 0));
     
    601334    }
    602335
    603     private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBehind(PackingPosition pos) {
    604       var line = new Line3D(pos, new Vector3D(0, 0, 1));
    605       return Items.Select(x => new {
    606         Item = x.Value,
    607         Position = Positions[x.Key],
    608         Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Front))
    609       }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
    610         .Select(x => Tuple.Create(x.Position, x.Item));
    611     }
    612 
    613     private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnLeft(PackingPosition pos) {
    614       var line = new Line3D(pos, new Vector3D(1, 0, 0));
    615       return Items.Select(x => new {
    616         Item = x.Value,
    617         Position = Positions[x.Key],
    618         Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Right))
    619       }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
    620         .Select(x => Tuple.Create(x.Position, x.Item));
    621     }
    622 
    623336    #endregion
    624 
    625 
    626 
    627     /// <summary>
    628     /// Updates the resiual space for a packing item.
    629     /// </summary>
    630     /// <param name="item"></param>
    631     /// <param name="pos"></param>
    632     public void UpdateResidualSpace(PackingItem item, PackingPosition pos) {
    633       foreach (var ep in ExtremePoints.ToList()) {
    634         var rs = ResidualSpace[ep];
    635         var depth = pos.Rotated ? item.Width : item.Depth;
    636         var width = pos.Rotated ? item.Depth : item.Width;
    637         var changed = false;
    638         if (ep.Z >= pos.Z && ep.Z < pos.Z + depth) {
    639           if (ep.X <= pos.X && ep.Y >= pos.Y && ep.Y < pos.Y + item.Height) {
    640             var diff = pos.X - ep.X;
    641             var newRSX = Math.Min(rs.Item1, diff);
    642             rs = Tuple.Create(newRSX, rs.Item2, rs.Item3);
    643             changed = true;
    644           }
    645           if (ep.Y <= pos.Y && ep.X >= pos.X && ep.X < pos.X + width) {
    646             var diff = pos.Y - ep.Y;
    647             var newRSY = Math.Min(rs.Item2, diff);
    648             rs = Tuple.Create(rs.Item1, newRSY, rs.Item3);
    649             changed = true;
    650           }
    651         }
    652 
    653         if (ep.Z <= pos.Z &&
    654             ep.Y >= pos.Y && ep.Y < pos.Y + item.Height &&
    655             ep.X >= pos.X && ep.X < pos.X + width) {
    656           var diff = pos.Z - ep.Z;
    657           var newRSZ = Math.Min(rs.Item3, diff);
    658           rs = Tuple.Create(rs.Item1, rs.Item2, newRSZ);
    659           changed = true;
    660         }
    661 
    662         if (changed) {
    663           if (IsNonZero(rs) && !IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), rs)) {
    664             ResidualSpace[ep] = rs;
    665           } else {
    666             ExtremePoints.Remove(ep);
    667             ResidualSpace.Remove(ep);
    668           }
    669         }
    670       }
    671       return;
    672     }
    673337  }
    674338}
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Encoding/ExtremePointPermutationDecoder.cs

    r15473 r15488  
    3030using HeuristicLab.Common;
    3131using HeuristicLab.Problems.BinPacking3D.Packer;
     32using HeuristicLab.Parameters;
     33using HeuristicLab.Data;
    3234
    3335namespace HeuristicLab.Problems.BinPacking3D.Encoding {
     
    3840  [Item("Extreme-point Permutation Decoder (3d) Base", "Base class for 3d decoders")]
    3941  [StorableClass]
    40   public class ExtremePointPermutationDecoder : Item, IDecoder<Permutation>
    41     //where TBinPacker : BinPacker, new ()
    42     {
     42  public class ExtremePointPermutationDecoder : ParameterizedNamedItem, IDecoder<Permutation> {
     43
     44    [Storable]
     45    private IValueParameter<EnumValue<FittingMethod>> fittingMethodParameter;
     46    public IValueParameter<EnumValue<FittingMethod>> FittingMethodParameter {
     47      get { return fittingMethodParameter; }
     48    }
     49
     50    public FittingMethod FittingMethod {
     51      get { return fittingMethodParameter.Value.Value; }
     52      set { fittingMethodParameter.Value.Value = value; }
     53    }
     54
     55    [Storable]
     56    private readonly IValueParameter<EnumValue<ExtremePointCreationMethod>> extremePointCreationMethodParameter;
     57    public IValueParameter<EnumValue<ExtremePointCreationMethod>> ExtremePointCreationMethodParameter {
     58      get { return extremePointCreationMethodParameter; }
     59    }
     60
     61    public ExtremePointCreationMethod ExtremePointCreationMethod {
     62      get { return extremePointCreationMethodParameter.Value.Value; }
     63      set { extremePointCreationMethodParameter.Value.Value = value; }
     64    }
    4365
    4466    [StorableConstructor]
     
    4668    protected ExtremePointPermutationDecoder(ExtremePointPermutationDecoder original, Cloner cloner)
    4769      : base(original, cloner) {
     70      fittingMethodParameter = cloner.Clone(original.fittingMethodParameter);
     71      //_binPacker = cloner.Clone(original._binPacker);
    4872    }
     73    public ExtremePointPermutationDecoder() {
     74      Parameters.Add(fittingMethodParameter =
     75            new ValueParameter<EnumValue<FittingMethod>>("Fitting Method",
     76                                                         "The fitting method that the decoder uses.",
     77                                                         new EnumValue<FittingMethod>(FittingMethod.FirstFit)));
    4978
    50     /// <summary>
    51     /// Creates an extrem point based permutation decoder
    52     /// </summary>
    53     /// <param name="binPacker">Contains the packing algorithm for packing the items</param>
    54     public ExtremePointPermutationDecoder(BinPacker binPacker) : base() {
    55       _binPacker = binPacker;
     79      Parameters.Add(extremePointCreationMethodParameter =
     80            new ValueParameter<EnumValue<ExtremePointCreationMethod>>("Extreme Point Generation Method",
     81                                                         "The Extreme point generation method that the decoder uses.",
     82                                                         new EnumValue<ExtremePointCreationMethod>(ExtremePointCreationMethod.PointProjection)));
    5683    }
    5784
     
    6087    }
    6188
     89    /*[Storable]
    6290    BinPacker _binPacker;
    63 
     91    */
    6492    /// <summary>
    6593    /// Creates a solution for displaying it on the HEAL gui
     
    7098    /// <param name="useStackingConstraints"></param>
    7199    /// <returns></returns>
    72     public Solution Decode(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
     100    public Solution Decode(Permutation permutation, PackingShape binShape, IList<PackingItem> items,bool useStackingConstraints) {
     101      var binPacker = BinPackerFactory.CreateBinPacker(FittingMethod);
    73102      Solution solution = new Solution(binShape, useExtremePoints: true, stackingConstraints: useStackingConstraints);
    74       foreach (var packedBin in _binPacker.PackItems(permutation, binShape, items, useStackingConstraints)) {
     103      foreach (var packedBin in binPacker.PackItems(permutation, binShape, items, ExtremePointCreationMethod, useStackingConstraints)) {
    75104        solution.Bins.Add(packedBin);
    76105      }
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Encoding/PermutationProblem.cs

    r15473 r15488  
    5050    public PermutationProblem()
    5151      : base() {
    52       Decoder = new ExtremePointPermutationDecoder(new BinPackerFirstFit()); // default decoder
     52      Decoder = new ExtremePointPermutationDecoder(); // default decoder
    5353
    5454      Encoding = new Encodings.PermutationEncoding.PermutationEncoding(EncodedSolutionName, Items.Count, PermutationTypes.Absolute);
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Line3D.cs

    r15454 r15488  
    2929      return plane.Intersect(this);
    3030    }
     31
     32    public Vector3D Intersect(Line3D line) {
     33      double r = 0;
     34      double s = 0;
     35
     36      if (Direction.X != 0) {
     37        r = (line.Point.X - this.Point.X) / (double)Direction.X;
     38      } else if (Direction.Y != 0) {
     39        r = (line.Point.Y - this.Point.Y) / (double)Direction.Y;
     40      } else if (Direction.Z != 0) {
     41        r = (line.Point.Z - this.Point.Z) / (double)Direction.Z;
     42      }
     43
     44      if (line.Direction.X != 0) {
     45        s = (this.Point.X - line.Point.X) / (double)line.Direction.X;
     46      } else if (line.Direction.Y != 0) {
     47        s = (this.Point.Y - line.Point.Y) / (double)line.Direction.Y;
     48      } else if (line.Direction.Z != 0) {
     49        s = (this.Point.Z - line.Point.Z) / (double)line.Direction.Z;
     50      }
     51
     52      var a = r * this.Direction + this.Point;
     53      var b = s * line.Direction + line.Point;
     54      var c = a.Equals(b);
     55      if (s!=0 && r!=0 && a.Equals(b)) {
     56       
     57        return a;
     58      }
     59
     60      return null;
     61    }
    3162  }
    3263}
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Vector3D.cs

    r15454 r15488  
    66
    77namespace HeuristicLab.Problems.BinPacking3D.Geometry {
    8   internal class Vector3D {
     8  public class Vector3D {
    99
    1010    public int X { get; set; }
     
    2323      Z = pos.Z;
    2424    }
     25
     26    public PackingPosition ToPackingPosition(int assignedBin) {
     27      return new PackingPosition(assignedBin, X, Y, Z);
     28    }
     29
    2530    public static Vector3D AlongX(Vector3D pos, PackingItem item) {
    2631      return new Vector3D(
     
    8691      return new Vector3D(a * b.X, a * b.Y, a * b.Z);
    8792    }
     93
     94    public static Vector3D operator *(double a, Vector3D b) {
     95      return new Vector3D((int)(a * b.X), (int)(a * b.Y), (int)(a * b.Z));
     96    }
     97
    8898    public static Vector3D operator *(Vector3D a, int b) {
    8999      return new Vector3D(a.X * b, a.Y * b, a.Z * b);
    90100    }
     101
     102    public static Vector3D operator *(Vector3D a, double b) {
     103      return new Vector3D((int)(b * a.X), (int)(b * a.Y), (int)(b * a.Z));
     104    }
     105
    91106    public static Vector3D operator +(Vector3D a, Vector3D b) {
    92107      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

    r15473 r15488  
    2020#endregion
    2121
     22using HeuristicLab.Common;
    2223using HeuristicLab.Core;
    2324using HeuristicLab.Encodings.PermutationEncoding;
    2425using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2526using HeuristicLab.Problems.BinPacking3D;
     27using HeuristicLab.Problems.BinPacking3D.ExtremePointCreation;
    2628using System;
    2729using System.Collections.Generic;
     
    3133
    3234namespace HeuristicLab.Problems.BinPacking3D.Packer {
    33   [Item("BinPacker", "A class for packing bins for the 3D bin-packer problem.")]
    34   [StorableClass]
    35   public abstract class BinPacker {
     35  public abstract class BinPacker : Item {
     36
     37    /*
     38    [Storable]
     39    IPositionFinder PositionFinder
    3640   
     41    */
     42
     43    #region Constructors for HEAL
     44
     45   
     46    [StorableConstructor]
     47    protected BinPacker(bool deserializing) : base(deserializing) { }
     48
     49    protected BinPacker(BinPacker original, Cloner cloner)
     50      : base(original, cloner) {
     51      //this.PositionFinder = original.PositionFinder;
     52    }
     53
     54    #endregion
     55
    3756    public BinPacker() { }
    3857
     
    4564    /// <param name="useStackingConstraints">Flag for using stacking constraints</param>
    4665    /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
    47     public abstract IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints);
     66    public abstract IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, bool useStackingConstraints);
    4867   
    4968    /// <summary>
     
    5473    /// <param name="packingItem"></param>
    5574    /// <param name="position"></param>
    56     protected virtual void PackItem(BinPacking3D packingBin, int itemId, PackingItem packingItem, PackingPosition position, bool useStackingConstraints) {
    57 
     75    protected virtual void PackItem(BinPacking3D packingBin, int itemId, PackingItem packingItem, PackingPosition position, IExtremePointCreator extremePointCreator, bool useStackingConstraints) {
     76      if (!CheckItemDimensions(packingBin, packingItem, position)) {
     77        throw new BinPacking3DException($"The dimensions of the given item exceeds the bin dimensions. " +
     78          $"Bin: ({packingBin.BinShape.Width} {packingBin.BinShape.Depth} {packingBin.BinShape.Height})" +
     79          $"Item: ({packingItem.Width} {packingItem.Depth} {packingItem.Height})");
     80      }
    5881      packingBin.PackItem(itemId, packingItem, position);
    59       packingBin.UpdateResidualSpace(packingItem, position);
    60       packingBin.UpdateExtremePoints(packingItem, position, useStackingConstraints);
     82      extremePointCreator.UpdateExtremePoints(packingBin, packingItem, position);
     83      extremePointCreator.UpdateResidualSpace(packingBin, packingItem, position);
    6184    }
    6285
     
    79102      return packingBin.ExtremePoints.Where(x => packingBin.IsPositionFeasible(newItem, x, useStackingConstraints)).FirstOrDefault();
    80103    }
     104
     105    /// <summary>
     106    /// Compares the dimensions of a given item and the current bin.
     107    /// </summary>
     108    /// <param name="item"></param>
     109    /// <returns>Returns true if the dimensions of an given item are less or equal to the bin.</returns>
     110    private bool CheckItemDimensions(BinPacking3D packingBin, PackingItem item, PackingPosition itemPosition) {
     111      var width = itemPosition.Rotated ? item.Depth : item.Width;
     112      var depth = itemPosition.Rotated ? item.Width : item.Depth;
     113      return packingBin.BinShape.Width >= width && packingBin.BinShape.Height >= item.Height && packingBin.BinShape.Depth >= depth;
     114    }
    81115  }
    82116}
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFirstFit.cs

    r15473 r15488  
    2020#endregion
    2121
     22using HeuristicLab.Common;
    2223using HeuristicLab.Core;
    2324using HeuristicLab.Encodings.PermutationEncoding;
    2425using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     26using HeuristicLab.Problems.BinPacking3D.ExtremePointCreation;
    2527using System;
    2628using System.Collections.Generic;
     
    3032
    3133namespace HeuristicLab.Problems.BinPacking3D.Packer {
     34  public class BinPackerFirstFit : BinPacker {
     35    #region Constructors for HEAL
     36    [StorableConstructor]
     37    protected BinPackerFirstFit(bool deserializing) : base(deserializing) { }
    3238
    33   [Item("BinPackerFirstFit", "A class for packing bins for the 3D bin-packer problem. It uses a first fit algorithm")]
    34   [StorableClass]
    35   public class BinPackerFirstFit : BinPacker {
     39    protected BinPackerFirstFit(BinPackerFirstFit original, Cloner cloner)
     40      : base(original, cloner) {
     41    }
     42
     43    public override IDeepCloneable Clone(Cloner cloner) {
     44      return new BinPackerFirstFit(this, cloner);
     45    }
     46    #endregion
    3647
    3748    public BinPackerFirstFit() : base() { }   
     
    4152    /// </summary>
    4253    /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
    43     public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
     54    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epGenerationMethod, bool useStackingConstraints) {
    4455      IList<BinPacking3D> packingList = new List<BinPacking3D>();
    4556      IList<int> remainingIds = new List<int>(sortedItems);
     
    4758      while (remainingIds.Count > 0) {
    4859        BinPacking3D packingBin = new BinPacking3D(binShape);
    49         PackRemainingItems(ref remainingIds, ref packingBin, items, useStackingConstraints, null);
     60        PackRemainingItems(ref remainingIds, ref packingBin, items, epGenerationMethod, useStackingConstraints, null);
    5061        packingList.Add(packingBin);
    5162      }
     
    6071    /// <param name="items">List of packing items. Some of the items will be assigned to the BinPacking3D object</param>
    6172    /// <param name="packingBin">This object will be filled with some of the given items</param>
    62     protected void PackRemainingItems(ref IList<int> remainingIds, ref BinPacking3D packingBin, IList<PackingItem> items, bool useStackingConstraints, Dictionary<int, bool> rotationArray) {
    63 
     73    protected void PackRemainingItems(ref IList<int> remainingIds, ref BinPacking3D packingBin, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, bool useStackingConstraints, Dictionary<int, bool> rotationArray) {
     74      IExtremePointCreator extremePointCreator = ExtremePointCreatorFactory.CreateExtremePointCreator(epCreationMethod, useStackingConstraints);
    6475      foreach (var itemId in new List<int>(remainingIds)) {
    6576        bool rotated = rotationArray == null ? false : rotationArray[itemId];
     
    6778        // if a valid packing position could be found, the current item can be added to the given bin
    6879        if (position != null) {
    69           PackItem(packingBin, itemId, items[itemId], position, useStackingConstraints);
     80          PackItem(packingBin, itemId, items[itemId], position, extremePointCreator, useStackingConstraints);
    7081          remainingIds.Remove(itemId);
    7182        }
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFreeVolumeBestFit.cs

    r15473 r15488  
    2020#endregion
    2121
     22using HeuristicLab.Common;
    2223using HeuristicLab.Core;
    2324using HeuristicLab.Encodings.PermutationEncoding;
    2425using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     26using HeuristicLab.Problems.BinPacking3D.ExtremePointCreation;
    2527using System;
    2628using System.Collections.Generic;
     
    3032
    3133namespace HeuristicLab.Problems.BinPacking3D.Packer {
    32   [Item("BinPackerFreeVolumeBestFit", "A class for packing bins for the 3D bin-packer problem. It uses a best fit algortihm depending on the free volume.")]
    33   [StorableClass]
    3434  public class BinPackerFreeVolumeBestFit : BinPacker {
     35   
     36    #region Constructors for HEAL
     37    [StorableConstructor]
     38    protected BinPackerFreeVolumeBestFit(bool deserializing) : base(deserializing) { }
     39
     40    protected BinPackerFreeVolumeBestFit(BinPackerFreeVolumeBestFit original, Cloner cloner)
     41      : base(original, cloner) {
     42    }
     43
     44    public override IDeepCloneable Clone(Cloner cloner) {
     45      return new BinPackerFreeVolumeBestFit(this, cloner);
     46    }
     47    #endregion
    3548
    3649    public BinPackerFreeVolumeBestFit() : base() { }
     
    4861    /// <param name="useStackingConstraints"></param>
    4962    /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
    50     public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
     63    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epGenerationMethod, bool useStackingConstraints) {
    5164      IList<BinPacking3D> packingList = new List<BinPacking3D>();
    5265      IList<int> remainingIds = new List<int>(sortedItems);
    53 
     66      IExtremePointCreator extremePointCreator = ExtremePointCreatorFactory.CreateExtremePointCreator(epGenerationMethod, useStackingConstraints);
    5467      foreach (int remainingId in remainingIds) {
    5568        var sortedBins = packingList.OrderBy(x => x.FreeVolume);
     
    6477          var bin = packingBin;
    6578          if (positionFound) {
    66             PackItem(bin, remainingId, item, position, useStackingConstraints);
     79            PackItem(bin, remainingId, item, position, extremePointCreator, useStackingConstraints);
    6780            break;
    6881          }
     
    7487
    7588          if (position == null) {
    76             throw new InvalidOperationException("Item " + remainingId + " cannot be packed in empty bin.");
     89            throw new InvalidOperationException("Item " + remainingId + " cannot be packed into an empty bin.");
    7790          }
    7891
    79           PackItem(packingBin, remainingId, item, position, useStackingConstraints);
     92          PackItem(packingBin, remainingId, item, position, extremePointCreator, useStackingConstraints);
    8093          packingList.Add(packingBin);
    8194        }
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerResidualSpaceBestFit.cs

    r15473 r15488  
    2020#endregion
    2121
     22using HeuristicLab.Common;
    2223using HeuristicLab.Core;
    2324using HeuristicLab.Encodings.PermutationEncoding;
    2425using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     26using HeuristicLab.Problems.BinPacking3D.ExtremePointCreation;
    2527using System;
    2628using System.Collections.Generic;
     
    3032
    3133namespace HeuristicLab.Problems.BinPacking3D.Packer {
    32   [Item("BinPackerResidualSpaceBestFit", "A class for packing bins for the 3D bin-packer problem. It uses a best fit algortihm depending on the residual space.")]
    33   [StorableClass]
    3434  public class BinPackerResidualSpaceBestFit : BinPacker {
     35
     36    #region Constructors for HEAL
     37    [StorableConstructor]
     38    protected BinPackerResidualSpaceBestFit(bool deserializing) : base(deserializing) { }
     39
     40    protected BinPackerResidualSpaceBestFit(BinPackerResidualSpaceBestFit original, Cloner cloner)
     41      : base(original, cloner) {
     42    }
     43
     44    public override IDeepCloneable Clone(Cloner cloner) {
     45      return new BinPackerResidualSpaceBestFit(this, cloner);
     46    }
     47    #endregion
    3548
    3649    public BinPackerResidualSpaceBestFit() : base() { }
     
    4255    /// </summary>
    4356    /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
    44     public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {
     57    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epGenerationMethod, bool useStackingConstraints) {
    4558      IList<BinPacking3D> packingList = new List<BinPacking3D>();
    4659      IList<int> remainingIds = new List<int>(sortedItems);
     60      IExtremePointCreator extremePointCreator = ExtremePointCreatorFactory.CreateExtremePointCreator(epGenerationMethod, useStackingConstraints);
    4761      bool rotated = false;
    4862
     
    5670          if (point.Item1.IsPositionFeasible(item, point.Item2, useStackingConstraints)) {
    5771            var binPacking = point.Item1;
    58             PackItem(binPacking, remainingId, item, point.Item2, useStackingConstraints);
     72            PackItem(binPacking, remainingId, item, point.Item2, extremePointCreator, useStackingConstraints);
    5973            packed = true;
    6074            break;
     
    6680          var position = FindPackingPositionForItem(binPacking, item, useStackingConstraints, rotated);
    6781          if (position != null) {
    68             PackItem(binPacking, remainingId, item, position, useStackingConstraints);
     82            PackItem(binPacking, remainingId, item, position, extremePointCreator, useStackingConstraints);
    6983          } else {
    70             throw new InvalidOperationException("Item " + remainingId + " cannot be packed in an empty bin.");
     84            throw new InvalidOperationException("Item " + remainingId + " cannot be packed into an empty bin.");
    7185          }
    7286          packingList.Add(binPacking);
    7387        }
    7488      }
    75 
    7689      return packingList;
    7790    }
     
    110123          (rs.Item3 - item.Depth));
    111124    }
    112 
    113125  }
    114126}
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj

    r15473 r15488  
    103103    <Compile Include="2D\ProblemBase.cs" />
    104104    <Compile Include="2D\Solution.cs" />
     105    <Compile Include="3D\BinPacking3DException.cs" />
     106    <Compile Include="3D\ExtremePointCreation\ExtremePointCreatorFactory.cs" />
     107    <Compile Include="3D\ExtremePointCreation\ExtremePointCreator.cs" />
     108    <Compile Include="3D\ExtremePointCreation\IExtremePointCreator.cs" />
     109    <Compile Include="3D\ExtremePointCreation\LineProjectionBasedEPCreator.cs" />
     110    <Compile Include="3D\ExtremePointCreation\PointProjectionBasedEPCreator.cs" />
     111    <Compile Include="3D\Geometry\Edge3D.cs" />
    105112    <Compile Include="3D\Packer\BinPacker.cs" />
    106113    <Compile Include="3D\Packer\BinPackerFactory.cs" />
     
    123130    <Compile Include="3D\Encoding\IDecoder.cs" />
    124131    <Compile Include="3D\Evaluators\IEvaluator.cs" />
    125     <Compile Include="3D\IOperator.cs" />
     132    <Compile Include="3D\Sorting\IOperator.cs" />
    126133    <Compile Include="3D\Evaluators\MoveEvaluatorBase.cs" />
    127134    <Compile Include="3D\PackingItem.cs" />
Note: See TracChangeset for help on using the changeset viewer.