Free cookie consent management tool by TermsFeed Policy Generator

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

#2817:

  • Unittests
  • Bugfixes on the line projection based extreme point creation method
File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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
Note: See TracChangeset for help on using the changeset viewer.