Free cookie consent management tool by TermsFeed Policy Generator

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

#2817:

  • Added line projection based bin packing
  • Added residual spaces to the view
File:
1 edited

Legend:

Unmodified
Added
Removed

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