Free cookie consent management tool by TermsFeed Policy Generator

Changeset 15554


Ignore:
Timestamp:
12/20/17 16:15:38 (7 years ago)
Author:
rhanghof
Message:

#2817:

  • Unittests
  • Bugfixes on the line projection based extreme point creation method
Location:
branches/2817-BinPackingSpeedup
Files:
18 added
5 deleted
21 edited

Legend:

Unmodified
Added
Removed

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

    r15520 r15554  
    7474    private Dictionary<int, DiffuseMaterial> materials;
    7575
    76     public ObservableDictionary<BinPacking3D.PackingPosition, ResidualSpace> ResidualSpaces { get; set; }
     76    public ObservableDictionary<BinPacking3D.PackingPosition, IList<ResidualSpace>> ResidualSpaces { get; set; }
    7777    public ObservableCollection<BinPacking3D.PackingPosition> ExtremePoints { get; set; }
    7878
    … …  
    8181      camMain.Position = new Point3D(0.5, 3, 3); // for design time we use a different camera position
    8282      materials = new Dictionary<int, DiffuseMaterial>();
    83       ResidualSpaces = new ObservableDictionary<BinPacking3D.PackingPosition, ResidualSpace>();
     83      ResidualSpaces = new ObservableDictionary<BinPacking3D.PackingPosition, IList<ResidualSpace>>();
    8484      ExtremePoints = new ObservableCollection<BinPacking3D.PackingPosition>();
    8585      selectedExtremePointIndex = -1;
    … …  
    240240    private void AddResidualSpacesForExtremePoint(Model3DGroup modelGroup, BinPacking3D.PackingPosition extremePoint) {
    241241      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.Width,
    251           rs.Height,
    252           rs.Depth);
    253 
     242        foreach (var rs in ResidualSpaces[extremePoint]) {
     243          var containerModel1 = new GeometryModel3D(new MeshGeometry3D(), new DiffuseMaterial(new SolidColorBrush(residualSpaceColor)));
     244
     245          modelGroup.Children.Add(containerModel1);
     246
     247          AddWireframeCube((MeshGeometry3D)containerModel1.Geometry,
     248            extremePoint.X,
     249            extremePoint.Y,
     250            extremePoint.Z,
     251            rs.Width,
     252            rs.Height,
     253            rs.Depth);
     254        }
    254255      }
     256       
    255257    }
    256258

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

    r15520 r15554  
    2424using HeuristicLab.MainForm;
    2525using HeuristicLab.Problems.BinPacking3D;
     26using System.Collections.Generic;
    2627
    2728namespace HeuristicLab.Problems.BinPacking.Views {
    … …  
    7576        itemSelection.Items.Add(item.Key);
    7677      }
    77       foreach (var ep in ((BinPacking3D.BinPacking3D)packing).ExtremePoints) {
    78         var rs = ((BinPacking3D.BinPacking3D)packing).ResidualSpaces[ep];
     78      foreach (var extremPoint in ((BinPacking3D.BinPacking3D)packing).ExtremePoints) {
     79        var ep = extremPoint.Key;
    7980        extremePointsSelection.Items.Add($"({ep.X}, {ep.Y}, {ep.Z})");
    8081        packingPlan3D.ExtremePoints.Add(ep);
    81         packingPlan3D.ResidualSpaces.Add(ep, rs);
     82        packingPlan3D.ResidualSpaces.Add(ep, extremPoint.Value as IList<ResidualSpace>);
    8283      }
    8384

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

    r15520 r15554  
    3434  [StorableClass]
    3535  public class BinPacking3D : BinPacking<PackingPosition, PackingShape, PackingItem> {
    36 
     36   
    3737    [Storable]
    38     public Dictionary<PackingPosition, ResidualSpace> ResidualSpaces { get; set; }
    39 
    40     [Storable]
    41     public SortedSet<PackingPosition> ExtremePoints { get; protected set; }
     38    public IDictionary<PackingPosition, IEnumerable<ResidualSpace>> ExtremePoints { get; protected set; }
    4239
    4340
    4441    public BinPacking3D(PackingShape binShape)
    4542      : base(binShape) {
    46       ExtremePoints = new SortedSet<PackingPosition>();
    47       ResidualSpaces = new Dictionary<PackingPosition, ResidualSpace>();
     43      ExtremePoints = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
    4844     
    49       ExtremePoints.Add(binShape.Origin);
    50       ResidualSpaces.Add(binShape.Origin, new ResidualSpace(BinShape.Width, BinShape.Height, BinShape.Depth));
     45      ExtremePoints.Add(binShape.Origin, new List<ResidualSpace>() {ResidualSpace.Create(binShape.Width, binShape.Height, binShape.Depth)});
    5146    }
    5247
    … …  
    5651    protected BinPacking3D(BinPacking3D original, Cloner cloner)
    5752      : base(original, cloner) {
    58       this.ResidualSpaces = new Dictionary<PackingPosition, ResidualSpace>();
    59       foreach (var o in original.ResidualSpaces)
    60         this.ResidualSpaces.Add(cloner.Clone(o.Key), ResidualSpace.Create(o.Value));
    61 
    62       this.ExtremePoints = new SortedSet<PackingPosition>(original.ExtremePoints.Select(p => cloner.Clone(p)));
     53
     54      this.ExtremePoints = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
     55      foreach (var extremePoint in original.ExtremePoints) {
     56        var residualSpaces = new List<ResidualSpace>();
     57        foreach (var residualSpace in extremePoint.Value) {
     58          residualSpaces.Add(cloner.Clone(residualSpace));
     59        }
     60        ExtremePoints.Add(cloner.Clone(extremePoint.Key), residualSpaces);
     61      }
    6362    }
    6463
    … …  
    6766    }
    6867
    69 
    70     [StorableHook(HookType.AfterDeserialization)]
    71     private void AfterDeserialization() {
    72       // BackwardsCompatibility3.3
    73       #region Backwards compatible code, remove with 3.4
    74       if (ResidualSpaces == null)
    75         ResidualSpaces = new Dictionary<PackingPosition, ResidualSpace>();
    76       #endregion
    77     }
    78 
    79 
    80 
     68   
    8169
    8270    /// <summary>
    … …  
    9078      Positions[itemID] = position;
    9179      ExtremePoints.Remove(position);
    92       ResidualSpaces.Remove(position);
    9380    }
    9481

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

    r15520 r15554  
    4646        // Projecting onto the XZ-plane
    4747        var below = ProjectDown(binPacking, sourcePoint);
    48         var residualSpace = CalculateResidualSpace(binPacking, below);
    49         if (!residualSpace.IsZero()
    50           && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpace)) {
     48        var residualSpaces = CalculateResidualSpace(binPacking, below);
     49        if (residualSpaces.Count() > 0
     50          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpaces)) {
    5151          // add only if the projected point's residual space is not a sub-space
    5252          // of another extreme point's residual space
    … …  
    5656        // Projecting onto the XY-plane
    5757        var back = ProjectBackward(binPacking, sourcePoint);
    58         residualSpace = CalculateResidualSpace(binPacking, back);
    59         if (!residualSpace.IsZero()
    60           && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpace)) {
     58        residualSpaces = CalculateResidualSpace(binPacking, back);
     59        if (residualSpaces.Count() > 0
     60          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpaces)) {
    6161          // add only if the projected point's residual space is not a sub-space
    6262          // of another extreme point's residual space
    … …  
    7171        // Projecting onto the YZ-plane
    7272        var left = ProjectLeft(binPacking, sourcePoint);
    73         var residualSpace = CalculateResidualSpace(binPacking, left);
    74         if (!residualSpace.IsZero()
    75           && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpace)) {
     73        var residualSpaces = CalculateResidualSpace(binPacking, left);
     74        if (residualSpaces.Count() > 0
     75          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpaces)) {
    7676          // add only if the projected point's residual space is not a sub-space
    7777          // of another extreme point's residual space
    … …  
    8181        // Projecting onto the XY-plane
    8282        var back = ProjectBackward(binPacking, sourcePoint);
    83         residualSpace = CalculateResidualSpace(binPacking, back);
    84         if (!residualSpace.IsZero()
    85           && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpace)) {
     83        residualSpaces = CalculateResidualSpace(binPacking, back);
     84        if (residualSpaces.Count() > 0
     85          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpaces)) {
    8686          // add only if the projected point's residual space is not a sub-space
    8787          // of another extreme point's residual space
    … …  
    9696        // Projecting onto the XZ-plane
    9797        var below = ProjectDown(binPacking, sourcePoint);
    98         var residualSpace = CalculateResidualSpace(binPacking, below);
    99         if (!residualSpace.IsZero()
    100           && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpace)) {
     98        var residualSpaces = CalculateResidualSpace(binPacking, below);
     99        if (residualSpaces.Count() > 0
     100          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpaces)) {
    101101          // add only if the projected point's residual space is not a sub-space
    102102          // of another extreme point's residual space
    … …  
    106106        // Projecting onto the YZ-plane
    107107        var left = ProjectLeft(binPacking, sourcePoint);
    108         residualSpace = CalculateResidualSpace(binPacking, left);
    109         if (!residualSpace.IsZero()
    110           && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpace)) {
     108        residualSpaces = CalculateResidualSpace(binPacking, left);
     109        if (residualSpaces.Count() > 0
     110          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpaces)) {
    111111          // add only if the projected point's residual space is not a sub-space
    112112          // of another extreme point's residual space
    … …  
    191191    /// <param name="residualSpace"></param>
    192192    /// <returns></returns>
    193     protected virtual bool IsWithinResidualSpaceOfAnotherExtremePoint(BinPacking3D binPacking, Vector3D pos, ResidualSpace residualSpace) {
    194       var eps = binPacking.ExtremePoints.Where(x => !pos.Equals(x) && pos.IsInside(x, binPacking.ResidualSpaces[x]));
    195       return eps.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, residualSpace, x, binPacking.ResidualSpaces[x]));
     193    protected bool IsWithinResidualSpaceOfAnotherExtremePoint(BinPacking3D binPacking, Vector3D pos, ResidualSpace residualSpace) {
     194      var eps = binPacking.ExtremePoints.Where(x => !pos.Equals(x.Key) && pos.IsInside(x.Key, x.Value));
     195      return eps.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, residualSpace, x.Key, x.Value));
     196    }
     197
     198    /// <summary>
     199    ///
     200    /// </summary>
     201    /// <param name="binPacking"></param>
     202    /// <param name="pos"></param>
     203    /// <param name="residualSpaces"></param>
     204    /// <returns></returns>
     205    protected bool IsWithinResidualSpaceOfAnotherExtremePoint(BinPacking3D binPacking, Vector3D pos, IEnumerable<ResidualSpace> residualSpaces) {
     206      foreach (var residualSpace in residualSpaces) {
     207        if (IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, pos, residualSpace)) {
     208          return true;
     209        }
     210      }
     211      return false;
     212    }
     213
     214
     215    /// <summary>
     216    /// Returns true, if the given poisition and the related residual space is within the residual space of the given extreme point
     217    /// </summary>
     218    /// <param name="pos"></param>
     219    /// <param name="rsPos"></param>
     220    /// <param name="ep"></param>
     221    /// <param name="rsEp"></param>
     222    /// <returns></returns>
     223    protected bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, ResidualSpace rsPos, PackingPosition ep, IEnumerable<ResidualSpace> rsEp) {
     224      return rsEp.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, rsPos, ep, x));
    196225    }
    197226
    … …  
    211240
    212241    /// <summary>
    213     /// Calculates the residual space for a given bin packing and position.
    214     /// It returns the residual space as a tuple which contains the dimensions
    215     /// </summary>
    216     /// <param name="binPacking"></param>
    217     /// <param name="pos"></param>
    218     /// <returns>A Tuple(width, Height, Depth)</width></returns>
    219     protected virtual ResidualSpace CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
    220       //return ResidualSpaceCalculator.Create().CalculateResidualSpace(binPacking, pos).First();
    221       return new ResidualSpace(CalculateResidualSpaceOld(binPacking, pos));
    222     }
    223 
    224     protected virtual Tuple<int, int, int> CalculateResidualSpaceOld(BinPacking3D binPacking, Vector3D pos) {
    225 
    226       if (pos == null) {
    227         return Tuple.Create(0, 0, 0);
    228       }
    229       var itemPos = binPacking.Items.Select(x => new {
    230         Item = x.Value,
    231         Position = binPacking.Positions[x.Key]
    232       });
    233       Vector3D limit = new Vector3D() {
    234         X = binPacking.BinShape.Width,
    235         Y = binPacking.BinShape.Height,
    236         Z = binPacking.BinShape.Depth
    237       };
    238 
    239       if (pos.X < limit.X && pos.Y < limit.Y && pos.Z < limit.Z) {
    240         var rightLimit = ProjectRight(binPacking, pos);
    241         var upLimit = ProjectUp(binPacking, pos);
    242         var forwardLimit = ProjectForward(binPacking, pos);
    243         if (rightLimit.X > 0) {
    244           limit.X = rightLimit.X;
    245         }
    246         if (upLimit.Y > 0) {
    247           limit.Y = upLimit.Y;
    248         }
    249         if (forwardLimit.Z > 0) {
    250           limit.Z = forwardLimit.Z;
    251         }
    252       }
    253 
    254       if (limit.X - pos.X <= 0 || limit.Y - pos.Y <= 0 || limit.Z - pos.Z <= 0) {
    255         return Tuple.Create(0, 0, 0);
    256       }
    257       return Tuple.Create(limit.X - pos.X, limit.Y - pos.Y, limit.Z - pos.Z);
    258     }
    259 
     242    /// Calculates the residual spaces for a given bin packing and position.
     243    /// It returns a collection of residual spaces
     244    /// </summary>
     245    /// <param name="binPacking"></param>
     246    /// <param name="pos"></param>
     247    /// <returns></returns>
     248    protected abstract IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos);
     249   
    260250    #endregion
    261251

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

    r15520 r15554  
    1515  public class LineProjectionBasedEPCreator : ExtremePointCreator {
    1616
    17 
    18 
    19 
    2017    protected override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    21       // After a item has been placed, the residual space has to be recalculated.
    22       //RecalculateResidualSpaces(binPacking);
    23 
    24       //GenerateNewExtremePointsForItem(binPacking, item, position);
    25 
    2618      binPacking.ExtremePoints.Clear();
    27       binPacking.ResidualSpaces.Clear();
    2819
    2920      foreach (var i in binPacking.Items) {
    … …  
    3223        GenerateNewExtremePointsForItem(binPacking, it, p);
    3324      }
    34       //RecalculateResidualSpaces(binPacking);
    35     }
    36 
    37     /// <summary>
    38     /// Adds an new extreme point an the related residual space to a given bin packing.
    39     /// - The given position has to be valid
    40     /// - The residual space must not be zero
    41     /// </summary>
    42     /// <param name="binPacking"></param>
    43     /// <param name="position"></param>
    44     /// <returns></returns>
     25    }
     26
     27    /// <summary>
     28    /// Adds a new extreme point an the related residual spaces to a given bin packing.
     29    /// - The given position has to be valid.
     30    /// - The extreme point does not exist in the bin packing.
     31    /// - There must be at minimum one valid residual space. A residual space is invalid if the space is zero.
     32    /// </summary>
     33    /// <param name="binPacking"></param>
     34    /// <param name="position"></param>
     35    /// <returns>True = the given point and its related residual spaces were successfully added to the bin packing</returns>
    4536    protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
    4637      if (position == null) {
    … …  
    4839      }
    4940
    50       if (PointIsInItem(binPacking, new Vector3D(position))) {
     41      if (PointIsInAnyItem(binPacking, new Vector3D(position))) {
    5142        return false;
    5243      }
    5344
     45      if (binPacking.ExtremePoints.ContainsKey(position)) {
     46        return false;
     47      }
     48
    5449      var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
    5550
    56       if (rs.IsZero()) {
     51      if (rs.Count() <= 0) {
    5752        return false;
    5853      }
    5954
    60       if (!binPacking.ExtremePoints.Add(position)) {
     55      // todo
     56      /*
     57       ist der extrempunkt im residual space eines anderen muss ueberprueft werden:
     58          - ist der andere ep in der luft, kann auch dieser hinzugefuegt werden.
     59          - hat der andere ep ein item unterhalb, darf dieser nicht hinzugefuegt werden.
     60       -> neu methode basierend auf IsWithinResidualSpaceOfAnotherExtremePoint, die den ep oder rs zurueck gibt, der einen anderen rs einschließt.
     61          eventuell gehoert diese logik in den ResidualSpaceCreator.
     62      if (LiesOnAnyItem(binPacking, position)) {
    6163        return false;
    62       }
    63 
    64       binPacking.ResidualSpaces.Add(position, rs);
     64      }*/
     65
     66      binPacking.ExtremePoints.Add(position, rs);
    6567      return true;
     68    }
     69
     70    private bool LiesOnAnyItem(BinPacking3D binPacking, PackingPosition position) {
     71      if (position.Y == 0) {
     72        return true;
     73      }
     74
     75      var items = binPacking.Items.Where(x => {
     76        var itemPosition = binPacking.Positions[x.Key];
     77        var item = x.Value;
     78        int width = itemPosition.Rotated ? item.Depth : item.Width;
     79        int depth = itemPosition.Rotated ? item.Width : item.Depth;
     80
     81        return itemPosition.Y + item.Height == position.Y &&
     82               itemPosition.X <= position.X && position.X < itemPosition.X + width &&
     83               itemPosition.Z <= position.Z && position.Z < itemPosition.Z + depth;
     84      });
     85
     86      return items.Count() > 0;
    6687    }
    6788
    … …  
    83104    /// <summary>
    84105    /// This method creates extreme points by using a point projection based method.
    85     /// For each item there will be three points created and each of the point will be projected twice.
     106    /// For each item there will be created three points and each of the points will be projected twice.
    86107    /// The direction of the projection depends on position of the point.
    87108    /// </summary>
    … …  
    118139      if (sourcePoint.X < binPacking.BinShape.Width && sourcePoint.Y < binPacking.BinShape.Height && sourcePoint.Z < binPacking.BinShape.Depth) {
    119140        Vector3D point = projectionMethod?.Invoke(binPacking, sourcePoint);
    120         AddExtremePoint(binPacking, new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
     141        if (point != null) {
     142          AddExtremePoint(binPacking, new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
     143        }
    121144      }
    122145    }
    … …  
    141164
    142165      foreach (var ep in GetEpsOnLeft(binPacking, newItem, position)) {
    143         AddExtremePoint(binPacking, ep);
     166        AddExtremePoint(binPacking, ep.Key);
    144167      }
    145168
    146169      foreach (var ep in GetEpsBelow(binPacking, newItem, position)) {
    147         AddExtremePoint(binPacking, ep);
     170        AddExtremePoint(binPacking, ep.Key);
    148171      }
    149172
    150173      foreach (var ep in GetEpsBehind(binPacking, newItem, position)) {
    151         AddExtremePoint(binPacking, ep);
     174        AddExtremePoint(binPacking, ep.Key);
    152175      }
    153176    }
    154177    #endregion
    155178
    156 
     179    /// <summary>
     180    /// Updates the residual spaces.
     181    /// It removes not needed ones.
     182    /// A residual space will be removed if the space is a subspace of another one and
     183    /// the current one has no item below or both have an item below.
     184    /// </summary>
     185    /// <param name="binPacking"></param>
     186    /// <param name="item"></param>
     187    /// <param name="position"></param>
    157188    protected override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    158       return;
    159     }
    160 
    161     private bool PointIsInItem(BinPacking3D binPacking, Vector3D point) {
     189    }
     190
     191    /// <summary>
     192    /// Returns true if any item in the bin packing encapsulates the given point
     193    /// </summary>
     194    /// <param name="binPacking"></param>
     195    /// <param name="point"></param>
     196    /// <returns></returns>
     197    private bool PointIsInAnyItem(BinPacking3D binPacking, Vector3D point) {
    162198      foreach (var item in binPacking.Items) {
    163199        PackingPosition position = binPacking.Positions[item.Key];
    … …  
    184220    }
    185221
    186     /// <summary>
    187     /// Recalculates the residual spaces if needed.
    188     /// It checks if an item is in an residual space and if so the residual space will be recalculated.
    189     /// If the residual space has gone to zero, this residual space and its related extreme point will be removed.
    190     /// </summary>
    191     /// <param name="binPacking"></param>
    192     private void RecalculateResidualSpaces(BinPacking3D binPacking) {
    193       var recalculatedSpaces = new Dictionary<PackingPosition, ResidualSpace>();
    194       foreach (var ep in binPacking.ExtremePoints.ToList()) {
    195         var newRs = CalculateResidualSpace(binPacking, new Vector3D(ep));
    196         if (!newRs.IsZero() && !PointIsInItem(binPacking, new Vector3D(ep))) {
    197           recalculatedSpaces.Add(ep, newRs);
    198         } else {
    199           binPacking.ExtremePoints.Remove(ep);
    200         }
    201       }
    202       binPacking.ResidualSpaces = recalculatedSpaces;
    203     }
    204 
    205222    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    206223      return binPacking.Items.Select(x => new {
    … …  
    228245
    229246    /// <summary>
    230     /// Returns the extremepoints on the left side of an given item
    231     /// </summary>
    232     /// <param name="item"></param>
    233     /// <param name="position"></param>
    234     /// <returns></returns>
    235     private IList<PackingPosition> GetEpsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    236       IList<PackingPosition> eps = new List<PackingPosition>();
     247    /// Returns the extreme points and its related residual spaces on the left side of an given item.
     248    /// This extreme points are being created by intersecting two edges on the left side of the given item
     249    /// (left - in front, left - on top) with all edges on the right side of all other items int the bin packing.
     250    /// </summary>
     251    /// <param name="item"></param>
     252    /// <param name="position"></param>
     253    /// <returns></returns>
     254    private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
     255      var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
    237256      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsOnLeft(binPacking, item, position);
    238257      var edges = GetProjectionEdgesOnLeft(item, position);
    239258
    240259      foreach (var otherItem in items) {
     260        if (position.Equals(otherItem.Item1)) {
     261          continue;
     262        }
     263
    241264        var otherItemEdges = GetEdgesOnRight(otherItem.Item2, otherItem.Item1);
     265        // left - in front
    242266        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(1, 0, 0))) {
    243267          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
     268            // As this edge has a vertical direction, every point of intersection won't have an item below.
     269            // So finally it is being projected down.
    244270            var point = ProjectDown(binPacking, ProjectLeft(binPacking, ep));
    245             var residualSpace = CalculateResidualSpace(binPacking, point);
    246             if (!residualSpace.IsZero()) {
    247               eps.Add(point.ToPackingPosition(position.AssignedBin));
     271            var residualSpaces = CalculateResidualSpace(binPacking, point);
     272            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
     273            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
     274              eps.Add(newExtremePoint, residualSpaces);
    248275            }
    249276          }
    250277        }
     278
     279        // left - on top
    251280        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(1, 0, 0))) {
    252281          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
    253282            var point = ProjectLeft(binPacking, ep);
    254             var residualSpace = CalculateResidualSpace(binPacking, point);
    255             if (!residualSpace.IsZero()) {
    256               eps.Add(point.ToPackingPosition(position.AssignedBin));
     283            var residualSpaces = CalculateResidualSpace(binPacking, point);
     284            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
     285            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
     286              eps.Add(newExtremePoint, residualSpaces);
    257287            }
    258288          }
    … …  
    264294
    265295    /// <summary>
    266     /// Returns the extremepoints below of an given item
    267     /// </summary>
    268     /// <param name="item"></param>
    269     /// <param name="position"></param>
    270     /// <returns></returns>
    271     private IList<PackingPosition> GetEpsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    272       IList<PackingPosition> eps = new List<PackingPosition>();
     296    /// Returns the extreme points and its related residual spaces below of an given item.
     297    /// This extreme points are being created by intersecting two edges below of the given item
     298    /// (below - in front, below - right) with all edges on top side of all other items int the bin packing.
     299    /// </summary>
     300    /// <param name="item"></param>
     301    /// <param name="position"></param>
     302    /// <returns></returns>
     303    private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
     304      var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
    273305      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBelow(binPacking, position);
    274306      var edges = GetProjectionEdgesBelow(item, position);
    275307
    276308      foreach (var otherItem in items) {
     309        if (position.Equals(otherItem.Item1)) {
     310          continue;
     311        }
     312
    277313        var otherItemEdges = GetEdgesOnTop(otherItem.Item2, otherItem.Item1);
     314        // below - in front
    278315        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 1, 0))) {
    279316          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
    280317            var point = ProjectDown(binPacking, ep);
    281             var residualSpace = CalculateResidualSpace(binPacking, point);
    282             if (!residualSpace.IsZero()) {
    283               eps.Add(point.ToPackingPosition(position.AssignedBin));
     318            var residualSpaces = CalculateResidualSpace(binPacking, point);
     319            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
     320            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
     321              eps.Add(newExtremePoint, residualSpaces);
    284322            }
    285323          }
    286324        }
     325
     326        // below - right
    287327        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 1, 0))) {
    288328          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
    289329            var point = ProjectDown(binPacking, ep);
    290             var residualSpace = CalculateResidualSpace(binPacking, point);
    291             if (!residualSpace.IsZero()) {
    292               eps.Add(point.ToPackingPosition(position.AssignedBin));
     330            var residualSpaces = CalculateResidualSpace(binPacking, point);
     331            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
     332            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
     333              eps.Add(newExtremePoint, residualSpaces);
    293334            }
    294335          }
    … …  
    299340
    300341    /// <summary>
    301     /// Returns
    302     /// </summary>
    303     /// <param name="item"></param>
    304     /// <param name="position"></param>
    305     /// <returns></returns>
    306     private IList<PackingPosition> GetEpsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    307       IList<PackingPosition> eps = new List<PackingPosition>();
     342    /// Returns the extreme points and its related residual spaces below of an given item.
     343    /// This extreme points are being created by intersecting two edges below of the given item
     344    /// (right - behind, on top - behind) with all edges on top side of all other items int the bin packing.
     345    /// </summary>
     346    /// <param name="item"></param>
     347    /// <param name="position"></param>
     348    /// <returns></returns>
     349    private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
     350      var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();
    308351      IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBehind(binPacking, position);
    309352      var edges = GetProjectionEdgesBehind(item, position);
    310353
    311354      foreach (var otherItem in items) {
     355        if (position.Equals(otherItem.Item1)) {
     356          continue;
     357        }
     358
    312359        var otherItemEdges = GetEdgesInFront(otherItem.Item2, otherItem.Item1);
     360        // right - behind
    313361        foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 0, 1))) {
    314362          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
     363            // As this edge has a vertical direction, every point of intersection won't have an item below.
     364            // So finally it is being projected down.
    315365            var point = ProjectDown(binPacking, ProjectBackward(binPacking, ep));
    316             var residualSpace = CalculateResidualSpace(binPacking, point);
    317             if (!residualSpace.IsZero()) {
    318               eps.Add(point.ToPackingPosition(position.AssignedBin));
     366            var residualSpaces = CalculateResidualSpace(binPacking, point);
     367            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
     368            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
     369              eps.Add(newExtremePoint, residualSpaces);
    319370            }
    320371          }
    321372        }
     373
     374        // on top - behind
    322375        foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 0, 1))) {
    323376          if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
    324377            var point = ProjectBackward(binPacking, ep);
    325             var residualSpace = CalculateResidualSpace(binPacking, point);
    326             if (!residualSpace.IsZero()) {
    327               eps.Add(point.ToPackingPosition(position.AssignedBin));
     378            var residualSpaces = CalculateResidualSpace(binPacking, point);
     379            var newExtremePoint = point.ToPackingPosition(position.AssignedBin);
     380            if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {
     381              eps.Add(newExtremePoint, residualSpaces);
    328382            }
    329383          }
    … …  
    452506
    453507    /// <summary>
    454     ///
     508    /// Returns a collection of points where a given edge (projectedEdge) intersects with other edges.
     509    /// The given edge (projectedEdge) will be projected by using the given vector direction
     510    /// and a edge of the given edge collection.
     511    /// The returned collecten can be empty.
    455512    /// </summary>
    456513    /// <param name="projectedEdge"></param>
    457514    /// <param name="edges"></param>
     515    /// <param name="direction"></param>
    458516    /// <returns></returns>
    459517    private IEnumerable<Vector3D> IntersectionsForItem(Edge3D projectedEdge, Edge3D[] edges, Vector3D direction = null) {
    … …  
    486544    #endregion
    487545
    488    
    489     protected override ResidualSpace CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
    490       return ResidualSpaceCalculatorFactory.CreateCalculator().CalculateResidualSpaces(binPacking, pos).First();
     546    /// <summary>
     547    /// Calculates the residual spaces for an extreme point.
     548    /// </summary>
     549    /// <param name="binPacking"></param>
     550    /// <param name="pos"></param>
     551    /// <returns></returns>
     552    protected override IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
     553      return ResidualSpaceCalculatorFactory.CreateCalculator().CalculateResidualSpaces(binPacking, pos);
    491554    }
    492555  }
    493556
    494  
     557
    495558}

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

    r15520 r15554  
    3131   
    3232    protected override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    33       foreach (var ep in binPacking.ExtremePoints.ToList()) {
    34         var rs = binPacking.ResidualSpaces[ep];
    35         var depth = position.Rotated ? item.Width : item.Depth;
    36         var width = position.Rotated ? item.Depth : item.Width;
    37         var changed = false;
    38         if (ep.Z >= position.Z && ep.Z < position.Z + depth) {
    39           if (ep.X <= position.X && ep.Y >= position.Y && ep.Y < position.Y + item.Height) {
    40             var diff = position.X - ep.X;
    41             var newRSX = Math.Min(rs.Width, diff);
    42             rs = ResidualSpace.Create(newRSX, rs.Height, rs.Depth);
     33      foreach (var extremePoint in binPacking.ExtremePoints.ToList()) {
     34        var ep = extremePoint.Key;
     35        var residualSpaces = extremePoint.Value as IList<ResidualSpace>;
     36        for (int i = 0; i < residualSpaces.Count(); i++) {
     37          var rs = residualSpaces[i];
     38          var depth = position.Rotated ? item.Width : item.Depth;
     39          var width = position.Rotated ? item.Depth : item.Width;
     40          var changed = false;
     41          if (ep.Z >= position.Z && ep.Z < position.Z + depth) {
     42            if (ep.X <= position.X && ep.Y >= position.Y && ep.Y < position.Y + item.Height) {
     43              var diff = position.X - ep.X;
     44              var newRSX = Math.Min(rs.Width, diff);
     45              rs = ResidualSpace.Create(newRSX, rs.Height, rs.Depth);
     46              changed = true;
     47            }
     48            if (ep.Y <= position.Y && ep.X >= position.X && ep.X < position.X + width) {
     49              var diff = position.Y - ep.Y;
     50              var newRSY = Math.Min(rs.Height, diff);
     51              rs = ResidualSpace.Create(rs.Width, newRSY, rs.Depth);
     52              changed = true;
     53            }
     54          }
     55
     56          if (ep.Z <= position.Z &&
     57              ep.Y >= position.Y && ep.Y < position.Y + item.Height &&
     58              ep.X >= position.X && ep.X < position.X + width) {
     59            var diff = position.Z - ep.Z;
     60            var newRSZ = Math.Min(rs.Depth, diff);
     61            rs = ResidualSpace.Create(rs.Width, rs.Height, newRSZ);
    4362            changed = true;
    4463          }
    45           if (ep.Y <= position.Y && ep.X >= position.X && ep.X < position.X + width) {
    46             var diff = position.Y - ep.Y;
    47             var newRSY = Math.Min(rs.Height, diff);
    48             rs = ResidualSpace.Create(rs.Width, newRSY, rs.Depth);
    49             changed = true;
     64
     65          if (changed) {
     66            if (!rs.IsZero() && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) {
     67              residualSpaces[i] = rs;
     68            } else {
     69              binPacking.ExtremePoints.Remove(ep);
     70              break;
     71            }
    5072          }
    51         }
    52 
    53         if (ep.Z <= position.Z &&
    54             ep.Y >= position.Y && ep.Y < position.Y + item.Height &&
    55             ep.X >= position.X && ep.X < position.X + width) {
    56           var diff = position.Z - ep.Z;
    57           var newRSZ = Math.Min(rs.Depth, diff);
    58           rs = ResidualSpace.Create(rs.Width, rs.Height, newRSZ);
    59           changed = true;
    60         }
    61 
    62         if (changed) {
    63           if (!rs.IsZero() && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) {
    64             binPacking.ResidualSpaces[ep] = rs;
    65           } else {
    66             binPacking.ExtremePoints.Remove(ep);
    67             binPacking.ResidualSpaces.Remove(ep);
    68           }
    69         }
     73        }       
    7074      }
    7175      return;
    … …  
    8185    /// <returns></returns>
    8286    protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
    83       if (binPacking.ExtremePoints.Add(position)) {
    84         var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
    85         binPacking.ResidualSpaces.Add(position, rs);
    86         // Check if the existing extreme points are shadowed by the new point
    87         // This is, their residual space fit entirely into the residual space of the new point
    88         foreach (var ep in binPacking.ExtremePoints.Where(x => x != position && new Vector3D(x).IsInside(position, rs)).ToList()) {
    89           if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), binPacking.ResidualSpaces[ep], position, rs)) {
     87      if (binPacking.ExtremePoints.ContainsKey(position)) {
     88        return false;
     89      }
     90
     91      var residualSpaces = CalculateResidualSpace(binPacking, new Vector3D(position));
     92      binPacking.ExtremePoints.Add(position, residualSpaces);
     93      // Check if the existing extreme points are shadowed by the new point
     94      // This is, their residual space fit entirely into the residual space of the new point
     95      foreach (var ep in binPacking.ExtremePoints.Where(x => x.Key != position && new Vector3D(x.Key).IsInside(position, residualSpaces)).ToList()) {
     96        foreach (var residualSpace in ep.Value) {
     97          if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep.Key), residualSpace, position, residualSpaces)) {
    9098            binPacking.ExtremePoints.Remove(ep);
    91             binPacking.ResidualSpaces.Remove(ep);
     99            break;
    92100          }
     101        }         
     102      }
     103      return true;
     104    }
     105
     106    /// <summary>
     107    /// Calculates the residual space for a given bin packing and position.
     108    /// It returns the residual space as a tuple which contains the dimensions
     109    /// </summary>
     110    /// <param name="binPacking"></param>
     111    /// <param name="pos"></param>
     112    /// <returns>A Tuple(width, Height, Depth)</width></returns>
     113    protected override IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
     114      var residualSpaces = new List<ResidualSpace>();
     115      var residualSpace = new ResidualSpace(CalculateResidualSpaceOld(binPacking, pos));
     116      if (!residualSpace.IsZero()) {
     117        residualSpaces.Add(residualSpace);
     118      }
     119      return residualSpaces;
     120    }
     121
     122    protected Tuple<int, int, int> CalculateResidualSpaceOld(BinPacking3D binPacking, Vector3D pos) {
     123
     124      if (pos == null) {
     125        return Tuple.Create(0, 0, 0);
     126      }
     127      var itemPos = binPacking.Items.Select(x => new {
     128        Item = x.Value,
     129        Position = binPacking.Positions[x.Key]
     130      });
     131      Vector3D limit = new Vector3D() {
     132        X = binPacking.BinShape.Width,
     133        Y = binPacking.BinShape.Height,
     134        Z = binPacking.BinShape.Depth
     135      };
     136
     137      if (pos.X < limit.X && pos.Y < limit.Y && pos.Z < limit.Z) {
     138        var rightLimit = ProjectRight(binPacking, pos);
     139        var upLimit = ProjectUp(binPacking, pos);
     140        var forwardLimit = ProjectForward(binPacking, pos);
     141        if (rightLimit.X > 0) {
     142          limit.X = rightLimit.X;
    93143        }
    94         return true;
     144        if (upLimit.Y > 0) {
     145          limit.Y = upLimit.Y;
     146        }
     147        if (forwardLimit.Z > 0) {
     148          limit.Z = forwardLimit.Z;
     149        }
    95150      }
    96       return false;
     151
     152      if (limit.X - pos.X <= 0 || limit.Y - pos.Y <= 0 || limit.Z - pos.Z <= 0) {
     153        return Tuple.Create(0, 0, 0);
     154      }
     155      return Tuple.Create(limit.X - pos.X, limit.Y - pos.Y, limit.Z - pos.Z);
    97156    }
    98157  }

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

    r15520 r15554  
    7070      });
    7171      Vector3D point = l1.Intersect(l2);
    72       if (e1.LiesOn(point) && e2.LiesOn(point)) {
     72      if (point != null && e1.LiesOn(point) && e2.LiesOn(point)) {
    7373        return point;
    7474      }

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

    r15488 r15554  
    99  /// A line is given as a point and a directing vector
    1010  /// </summary>
    11   internal class Line3D {
     11  public class Line3D {
    1212    public Vector3D Point;
    1313    public Vector3D Direction;
    … …  
    3030    }
    3131
     32    /// <summary>
     33    /// Returns the intersection point of two lines.
     34    /// It the lines doesn't intersect it returns null.
     35    /// </summary>
     36    /// <param name="line"></param>
     37    /// <returns></returns>
    3238    public Vector3D Intersect(Line3D line) {
    3339      double r = 0;
    3440      double s = 0;
     41
     42      // if they have the same source point, this point can be returned.
     43      if (this.Point.Equals(line.Point)) {
     44        return this.Point;
     45      }
    3546
    3647      if (Direction.X != 0) {
    … …  
    4960        s = (this.Point.Z - line.Point.Z) / (double)line.Direction.Z;
    5061      }
    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;
     62      var p1 = r * this.Direction + this.Point;
     63      var p2 = s * line.Direction + line.Point;
     64      var c = p1.Equals(p2);
     65      if (s!=0 && r!=0 && p1.Equals(p2)) {       
     66        return p1;
    5867      }
    5968

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

    r15454 r15554  
    66
    77namespace HeuristicLab.Problems.BinPacking3D.Geometry {
    8   internal enum Side { Top, Left, Bottom, Right, Front, Back }
     8  public enum Side { Top, Left, Bottom, Right, Front, Back }
    99
    1010  /// <summary>
    1111  /// A plane is given as a point and two directing vectors
    1212  /// </summary>
    13   internal class Plane3D {
     13  public class Plane3D {
    1414    public Vector3D Point { get; private set; }
    1515    public Vector3D Direction1 { get; private set; }
    1616    public Vector3D Direction2 { get; private set; }
    1717    public Vector3D Normal { get; private set; }
     18
    1819    private int rhs;
    1920
    … …  
    9394    }
    9495
     96    /// <summary>
     97    /// Returns true if the given point is an element of the current plane
     98    /// </summary>
     99    /// <param name="point"></param>
     100    /// <returns></returns>
    95101    public bool IsElementOf(Vector3D point) {
    96102      return Normal.X * point.X + Normal.Y * point.Y + Normal.Z * point.Z == rhs;
    97103    }
    98104
     105    /// <summary>
     106    /// Returns true, if the given line intersects with the current plane
     107    /// </summary>
     108    /// <param name="line"></param>
     109    /// <returns></returns>
    99110    public bool Intersects(Line3D line) {
    100111      return Intersect(line) != null;
    101112    }
    102113
     114    /// <summary>
     115    /// Returns the point of intersection of a given line and the current plane.
     116    /// It returns null if there is no intersection.
     117    /// </summary>
     118    /// <param name="line"></param>
     119    /// <returns></returns>
    103120    public Vector3D Intersect(Line3D line) {
    104121      var denom = Normal * line.Direction;

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

    r15520 r15554  
    1212    public int Z { get; set; }
    1313
    14     public Vector3D() { }
     14    public Vector3D() {
     15      X = 0;
     16      Y = 0;
     17      Z = 0;
     18    }
    1519    public Vector3D(int x, int y, int z) {
    1620      X = x;
    … …  
    8589    }
    8690
     91    public bool IsInside(PackingPosition pos, IEnumerable<ResidualSpace> rs) {
     92      return rs.Any(x => IsInside(pos, x));
     93    }
     94
    8795    public static int operator *(Vector3D a, Vector3D b) {
    8896      return a.X * b.X + a.Y * b.Y + a.Z * b.Z;

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

    r15520 r15554  
    3333
    3434namespace HeuristicLab.Problems.BinPacking3D.Packer {
    35   public abstract class BinPacker : Item {
    36 
    37     /*
    38     [Storable]
    39     IPositionFinder PositionFinder
     35  internal abstract class BinPacker : Item, IBinPacker {
    4036   
    41     */
    42 
    4337    #region Constructors for HEAL
    4438
    … …  
    4943    protected BinPacker(BinPacker original, Cloner cloner)
    5044      : base(original, cloner) {
    51       //this.PositionFinder = original.PositionFinder;
    5245    }
    5346
    … …  
    9992
    10093      // The extremepoints are sortet by Y / Z / X
    101       return packingBin.ExtremePoints.Where(x => packingBin.IsPositionFeasible(newItem, x, useStackingConstraints)).FirstOrDefault();
     94      var newPosition = packingBin.ExtremePoints.Where(x => packingBin.IsPositionFeasible(newItem, x.Key, useStackingConstraints)).FirstOrDefault();
     95     
     96      return newPosition.Key;
    10297    }
    10398

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

    r15471 r15554  
    1717    /// <param name="fittingMethod"></param>
    1818    /// <returns>Returns a new BinPacker depending on the given fitting method</returns>
    19     public static BinPacker CreateBinPacker(FittingMethod fittingMethod) {
    20       BinPacker binPacker = null;
     19    public static IBinPacker CreateBinPacker(FittingMethod fittingMethod) {
     20      IBinPacker binPacker = null;
    2121      switch (fittingMethod) {
    2222        case FittingMethod.FirstFit:

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

    r15488 r15554  
    3232
    3333namespace HeuristicLab.Problems.BinPacking3D.Packer {
    34   public class BinPackerFirstFit : BinPacker {
     34  internal class BinPackerFirstFit : BinPacker {
    3535    #region Constructors for HEAL
    3636    [StorableConstructor]

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

    r15488 r15554  
    3232
    3333namespace HeuristicLab.Problems.BinPacking3D.Packer {
    34   public class BinPackerFreeVolumeBestFit : BinPacker {
     34  internal class BinPackerFreeVolumeBestFit : BinPacker {
    3535   
    3636    #region Constructors for HEAL

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

    r15520 r15554  
    3232
    3333namespace HeuristicLab.Problems.BinPacking3D.Packer {
    34   public class BinPackerResidualSpaceBestFit : BinPacker {
     34  internal class BinPackerResidualSpaceBestFit : BinPacker {
    3535
    3636    #region Constructors for HEAL
    … …  
    5555    /// </summary>
    5656    /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
    57     public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epGenerationMethod, bool useStackingConstraints) {
     57    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, bool useStackingConstraints) {
    5858      IList<BinPacking3D> packingList = new List<BinPacking3D>();
    5959      IList<int> remainingIds = new List<int>(sortedItems);
    60       IExtremePointCreator extremePointCreator = ExtremePointCreatorFactory.CreateExtremePointCreator(epGenerationMethod, useStackingConstraints);
     60      IExtremePointCreator extremePointCreator = ExtremePointCreatorFactory.CreateExtremePointCreator(epCreationMethod, useStackingConstraints);
    6161      bool rotated = false;
    6262
    … …  
    100100      var residualSpacePoints = new List<Tuple<BinPacking3D, PackingPosition, int>>();
    101101      foreach (BinPacking3D bp in packingList) {
    102         foreach (var ep in bp.ExtremePoints) {
    103           var rs = bp.ResidualSpaces[ep];
    104           if (rs.Width < item.Width || rs.Height < item.Height || rs.Depth < item.Depth) {
     102        foreach (var extremPoints in bp.ExtremePoints) {
     103          var ep = extremPoints.Key;
     104          var residualSpaces = extremPoints.Value.Where(rs => rs.Width < item.Width || rs.Height < item.Height || rs.Depth < item.Depth);
     105          if (residualSpaces.Count() <= 0) {
    105106            continue;
    106107          }
    107           residualSpacePoints.Add(Tuple.Create(bp, ep, CalculateResidualMerit(rs, item, ep)));
     108          int merit = residualSpaces.Max(rs => CalculateResidualMerit(rs, item, ep));
     109          residualSpacePoints.Add(Tuple.Create(bp, ep, merit));
    108110        }
    109111      }

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

    r15471 r15554  
    7575      return base.GetHashCode() + 13 * X + 17 * Y + 23 * Z;
    7676    }
    77 
    78     [Obsolete]
    79     public static PackingPosition MoveLeft(PackingPosition original) {
    80       return new PackingPosition(original.AssignedBin, original.X - 1, original.Y, original.Z, original.Rotated);
    81     }
    82     [Obsolete]
    83     public static PackingPosition MoveDown(PackingPosition original) {
    84       return new PackingPosition(original.AssignedBin, original.X, original.Y - 1, original.Z, original.Rotated);
    85     }
    86     [Obsolete]
    87     public static PackingPosition MoveBack(PackingPosition original) {
    88       return new PackingPosition(original.AssignedBin, original.X, original.Y, original.Z - 1, original.Rotated);
    89     }
    90     [Obsolete]
    91     public static PackingPosition MoveRight(PackingPosition original) {
    92       return new PackingPosition(original.AssignedBin, original.X + 1, original.Y, original.Z, original.Rotated);
    93     }
    94     [Obsolete]
    95     public static PackingPosition MoveUp(PackingPosition original) {
    96       return new PackingPosition(original.AssignedBin, original.X, original.Y + 1, original.Z, original.Rotated);
    97     }
    98     [Obsolete]
    99     public static PackingPosition MoveFront(PackingPosition original) {
    100       return new PackingPosition(original.AssignedBin, original.X, original.Y, original.Z + 1, original.Rotated);
    101     }
    102 
     77   
    10378    #region IComparable<PackingPosition> Members
    10479
    … …  
    11590      if (result == 0)
    11691        result = X.CompareTo(other.X);
    117       /*
    118       int result = Z.CompareTo(other.Z);
    119       if (result == 0)
    120         result = X.CompareTo(other.X);
    121       if (result == 0)
    122         result = Y.CompareTo(other.Y);
    123       */
    12492      return result;
    125 
    12693    }
    12794

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

    r15520 r15554  
    1111    /// <summary>
    1212    /// Calculates all available residual spaces for a given point and returns them packed in a collection.
     13    /// The returned collection has zero elements if the residual space is zero
    1314    /// </summary>
    1415    /// <param name="binPacking"></param>

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

    r15520 r15554  
    1010
    1111    internal ResidualSpaceCalculator() {}
    12 
     12   
    1313    public IEnumerable<ResidualSpace> CalculateResidualSpaces(BinPacking3D binPacking, Vector3D point) {
    1414      IList<ResidualSpace> residualSpaces = new List<ResidualSpace>();
    … …  
    1717      var rs3 = CalculateYXZ(binPacking, point);
    1818
    19       residualSpaces.Add(rs1);
    20 
    21 
    22       if (!residualSpaces.Any(rs => rs.Equals(rs2))) {
     19      if (!rs1.IsZero()) {
     20        residualSpaces.Add(rs1);
     21      }     
     22
     23
     24      if (!rs2.IsZero() && !residualSpaces.Any(rs => rs.Equals(rs2))) {
    2325        residualSpaces.Add(rs2);
    2426      }
    25       if (!residualSpaces.Any(rs => rs.Equals(rs3))) {
     27      if (!rs3.IsZero() && !residualSpaces.Any(rs => rs.Equals(rs3))) {
    2628        residualSpaces.Add(rs3);
    2729      }
    … …  
    5658    }
    5759   
     60    /// <summary>
     61    /// Returnst true if a given residual space and item overlaps at the x-axis
     62    /// </summary>
     63    /// <param name="point"></param>
     64    /// <param name="residualSpace"></param>
     65    /// <param name="position"></param>
     66    /// <param name="item"></param>
     67    /// <returns></returns>
    5868    private bool OverlapsX(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
    5969      if (point.X > position.X && point.X >= position.X + item.Width) {
    … …  
    6676      return true;
    6777    }
    68    
     78
     79    /// <summary>
     80    /// Returnst true if a given residual space and item overlaps at the y-axis
     81    /// </summary>
     82    /// <param name="point"></param>
     83    /// <param name="residualSpace"></param>
     84    /// <param name="position"></param>
     85    /// <param name="item"></param>
    6986    private bool OverlapsY(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
    7087      if (point.Y > position.Y && point.Y >= position.Y + item.Height) {
    … …  
    7895    }
    7996
     97    /// <summary>
     98    /// Returnst true if a given residual space and item overlaps at the z-axis
     99    /// </summary>
     100    /// <param name="point"></param>
     101    /// <param name="residualSpace"></param>
     102    /// <param name="position"></param>
     103    /// <param name="item"></param>
    80104    private bool OverlapsZ(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
    81105      if (point.Z > position.Z && point.Z >= position.Z + item.Depth) {
    … …  
    90114
    91115    private bool OverlapsOnRight(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
     116      // if point.x >= position.x, the residual space would be located on the left side!
    92117      if (point.X >= position.X) {
    93118        return false;

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

    r15520 r15554  
    130130    <Compile Include="3D\Encoding\IDecoder.cs" />
    131131    <Compile Include="3D\Evaluators\IEvaluator.cs" />
     132    <Compile Include="3D\Packer\IBinPacker.cs" />
    132133    <Compile Include="3D\ResidualSpace.cs" />
    133134    <Compile Include="3D\ResidualSpaceCalculation\IResidualSpaceCalculator.cs" />
    134135    <Compile Include="3D\ResidualSpaceCalculation\ResidualSpaceCalculator.cs" />
    135136    <Compile Include="3D\ResidualSpaceCalculation\ResidualSpaceCalculatorFactory.cs" />
    136     <Compile Include="3D\Sorting\IOperator.cs" />
     137    <Compile Include="3D\IOperator.cs" />
    137138    <Compile Include="3D\Evaluators\MoveEvaluatorBase.cs" />
    138139    <Compile Include="3D\PackingItem.cs" />

  • branches/2817-BinPackingSpeedup/HeuristicLab.Tests/HeuristicLab.Problems.Bin-Packing-3.3/Utils/TestUtils.cs

    r15463 r15554  
    1313    }
    1414
     15    /// <summary>
     16    /// Invokes a private method of an given object by using reflection
     17    /// </summary>
     18    /// <param name="type"></param>
     19    /// <param name="o"></param>
     20    /// <param name="methodName"></param>
     21    /// <param name="parameters"></param>
     22    /// <returns></returns>
    1523    public static object InvokeMethod(Type type, object o, string methodName, object[] parameters) {
    1624      var method = type.GetMethod(methodName, BindingFlags.NonPublic | BindingFlags.Instance);

  • branches/2817-BinPackingSpeedup/HeuristicLab.Tests/HeuristicLab.Tests.csproj

    r15473 r15554  
    583583    <Compile Include="HeuristicLab.PluginInfraStructure-3.3\InstallationManagerTest.cs" />
    584584    <Compile Include="HeuristicLab.PluginInfraStructure-3.3\TypeExtensionsTest.cs" />
    585     <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\3D\RandomInstanceProviderTest.cs" />
    586     <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\3D\PermutationSortingTest.cs" />
    587     <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\3D\ExtremePointAlgorithmTest.cs" />
    588     <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\3D\ThreeDInstanceParserTest.cs" />
     585    <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\3D\ExtremePointCreation\TestLineProjectionBasedEPCreator.cs" />
     586    <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\3D\Geometry\Edge3DTest.cs" />
     587    <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\3D\Geometry\Line3DTest.cs" />
     588    <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\3D\Geometry\Plane3DTest.cs" />
     589    <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\3D\Geometry\Vector3DTest.cs" />
     590    <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\3D\Instances\RandomInstanceProviderTest.cs" />
     591    <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\3D\Sorting\PermutationSortingTest.cs" />
     592    <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\3D\Algorithms\ExtremePointAlgorithmTest.cs" />
     593    <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\3D\ResidualSpaceCalculation\ResidualSpaceCalculatorTest.cs" />
     594    <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\3D\Instances\ThreeDInstanceParserTest.cs" />
    589595    <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\Utils\TestUtils.cs" />
    590596    <Compile Include="HeuristicLab.Problems.DataAnalysis-3.4\ThresholdCalculatorsTest.cs" />
Note: See TracChangeset for help on using the changeset viewer.