Ignore:
Timestamp:
01/16/18 15:40:43 (22 months ago)
Author:
rhanghof
Message:

#2817:

  • The items can be rotated and tilted now.
  • Added pruning of extreme points in packed bins.
  • Added new packer which packs items by positioning them on the point with the minimum of wasted space. He uses rotating and tilting of items.
  • Added classes for sorting given items.
File:
1 edited

Legend:

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

    r15585 r15617  
    1 using HeuristicLab.Common;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     4 *
     5 * This file is part of HeuristicLab.
     6 *
     7 * HeuristicLab is free software: you can redistribute it and/or modify
     8 * it under the terms of the GNU General Public License as published by
     9 * the Free Software Foundation, either version 3 of the License, or
     10 * (at your option) any later version.
     11 *
     12 * HeuristicLab is distributed in the hope that it will be useful,
     13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
     14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     15 * GNU General Public License for more details.
     16 *
     17 * You should have received a copy of the GNU General Public License
     18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
     19 */
     20#endregion
     21
     22using HeuristicLab.Common;
    223using HeuristicLab.Problems.BinPacking3D.Geometry;
    324using HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation;
     
    728using System.Text;
    829using System.Threading.Tasks;
     30using System.Collections.Concurrent;
    931
    1032namespace HeuristicLab.Problems.BinPacking3D.ExtremePointCreation {
     
    1537  public class LineProjectionBasedEPCreator : ExtremePointCreator {
    1638
     39    /// <summary>
     40    /// This lock object is needed because of creating the extreme points in an parallel for loop.
     41    /// </summary>
     42    object _lockAddExtremePoint = new object();
     43
    1744    protected override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    1845      binPacking.ExtremePoints.Clear();
    1946
    20       foreach (var i in binPacking.Items) {
     47      // generate all new extreme points parallel. This speeds up the creator.
     48      Parallel.ForEach(binPacking.Items, i => {
    2149        PackingItem it = i.Value;
    2250        PackingPosition p = binPacking.Positions[i.Key];
    2351        GenerateNewExtremePointsForItem(binPacking, it, p);
    24       }
    25      
     52      });
     53
    2654      // remove not needed extreme points.
    2755      foreach (var extremePoint in binPacking.ExtremePoints.ToList()) {
     
    3765        }
    3866      }
    39     }
    40    
     67     
     68    }
     69
    4170    /// <summary>
    4271    /// Returns true if a given residual space can be removed.
     
    6089          if (itemBelowEp || !itemBelowEp && !itemBelowPos) {
    6190            return true;
    62           }         
     91          }
    6392        }
    6493      }
    6594      return false;
    6695    }
    67    
     96
    6897    /// <summary>
    6998    /// Returns true if the given position lies on an item or an the ground.
     
    80109        var itemPosition = binPacking.Positions[x.Key];
    81110        var item = x.Value;
    82         int width = itemPosition.Rotated ? item.Depth : item.Width;
    83         int depth = itemPosition.Rotated ? item.Width : item.Depth;
     111        int width = item.Width;
     112        int depth = item.Depth;
    84113
    85114        return itemPosition.Y + item.Height == position.Y &&
     
    110139      }
    111140
    112       if (binPacking.ExtremePoints.ContainsKey(position)) {
    113         return false;
    114       }
    115 
    116       var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
    117 
    118       if (rs.Count() <= 0) {
    119         return false;
    120       }
    121 
    122       binPacking.ExtremePoints.Add(position, rs);
    123       return true;
     141      // this is necessary if the extreme points are being created in a parallel loop.
     142      lock (_lockAddExtremePoint) {
     143        if (binPacking.ExtremePoints.ContainsKey(position)) {
     144          return false;
     145        }
     146
     147        var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
     148
     149        if (rs.Count() <= 0) {
     150          return false;
     151        }
     152
     153        binPacking.ExtremePoints.Add(position, rs);
     154        return true;
     155      }
    124156    }
    125157
     
    148180    /// <param name="position"></param>
    149181    private void PointProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
    150       int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
    151       int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
     182      int newWidth = newItem.Width;
     183      int newDepth = newItem.Depth;
    152184      var binShape = binPacking.BinShape;
    153185      var sourcePoint = new PackingPosition(position.AssignedBin, position.X + newWidth, position.Y, position.Z);
     
    196228    /// <param name="position"></param>
    197229    private void EdgeProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
    198       int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
    199       int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
     230      int newWidth = newItem.Width;
     231      int newDepth = newItem.Depth;
    200232      var binShape = binPacking.BinShape;
    201233
     
    235267      foreach (var item in binPacking.Items) {
    236268        PackingPosition position = binPacking.Positions[item.Key];
    237         var depth = position.Rotated ? item.Value.Width : item.Value.Depth;
    238         var width = position.Rotated ? item.Value.Depth : item.Value.Width;
     269        var depth = item.Value.Depth;
     270        var width = item.Value.Width;
    239271        if (position.X <= point.X && point.X < position.X + width &&
    240272            position.Y <= point.Y && point.Y < position.Y + item.Value.Height &&
     
    444476    /// <returns></returns>
    445477    private Vector3D[] GetVertices(PackingItem item, PackingPosition position) {
    446       int width = position.Rotated ? item.Depth : item.Width;
    447       int depth = position.Rotated ? item.Width : item.Depth;
     478      int width = item.Width;
     479      int depth = item.Depth;
    448480      return new Vector3D[] {
    449481        new Vector3D(position.X + 0,     position.Y + 0,           position.Z + 0), // (0,0,0)
     
    574606        }
    575607      }
     608
    576609      return eps as IEnumerable<Vector3D>;
    577610    }
Note: See TracChangeset for help on using the changeset viewer.