Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
11/08/17 16:30:41 (7 years ago)
Author:
rhanghof
Message:

#2817
-Added unit tests for bin packing 3d.
-The items can now be sorted by the material.

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r15454 r15462  
    6767    #region New methods for bin packer class
    6868
    69     public void AddItem(int itemID, PackingItem item, PackingPosition position) {
     69    public override void PackItem(int itemID, PackingItem item, PackingPosition position) {
    7070      Items[itemID] = item;
    7171      Positions[itemID] = position;
    … …  
    7474    }
    7575
     76    /// <summary>
     77    /// Updates the extreme points of the bin
     78    /// </summary>
     79    /// <param name="item"></param>
     80    /// <param name="position"></param>
     81    /// <param name="stackingConstraints"></param>
    7682    public void UpdateExtremePoints(PackingItem item, PackingPosition position, bool stackingConstraints) {
    77       /*if (stackingConstraints) {
    78         AddExtremePoint(new PackingPosition(position.AssignedBin, position.X + item.Width, position.Y, position.Z));
    79         AddExtremePoint(new PackingPosition(position.AssignedBin, position.X, position.Y + item.Height, position.Z));
    80         AddExtremePoint(new PackingPosition(position.AssignedBin, position.X, position.Y, position.Z + item.Depth));
    81       } else {*/
     83      if (stackingConstraints) {
     84        UpdateExtremePointsWithStackingConstriants(item, position);
     85      } else {
     86        UpdateExtremePointsWithoutStackingConstriants(item, position);
     87      }
     88    }
     89
     90    /// <summary>
     91    /// Updates the extreme points of the bin.
     92    /// As there is no need to project the extreme points to the next side of an item, the extreme points are only generated for the current item.
     93    /// </summary>
     94    /// <param name="item"></param>
     95    /// <param name="position"></param>
     96    private void UpdateExtremePointsWithStackingConstriants(PackingItem newItem, PackingPosition position) {
     97
     98      //UpdateExtremePointsWithoutStackingConstriants(newItem, position);
     99      //return;
     100
     101      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
     102      int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
     103      var ep1 = new PackingPosition(position.AssignedBin, position.X + newWidth, position.Y, position.Z);
     104      var ep2 = new PackingPosition(position.AssignedBin, position.X, position.Y + newItem.Height, position.Z);
     105      var ep3 = new PackingPosition(position.AssignedBin, position.X, position.Y, position.Z + newDepth);
     106      AddExtremePoint(ep1);
     107      AddExtremePoint(ep2);
     108      AddExtremePoint(ep3);
     109
     110      /*
     111      ExtremePoints.Add(ep1);
     112      ExtremePoints.Add(ep2);
     113      ExtremePoints.Add(ep3);
     114
     115      var rs1 = CalculateResidualSpace(CreateRs(ep1));
     116      var rs2 = CalculateResidualSpace(CreateRs(ep2));
     117      var rs3 = CalculateResidualSpace(CreateRs(ep3));
     118      ResidualSpace.Add(ep1, rs1);
     119      ResidualSpace.Add(ep2, rs2);
     120      ResidualSpace.Add(ep3, rs3);*/
     121    }
     122
     123
     124    /*private bool AddExtremePoint(PackingPosition position) {
     125      if ()
     126
     127      return true;
     128    }
     129
     130   
     131    private bool AddExtremePoint(PackingPosition pos) {
     132      if (ExtremePoints.Add(pos)) {
     133        var rs = CalculateResidualSpace(new Vector3D(pos));
     134        ResidualSpace.Add(pos, rs);
     135        // Check if existing extreme points are shadowed by the new point
     136        // That is, their residual space fit entirely into the residual space of the new point
     137        foreach (var ep in ExtremePoints.Where(x => x != pos && new Vector3D(x).IsInside(pos, rs)).ToList()) {
     138          if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), ResidualSpace[ep], pos, rs)) {
     139            ExtremePoints.Remove(ep);
     140            ResidualSpace.Remove(ep);
     141          }
     142        }
     143        return true;
     144      }
     145      return false;
     146    }*/
     147
     148
     149    private Tuple<int, int, int> CalculateResidualSpace(Vector3D pos) {
     150      var itemPos = Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] });
     151      Vector3D limit = new Vector3D() { X = BinShape.Width, Y = BinShape.Height, Z = BinShape.Depth };
     152      if (pos.X < limit.X && pos.Y < limit.Y && pos.Z < limit.Z) {
     153        var rightLimit = ProjectRight(pos);
     154        var upLimit = ProjectUp(pos);
     155        var forwardLimit = ProjectForward(pos);
     156        if (rightLimit.X > 0) {
     157          limit.X = rightLimit.X;
     158        }
     159        if (upLimit.Y > 0) {
     160          limit.Y = upLimit.Y;
     161        }
     162        if (forwardLimit.Z > 0) {
     163          limit.Z = forwardLimit.Z;
     164        }
     165      }
     166
     167     
     168     
     169      if (limit.X - pos.X <= 0 || limit.Y - pos.Y <= 0  || limit.Z - pos.Z <= 0) {
     170        return Tuple.Create(0, 0, 0);
     171      }
     172
     173
     174      return Tuple.Create(limit.X - pos.X, limit.Y - pos.Y, limit.Z - pos.Z);
     175    }
     176
     177
     178    private Vector3D CreateRs(PackingPosition position) {
     179      return new Vector3D() { X = position.X, Y = position.Y, Z = position.Z };
     180    }
     181
     182    private void UpdateExtremePointsWithoutStackingConstriants(PackingItem item, PackingPosition position) {
    82183      GenerateNewExtremePointsForNewItem(item, position);
    83184
    … …  
    92193        GenerateNewExtremePointsForNewItem(right.Item2, right.Item1);
    93194      }
    94       //}
    95195    }
    96196
    … …  
    147247        }
    148248      }
    149       return true;     
     249      return true;
    150250    }
    151251
    … …  
    156256    /// <param name="t2"></param>
    157257    /// <returns></returns>
    158     bool ItemsCollides(Tuple<PackingPosition, PackingItem> t1, Tuple<PackingPosition, PackingItem> t2) {
     258    private bool ItemsCollides(Tuple<PackingPosition, PackingItem> t1, Tuple<PackingPosition, PackingItem> t2) {
    159259      var position1 = t1.Item1;
    160260      var item1 = t1.Item2;
    … …  
    189289    /// <param name="position"></param>
    190290    /// <returns></returns>
    191     public bool HasOnePointWithAnItemBelow(PackingItem item, PackingPosition position) {
     291    private bool HasOnePointWithAnItemBelow(PackingItem item, PackingPosition position) {
    192292      bool p1, p2, p3, p4;
    193       PointsLiesOnAnItems(item, position, out p1, out p2, out p3, out p4);
     293      PointsLiesOnAnItem(item, position, out p1, out p2, out p3, out p4);
    194294
    195295      return p1 || p2 || p3 || p4;
    … …  
    205305    public override bool IsStaticStable(PackingItem item, PackingPosition position) {
    206306      bool p1, p2, p3, p4;
    207       PointsLiesOnAnItems(item, position, out p1, out p2, out p3, out p4);
     307      PointsLiesOnAnItem(item, position, out p1, out p2, out p3, out p4);
    208308      return p1 && p2 && p3 && p4;
    209309    }
    210310
    211311    /// <summary>
    212     /// This method sets the out parameters p1 ... p3 if the point lies on another item.
     312    /// This method sets the out parameters p1 ... p4 if the point lies on another item.
    213313    /// p1 ... p3 represents one point on the bottom side of an given item.
    214314    /// +---------+
    … …  
    224324    /// <param name="p3"></param>
    225325    /// <param name="p4"></param>
    226     public void PointsLiesOnAnItems(PackingItem item, PackingPosition position, out bool p1, out bool p2, out bool p3, out bool p4) {
     326    private void PointsLiesOnAnItem(PackingItem item, PackingPosition position, out bool p1, out bool p2, out bool p3, out bool p4) {
    227327      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1;
    228328      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2;
    … …  
    240340
    241341    /// <summary>
    242     ///
     342    /// This method returns a collection for the out parameters itemsP1 ... itemsP4 with the items below
     343    /// itemsP1 ... itemsP4 represents one point on the bottom side of an given item.
     344    /// +---------+
     345    /// |p1     p2|
     346    /// |         |
     347    /// |p4     p3|
     348    /// +---------+
    243349    /// </summary>
    244350    /// <param name="item"></param>
    … …  
    277383    /// <param name="position"></param>
    278384    /// <returns></returns>
    279     public bool IsWeightSupported(PackingItem item, PackingPosition position) {
     385    private bool IsWeightSupported(PackingItem item, PackingPosition position) {
    280386      if (position.Y == 0) {
    281387        return true;
    … …  
    298404    #endregion
    299405
    300     public override void PackItem(int itemID, PackingItem item, PackingPosition position) {
    301       // base call is deliberately omitted, because UpdateResidualSpace needs to be fitted in before
    302       // generating new extreme points
    303       Items[itemID] = item;
    304       Positions[itemID] = position;
    305       ExtremePoints.Remove(position);
    306       ResidualSpace.Remove(position);
    307       UpdateResidualSpace(item, position);
    308       GenerateNewExtremePointsForNewItem(item, position);
    309       // if an item is fit in below, before, or left of another its extreme points have to be regenerated
    310       foreach (var above in GetItemsAbove(position))
    311         GenerateNewExtremePointsForNewItem(above.Item2, above.Item1);
    312       foreach (var front in GetItemsInfront(position))
    313         GenerateNewExtremePointsForNewItem(front.Item2, front.Item1);
    314       foreach (var right in GetItemsOnRight(position))
    315         GenerateNewExtremePointsForNewItem(right.Item2, right.Item1);
    316       AddNewItemToOccupationLayers(itemID, item, position);
    317     }
    318 
    319 
    320 
     406    /// <summary>
     407    /// Generates new extreme points for a given item and its position.
     408    /// It also recalcualtes the residual space and removes the extreme points which are not needed any more.
     409    /// </summary>
     410    /// <param name="newItem"></param>
     411    /// <param name="position"></param>
    321412    protected override void GenerateNewExtremePointsForNewItem(PackingItem newItem, PackingPosition position) {
    322413      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
    … …  
    404495    }
    405496
    406 
    407497    private bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> residualSpace) {
    408498      var eps = ExtremePoints.Where(x => !pos.Equals(x) && pos.IsInside(x, ResidualSpace[x]));
    … …  
    432522    }
    433523
    434     private Tuple<int, int, int> CalculateResidualSpace(Vector3D pos) {
     524    private Tuple<int, int, int> CalculateResidualSpace1(Vector3D pos) {
    435525      var itemPos = Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] });
    436526      var rightLimit = ProjectRight(pos);
    … …  
    505595    #region Get items
    506596
    507     /// <summary>
    508     ///
    509     /// </summary>
    510     /// <param name="pos"></param>
    511     /// <returns></returns>
    512597    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsAbove(PackingPosition pos) {
    513598      var line = new Line3D(pos, new Vector3D(0, 1, 0));
    … …  
    573658
    574659
    575 
     660    #region Sliding based packing  and obsolet methods
    576661    public override PackingPosition FindExtremePointForItem(PackingItem item, bool rotated, bool stackingConstraints) {
     662      throw new NotSupportedException();
    577663      PackingItem newItem = new PackingItem(
    578664        rotated ? item.Depth : item.Width,
    … …  
    590676    }
    591677
    592  
    593 
    594     #region Sliding based packing   
     678
     679
     680
    595681    public override PackingPosition FindPositionBySliding(PackingItem item, bool rotated, bool stackingConstraints) {
    596       //Starting-position at upper right corner (=left bottom point of item-rectangle is at position item.width,item.height)
    597       PackingPosition currentPosition = new PackingPosition(0,
    598         BinShape.Width - (rotated ? item.Depth : item.Width),
    599         BinShape.Height - item.Height,
    600         BinShape.Depth - (rotated ? item.Width : item.Depth), rotated);
    601       //Slide the item as far as possible to the bottom
    602       while (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition), stackingConstraints)
    603         || IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints)
    604         || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) {
    605         //Slide the item as far as possible to the left
    606         while (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints)
    607       || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) {
    608           //Slide the item as far as possible to the back
    609           while (IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) {
    610             currentPosition = PackingPosition.MoveBack(currentPosition);
    611           }
    612           if (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints))
    613             currentPosition = PackingPosition.MoveLeft(currentPosition);
    614         }
    615         if (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition), stackingConstraints))
    616           currentPosition = PackingPosition.MoveDown(currentPosition);
    617       }
    618 
    619       return IsPositionFeasible(item, currentPosition, stackingConstraints) ? currentPosition : null;
     682      throw new NotSupportedException();
    620683    }
    621684
    622685    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
    623       var temp = new List<int>(sequence);
    624       for (int i = 0; i < temp.Count; i++) {
    625         var item = items[temp[i]];
    626         var position = FindPositionBySliding(item, false, stackingConstraints);
    627         if (position != null) {
    628           PackItem(temp[i], item, position);
    629           sequence.Remove(temp[i]);
    630         }
    631       }
     686      throw new NotSupportedException();
    632687    }
    633688    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, Dictionary<int, bool> rotationArray, bool stackingConstraints) {
    634       var temp = new List<int>(sequence);
    635       for (int i = 0; i < temp.Count; i++) {
    636         var item = items[temp[i]];
    637         var position = FindPositionBySliding(item, rotationArray[i], stackingConstraints);
    638         if (position != null) {
    639           PackItem(temp[i], item, position);
    640           sequence.Remove(temp[i]);
    641         }
    642       }
     689      throw new NotSupportedException();
     690    }
     691
     692
     693    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
     694      throw new NotSupportedException();
     695    }
     696
     697    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray) {
     698      throw new NotSupportedException();
     699    }
     700
     701    public override int ShortestPossibleSideFromPoint(PackingPosition position) {
     702      throw new NotSupportedException();
     703    }
     704
     705
     706    protected override void InitializeOccupationLayers() {
     707    }
     708    protected override void AddNewItemToOccupationLayers(int itemID, PackingItem item, PackingPosition position) {
     709    }
     710
     711
     712    protected override List<int> GetLayerItemIDs(PackingPosition position) {
     713      return null;
     714    }
     715    protected override List<int> GetLayerItemIDs(PackingItem item, PackingPosition position) {
     716      return null;
    643717    }
    644718    #endregion
    645     public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
    646       var temp = new List<int>(sequence);
    647       foreach (int itemID in temp) {
    648         var item = items[itemID];
    649         var positionFound = FindExtremePointForItem(item, false, stackingConstraints);
    650         if (positionFound != null) {
    651           PackItem(itemID, item, positionFound);
    652           sequence.Remove(itemID);
    653         }
    654       }
    655     }
    656     public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray) {
    657       var temp = new List<int>(sequence);
    658       foreach (int itemID in temp) {
    659         var item = items[itemID];
    660         var positionFound = FindExtremePointForItem(item, rotationArray[itemID], stackingConstraints);
    661         if (positionFound != null) {
    662           PackItem(itemID, item, positionFound);
    663           sequence.Remove(itemID);
    664         }
    665       }
    666     }
    667     public override int ShortestPossibleSideFromPoint(PackingPosition position) {
    668 
    669       int shortestSide = int.MaxValue;
    670       int width = BinShape.Width;
    671       int height = BinShape.Height;
    672       int depth = BinShape.Depth;
    673 
    674       if (position.X >= width || position.Y >= height || position.Z >= depth)
    675         return shortestSide;
    676 
    677       PackingPosition current = new PackingPosition(0, position.X, position.Y, position.Z);
    678       while (current.X < width && IsPointOccupied(current)) { current = PackingPosition.MoveRight(current); }
    679       if (current.X - position.X < shortestSide)
    680         shortestSide = current.X - position.X;
    681 
    682 
    683       current = new PackingPosition(0, position.X, position.Y, position.Z);
    684       while (current.Y < height && IsPointOccupied(current)) { current = PackingPosition.MoveUp(current); }
    685       if (current.Y - position.Y < shortestSide)
    686         shortestSide = current.Y - position.Y;
    687 
    688 
    689       current = new PackingPosition(0, position.X, position.Y, position.Z);
    690       while (current.Z < depth && IsPointOccupied(current)) { current = PackingPosition.MoveFront(current); }
    691       if (current.Z - position.Z < shortestSide)
    692         shortestSide = current.Z - position.Z;
    693 
    694       return shortestSide;
    695     }
    696    
    697 
    698     protected override void InitializeOccupationLayers() {
    699       for (int i = 0; i * 10 <= BinShape.Depth; i += 1) {
    700         OccupationLayers[i] = new List<int>();
    701       }
    702     }
    703     protected override void AddNewItemToOccupationLayers(int itemID, PackingItem item, PackingPosition position) {
    704       int z1 = position.Z / 10;
    705       int z2 = (position.Z + (position.Rotated ? item.Width : item.Depth)) / 10;
    706 
    707       for (int i = z1; i <= z2; i++)
    708         OccupationLayers[i].Add(itemID);
    709     }
    710     protected override List<int> GetLayerItemIDs(PackingPosition position) {
    711       return OccupationLayers[position.Z / 10];
    712     }
    713     protected override List<int> GetLayerItemIDs(PackingItem item, PackingPosition position) {
    714       List<int> result = new List<int>();
    715       int z1 = position.Z / 10;
    716       int z2 = (position.Z + (position.Rotated ? item.Width : item.Depth)) / 10;
    717 
    718       for (int i = z1; i <= z2; i++)
    719         result.AddRange(OccupationLayers[i]);
    720       return result;
    721     }
     719
    722720
    723721    public void UpdateResidualSpace(PackingItem item, PackingPosition pos) {
    … …  
    762760      return;
    763761    }
    764 
    765 
    766762  }
    767763}
Note: See TracChangeset for help on using the changeset viewer.