Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Decoders/2D/EP/ExtremePointsFunctions2D.cs @ 9440

Last change on this file since 9440 was 9440, checked in by jhelm, 11 years ago

#1966: Implemented new encoding (MultiComponentVector/MCV); Implemented move-operators for MCV and GV encodings; Implemented new decoding-methods for PS, GV and MCV encodings (ExtremePoint-based packing);

File size: 16.1 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Text;
5using HeuristicLab.Collections;
6using HeuristicLab.Core;
7using HeuristicLab.Encodings.PackingEncoding.GroupingVector;
8using HeuristicLab.Encodings.PackingEncoding.MultiComponentVector;
9using HeuristicLab.Encodings.PackingEncoding.PackingSequence;
10using HeuristicLab.Problems.BinPacking.Dimensions;
11using HeuristicLab.Problems.BinPacking.Interfaces;
12using HeuristicLab.Problems.BinPacking.PackingBin;
13using HeuristicLab.Problems.BinPacking.PackingItem;
14using HeuristicLab.Problems.BinPacking.Shapes;
15
16namespace HeuristicLab.Problems.BinPacking.Decoders {
17  public static class ExtremPointsFunctions2D {
18
19
20
21
22    public static ObservableDictionary<int, TwoDimensionalPacking> ExtremePointBasedPacking(MultiComponentVectorEncoding solution,
23        ItemList<RectangularPackingItem> itemMeasures, RectangularPackingBin binMeasures) {
24
25      #region Preperations
26      int nrOfBins = solution.PackingInformations.Max(x => x.AssignedBin) + 1;
27
28      //Get all indexes of items for every bin according to grouping-vector                     
29      Dictionary<int, List<PackingInformation>> unpackedItemIndexesPerBin = new Dictionary<int, List<PackingInformation>>();
30      Dictionary<int, HashSet<TwoDimensionalPacking>> extremePointsForBin = new Dictionary<int, HashSet<TwoDimensionalPacking>>();
31      var occupiedPoints = new List<int[,]>();
32
33      for (int i = 0; i < nrOfBins; i++) {       
34        unpackedItemIndexesPerBin[i] = solution.PackingInformations
35          .Where(pi => pi.AssignedBin == i)
36          .ToList();
37
38        extremePointsForBin[i] = new HashSet<TwoDimensionalPacking>();
39        extremePointsForBin[i].Add(new TwoDimensionalPacking(i, 0, 0, false));
40        occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
41      }
42
43      ObservableDictionary<int, TwoDimensionalPacking> itemPositions = new ObservableDictionary<int, TwoDimensionalPacking>();
44      var remainingItems = new List<PackingInformation>();
45
46      #endregion Preperations
47
48
49      //Iterate over all bin-lists
50      for (int binNr = 0; binNr < nrOfBins; binNr++) {
51        //Iterate over the current bin-item-list and find feasible positions in the current bin for each item
52        var unpackedItems = unpackedItemIndexesPerBin[binNr];
53        for (int i = 0; i < unpackedItems.Count; i++) {
54          var itemIndex = unpackedItems[i].ItemIndex;
55          var item = itemMeasures[itemIndex];
56
57          extremePointsForBin[binNr] = new HashSet<TwoDimensionalPacking>(extremePointsForBin[binNr].OrderBy(ep => ep.AssignedBin).ThenBy(ep => ShortestPossibleSideFromEP(ep, occupiedPoints, binMeasures)));
58          var positionFound = FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePointsForBin[binNr], occupiedPoints, itemPositions, unpackedItems[i].Rotated);
59          if (positionFound != null) {
60            extremePointsForBin[binNr].Remove(positionFound);
61            itemPositions[itemIndex] = positionFound;
62            occupiedPoints = OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
63            extremePointsForBin[binNr] = GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, binMeasures);
64          } else
65            remainingItems.Add(unpackedItems[i]);
66        }
67      }
68
69
70      //Packing of remaining items   
71      //Iterate over all bin-lists
72      for (int binNr = 0; binNr < nrOfBins && remainingItems.Count > 0; binNr++) {
73        var unpackedItems = new List<PackingInformation>(remainingItems);
74        //Iterate over all the remaining items
75        for (int i = 0; i < unpackedItems.Count; i++) {
76          var itemIndex = unpackedItems[i].ItemIndex;
77          var item = itemMeasures[itemIndex];
78
79          extremePointsForBin[binNr] = new HashSet<TwoDimensionalPacking>(extremePointsForBin[binNr].OrderBy(ep => ep.AssignedBin).ThenBy(ep => ShortestPossibleSideFromEP(ep, occupiedPoints, binMeasures)));
80          var positionFound = FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePointsForBin[binNr], occupiedPoints, itemPositions, unpackedItems[i].Rotated);
81          if (positionFound != null) {
82            extremePointsForBin[binNr].Remove(positionFound);
83            itemPositions[itemIndex] = positionFound;
84            occupiedPoints = OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
85            extremePointsForBin[binNr] = GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, binMeasures);
86            remainingItems.Remove(unpackedItems[i]);
87          }
88        }
89        if (remainingItems.Count > 0 && binNr + 1 >= nrOfBins) {
90          extremePointsForBin[nrOfBins] = new HashSet<TwoDimensionalPacking>();
91          extremePointsForBin[nrOfBins].Add(new TwoDimensionalPacking(nrOfBins, 0, 0, false));
92          occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
93          nrOfBins++;
94        }
95      }
96
97      return itemPositions;
98    }
99
100
101    public static ObservableDictionary<int, TwoDimensionalPacking> ExtremePointBasedPacking(GroupingVectorEncoding solution,
102        ItemList<RectangularPackingItem> itemMeasures, RectangularPackingBin binMeasures) {
103
104      #region Preperations
105      int nrOfBins = solution.GroupingVector.Max() + 1;
106
107      //Get all indexes of items for every bin according to grouping-vector
108      Dictionary<int, List<int>> unpackedItemIndexesPerBin = new Dictionary<int, List<int>>();   
109      Dictionary<int, HashSet<TwoDimensionalPacking>> extremePointsForBin = new Dictionary<int, HashSet<TwoDimensionalPacking>>();
110      var occupiedPoints = new List<int[,]>();
111
112      for (int i = 0; i < nrOfBins; i++) {
113        unpackedItemIndexesPerBin[i] = solution.GroupingVector
114          .Select((Value, Index) => new { Value, Index })
115          .Where(temp => temp.Value == i)
116          .Select(temp => temp.Index).ToList();
117
118        extremePointsForBin[i] = new HashSet<TwoDimensionalPacking>();
119        extremePointsForBin[i].Add(new TwoDimensionalPacking(i, 0, 0, false));   
120        occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
121      }
122
123      ObservableDictionary<int, TwoDimensionalPacking> itemPositions = new ObservableDictionary<int, TwoDimensionalPacking>();
124      var remainingItems = new List<int>();
125
126      #endregion Preperations
127
128             
129
130      //Iterate over all bin-lists
131      for (int binNr = 0; binNr < nrOfBins; binNr++) {
132        //Iterate over the current bin-item-list and find feasible positions in the current bin for each item
133        var unpackedItems = unpackedItemIndexesPerBin[binNr];
134        for (int i = 0; i < unpackedItems.Count; i++) {
135          var itemIndex = unpackedItems[i];
136          var item = itemMeasures[itemIndex];
137
138          extremePointsForBin[binNr] = new HashSet<TwoDimensionalPacking>(extremePointsForBin[binNr].OrderBy(ep => ep.AssignedBin).ThenBy(ep => ShortestPossibleSideFromEP(ep, occupiedPoints, binMeasures)));
139          var positionFound = FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePointsForBin[binNr], occupiedPoints, itemPositions);
140          if (positionFound != null) {
141            extremePointsForBin[binNr].Remove(positionFound);
142            itemPositions[itemIndex] = positionFound;
143            occupiedPoints = OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
144            extremePointsForBin[binNr] = GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, binMeasures);
145          } else
146            remainingItems.Add(itemIndex);
147        }
148      }
149
150
151
152      //Packing of remaining items   
153      //Iterate over all bin-lists
154      for (int binNr = 0; binNr < nrOfBins && remainingItems.Count > 0; binNr++) {
155        var unpackedItems = new List<int>(remainingItems);
156        //Iterate over all the remaining items
157        for (int i = 0; i < unpackedItems.Count; i++) {
158          var itemIndex = unpackedItems[i];
159          var item = itemMeasures[itemIndex];
160
161          extremePointsForBin[binNr] = new HashSet<TwoDimensionalPacking>(extremePointsForBin[binNr].OrderBy(ep => ep.AssignedBin).ThenBy(ep => ShortestPossibleSideFromEP(ep, occupiedPoints, binMeasures)));
162          var positionFound = FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePointsForBin[binNr], occupiedPoints, itemPositions);
163          if (positionFound != null) {
164            extremePointsForBin[binNr].Remove(positionFound);
165            itemPositions[itemIndex] = positionFound;
166            occupiedPoints = OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
167            extremePointsForBin[binNr] = GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, binMeasures);       
168            remainingItems.Remove(itemIndex);
169          }
170        }
171        if (remainingItems.Count > 0 && binNr + 1 >= nrOfBins) {
172          extremePointsForBin[nrOfBins] = new HashSet<TwoDimensionalPacking>();
173          extremePointsForBin[nrOfBins].Add(new TwoDimensionalPacking(nrOfBins, 0, 0, false));
174          occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
175          nrOfBins++;
176        }
177      }
178
179      return itemPositions;
180    }
181
182
183    public static ObservableDictionary<int, TwoDimensionalPacking> ExtremePointBasedPacking(PackingSequenceEncoding solution,
184        ItemList<RectangularPackingItem> itemMeasures, RectangularPackingBin binMeasures) {
185
186      #region Preperations
187      var itemPositions = new ObservableDictionary<int, TwoDimensionalPacking>(); 
188      int nrOfBins = 1;
189
190      var occupiedPoints = new List<int[,]>();
191      occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
192
193      HashSet<TwoDimensionalPacking> extremePoints = new HashSet<TwoDimensionalPacking>();
194      extremePoints.Add(new TwoDimensionalPacking(0, 0, 0, false));
195      #endregion
196
197      foreach (int itemIndex in solution.PackingSequence) {
198        var item = itemMeasures[itemIndex];
199        extremePoints = new HashSet<TwoDimensionalPacking>(extremePoints.OrderBy(ep => ep.AssignedBin).ThenBy(ep => ShortestPossibleSideFromEP(ep, occupiedPoints, binMeasures)));
200        var positionFound = FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePoints, occupiedPoints, itemPositions);
201        if (positionFound != null) {
202          extremePoints.Remove(positionFound);
203        }
204        else {
205          positionFound = new TwoDimensionalPacking(nrOfBins, 0, 0);
206          occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
207          nrOfBins++;
208        }
209        itemPositions[itemIndex] = positionFound;
210        occupiedPoints = OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
211        extremePoints = GenerateNewExtremePointsForNewItem(extremePoints, occupiedPoints, item, positionFound, binMeasures);
212      }
213
214      return itemPositions;
215    }
216
217
218    private static TwoDimensionalPacking FindExtremePointForItem(int itemIndex, ItemList<RectangularPackingItem> itemMeasures, RectangularPackingBin binMeasures,
219        HashSet<TwoDimensionalPacking> extremePoints, List<int[,]> occupiedPoints, ObservableDictionary<int, TwoDimensionalPacking> itemPositions) {
220          return FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePoints, occupiedPoints, itemPositions, false);
221    }
222    private static TwoDimensionalPacking FindExtremePointForItem(int itemIndex, ItemList<RectangularPackingItem> itemMeasures, RectangularPackingBin binMeasures,
223        HashSet<TwoDimensionalPacking> extremePoints, List<int[,]> occupiedPoints, ObservableDictionary<int, TwoDimensionalPacking> itemPositions, bool rotated) {
224
225      var itemFromList = itemMeasures[itemIndex];
226      RectangularPackingItem item = new RectangularPackingItem(
227        rotated ? itemFromList.Height : itemFromList.Width,
228        rotated ? itemFromList.Width : itemFromList.Height,
229        itemFromList.TargetBin);
230
231      int epIndex = 0;
232      while (epIndex < extremePoints.Count &&
233        (!BottomLeftFunctions.IsPositionFeasible(binMeasures, extremePoints.ElementAt(epIndex).AssignedBin, item, extremePoints.ElementAt(epIndex), itemPositions, itemMeasures)))
234      { epIndex++; }
235
236      if (epIndex < extremePoints.Count) {
237        var result = extremePoints.ElementAt(epIndex);
238        result.Rotated = rotated;
239        return result;
240      }
241      return null;
242    }
243    private static List<int[,]> IncreaseBinCountForOccupiedPoints(List<int[,]> occupiedPoints, RectangularPackingBin binMeasures) {
244      occupiedPoints.Add(new int[binMeasures.Width, binMeasures.Height]);
245      int lastIndex = occupiedPoints.Count - 1;
246      for (int w = 0; w < binMeasures.Width; w++) {
247        for (int h = 0; h < binMeasures.Height; h++) {
248            occupiedPoints[lastIndex][w, h] = -1;
249        }
250      }
251      return occupiedPoints;
252    }
253    private static List<int[,]>  OccupyPointsForNewItem(List<int[,]> occupiedPoints, RectangularPackingItem newItem, TwoDimensionalPacking position, int itemIndex) {
254      int width = position.Rotated ? newItem.Height : newItem.Width;
255      int height = position.Rotated ? newItem.Width : newItem.Height;
256      for (int w = position.X; w < position.X + width; w++) {
257        for (int h = position.Y; h < position.Y + height; h++) {
258            occupiedPoints[position.AssignedBin][w,h] = itemIndex;
259        }
260      }
261      return occupiedPoints;
262    }
263    private static HashSet<TwoDimensionalPacking> GenerateNewExtremePointsForNewItem(HashSet<TwoDimensionalPacking> extremePoints, List<int[,]> occupiedPoints,
264        RectangularPackingItem newItem, TwoDimensionalPacking position, RectangularPackingBin binMeasures) {
265      int currentBin = position.AssignedBin;
266
267      int newWidth = position.Rotated ? newItem.Height : newItem.Width;
268      int newHeight = position.Rotated ? newItem.Width : newItem.Height;
269
270      //Find ExtremePoints beginning from sourcepointX
271      var sourcePointX = new TwoDimensionalPacking(currentBin, position.X + newWidth, position.Y);
272      if (sourcePointX.X < binMeasures.Width && sourcePointX.Y < binMeasures.Height) {
273        //Traversing down the y-axis                                                                           
274        int currentYValue = sourcePointX.Y;
275        while (currentYValue > 0 && occupiedPoints[currentBin][sourcePointX.X, currentYValue] == -1) {
276          currentYValue--;
277        }
278        extremePoints.Add(new TwoDimensionalPacking(currentBin, sourcePointX.X, currentYValue));
279      }
280
281
282
283
284      //Find ExtremePoints beginning from sourcepointY
285      var sourcePointY = new TwoDimensionalPacking(currentBin, position.X, position.Y + newItem.Height);
286      if (sourcePointY.X < binMeasures.Width && sourcePointY.Y < binMeasures.Height) {
287        //Traversing down the x-axis 
288        int currentXValue = sourcePointY.X;
289        while (currentXValue > 0 && occupiedPoints[currentBin][currentXValue - 1, sourcePointY.Y] == -1) {
290          currentXValue--;
291        }
292        extremePoints.Add(new TwoDimensionalPacking(currentBin, currentXValue, sourcePointY.Y));
293      }
294
295
296      return extremePoints;
297    }
298    private static int ShortestPossibleSideFromEP(TwoDimensionalPacking ep, List<int[,]> occupiedPoints, RectangularPackingBin binMeasures) {
299      int shortestSide = int.MaxValue;
300
301      if (ep.X >= binMeasures.Width || ep.Y >= binMeasures.Height)
302        return shortestSide;
303
304      int currentX = ep.X;
305      while (currentX < binMeasures.Width && occupiedPoints[ep.AssignedBin][currentX, ep.Y] == -1) { currentX++; }   
306      if (currentX - ep.X < shortestSide)
307        shortestSide = currentX - ep.X;
308
309      int currentY = ep.Y;
310      while (currentY < binMeasures.Height && occupiedPoints[ep.AssignedBin][ep.X, currentY] == -1) { currentY++;  }
311      if (currentY - ep.Y < shortestSide)
312        shortestSide = currentY - ep.Y;
313
314      return shortestSide;
315    }
316  }
317}
Note: See TracBrowser for help on using the repository browser.