1 /** @file GuillotineBinPack.cpp
2 @author Jukka Jyl�nki
3
4 @brief Implements different bin packer algorithms that use the GUILLOTINE data structure.
5
6 This work is released to Public Domain, do whatever you want with it.
7 */
8
9 #include <cassert>
10 #include <limits.h>
11 #include "templates.h"
12 #include "GuillotineBinPack.h"
13
14 using namespace std;
15
GuillotineBinPack()16 GuillotineBinPack::GuillotineBinPack()
17 :binWidth(0),
18 binHeight(0)
19 {
20 }
21
GuillotineBinPack(int width,int height)22 GuillotineBinPack::GuillotineBinPack(int width, int height)
23 {
24 Init(width, height);
25 }
26
Init(int width,int height)27 void GuillotineBinPack::Init(int width, int height)
28 {
29 binWidth = width;
30 binHeight = height;
31
32 #ifdef _DEBUG
33 disjointRects.Clear();
34 #endif
35
36 // Clear any memory of previously packed rectangles.
37 usedRectangles.Clear();
38
39 // We start with a single big free rectangle that spans the whole bin.
40 Rect n;
41 n.x = 0;
42 n.y = 0;
43 n.width = width;
44 n.height = height;
45
46 freeRectangles.Clear();
47 freeRectangles.Push(n);
48 }
49
Insert(TArray<RectSize> & rects,TArray<Rect> & dst,bool merge,FreeRectChoiceHeuristic rectChoice,GuillotineSplitHeuristic splitMethod)50 void GuillotineBinPack::Insert(TArray<RectSize> &rects, TArray<Rect> &dst, bool merge,
51 FreeRectChoiceHeuristic rectChoice, GuillotineSplitHeuristic splitMethod)
52 {
53 dst.Clear();
54
55 // Remember variables about the best packing choice we have made so far during the iteration process.
56 int bestFreeRect = 0;
57 int bestRect = 0;
58 bool bestFlipped = false;
59
60 // Pack rectangles one at a time until we have cleared the rects array of all rectangles.
61 // rects will get destroyed in the process.
62 while(rects.Size() > 0)
63 {
64 // Stores the penalty score of the best rectangle placement - bigger=worse, smaller=better.
65 int bestScore = INT_MAX;
66
67 for(unsigned i = 0; i < freeRectangles.Size(); ++i)
68 {
69 for(unsigned j = 0; j < rects.Size(); ++j)
70 {
71 // If this rectangle is a perfect match, we pick it instantly.
72 if (rects[j].width == freeRectangles[i].width && rects[j].height == freeRectangles[i].height)
73 {
74 bestFreeRect = i;
75 bestRect = j;
76 bestFlipped = false;
77 bestScore = INT_MIN;
78 i = freeRectangles.Size(); // Force a jump out of the outer loop as well - we got an instant fit.
79 break;
80 }
81 // If flipping this rectangle is a perfect match, pick that then.
82 else if (rects[j].height == freeRectangles[i].width && rects[j].width == freeRectangles[i].height)
83 {
84 bestFreeRect = i;
85 bestRect = j;
86 bestFlipped = true;
87 bestScore = INT_MIN;
88 i = freeRectangles.Size(); // Force a jump out of the outer loop as well - we got an instant fit.
89 break;
90 }
91 // Try if we can fit the rectangle upright.
92 else if (rects[j].width <= freeRectangles[i].width && rects[j].height <= freeRectangles[i].height)
93 {
94 int score = ScoreByHeuristic(rects[j].width, rects[j].height, freeRectangles[i], rectChoice);
95 if (score < bestScore)
96 {
97 bestFreeRect = i;
98 bestRect = j;
99 bestFlipped = false;
100 bestScore = score;
101 }
102 }
103 // If not, then perhaps flipping sideways will make it fit?
104 else if (rects[j].height <= freeRectangles[i].width && rects[j].width <= freeRectangles[i].height)
105 {
106 int score = ScoreByHeuristic(rects[j].height, rects[j].width, freeRectangles[i], rectChoice);
107 if (score < bestScore)
108 {
109 bestFreeRect = i;
110 bestRect = j;
111 bestFlipped = true;
112 bestScore = score;
113 }
114 }
115 }
116 }
117
118 // If we didn't manage to find any rectangle to pack, abort.
119 if (bestScore == INT_MAX)
120 return;
121
122 // Otherwise, we're good to go and do the actual packing.
123 Rect newNode;
124 newNode.x = freeRectangles[bestFreeRect].x;
125 newNode.y = freeRectangles[bestFreeRect].y;
126 newNode.width = rects[bestRect].width;
127 newNode.height = rects[bestRect].height;
128
129 if (bestFlipped)
130 std::swap(newNode.width, newNode.height);
131
132 // Remove the free space we lost in the bin.
133 SplitFreeRectByHeuristic(freeRectangles[bestFreeRect], newNode, splitMethod);
134 freeRectangles.Delete(bestFreeRect);
135
136 // Remove the rectangle we just packed from the input list.
137 rects.Delete(bestRect);
138
139 // Perform a Rectangle Merge step if desired.
140 if (merge)
141 MergeFreeList();
142
143 // Remember the new used rectangle.
144 usedRectangles.Push(newNode);
145
146 // Check that we're really producing correct packings here.
147 #ifdef _DEBUG
148 assert(disjointRects.Add(newNode) == true);
149 #endif
150 }
151 }
152
153 /// @return True if r fits inside freeRect (possibly rotated).
Fits(const RectSize & r,const Rect & freeRect)154 bool Fits(const RectSize &r, const Rect &freeRect)
155 {
156 return (r.width <= freeRect.width && r.height <= freeRect.height) ||
157 (r.height <= freeRect.width && r.width <= freeRect.height);
158 }
159
160 /// @return True if r fits perfectly inside freeRect, i.e. the leftover area is 0.
FitsPerfectly(const RectSize & r,const Rect & freeRect)161 bool FitsPerfectly(const RectSize &r, const Rect &freeRect)
162 {
163 return (r.width == freeRect.width && r.height == freeRect.height) ||
164 (r.height == freeRect.width && r.width == freeRect.height);
165 }
166
167 /*
168 // A helper function for GUILLOTINE-MAXFITTING. Counts how many rectangles fit into the given rectangle
169 // after it has been split.
170 void CountNumFitting(const Rect &freeRect, int width, int height, const TArray<RectSize> &rects,
171 int usedRectIndex, bool splitHorizontal, int &score1, int &score2)
172 {
173 const int w = freeRect.width - width;
174 const int h = freeRect.height - height;
175
176 Rect bottom;
177 bottom.x = freeRect.x;
178 bottom.y = freeRect.y + height;
179 bottom.height = h;
180
181 Rect right;
182 right.x = freeRect.x + width;
183 right.y = freeRect.y;
184 right.width = w;
185
186 if (splitHorizontal)
187 {
188 bottom.width = freeRect.width;
189 right.height = height;
190 }
191 else // Split vertically
192 {
193 bottom.width = width;
194 right.height = freeRect.height;
195 }
196
197 int fitBottom = 0;
198 int fitRight = 0;
199 for(size_t i = 0; i < rects.size(); ++i)
200 if (i != usedRectIndex)
201 {
202 if (FitsPerfectly(rects[i], bottom))
203 fitBottom |= 0x10000000;
204 if (FitsPerfectly(rects[i], right))
205 fitRight |= 0x10000000;
206
207 if (Fits(rects[i], bottom))
208 ++fitBottom;
209 if (Fits(rects[i], right))
210 ++fitRight;
211 }
212
213 score1 = min(fitBottom, fitRight);
214 score2 = max(fitBottom, fitRight);
215 }
216 */
217 /*
218 // Implements GUILLOTINE-MAXFITTING, an experimental heuristic that's really cool but didn't quite work in practice.
219 void GuillotineBinPack::InsertMaxFitting(TArray<RectSize> &rects, TArray<Rect> &dst, bool merge,
220 FreeRectChoiceHeuristic rectChoice, GuillotineSplitHeuristic splitMethod)
221 {
222 dst.clear();
223 int bestRect = 0;
224 bool bestFlipped = false;
225 bool bestSplitHorizontal = false;
226
227 // Pick rectangles one at a time and pack the one that leaves the most choices still open.
228 while(rects.size() > 0 && freeRectangles.size() > 0)
229 {
230 int bestScore1 = -1;
231 int bestScore2 = -1;
232
233 ///\todo Different sort predicates.
234 clb::sort::QuickSort(&freeRectangles[0], freeRectangles.size(), CompareRectShortSide);
235
236 Rect &freeRect = freeRectangles[0];
237
238 for(size_t j = 0; j < rects.size(); ++j)
239 {
240 int score1;
241 int score2;
242
243 if (rects[j].width == freeRect.width && rects[j].height == freeRect.height)
244 {
245 bestRect = j;
246 bestFlipped = false;
247 bestScore1 = bestScore2 = std::numeric_limits<int>::max();
248 break;
249 }
250 else if (rects[j].width <= freeRect.width && rects[j].height <= freeRect.height)
251 {
252 CountNumFitting(freeRect, rects[j].width, rects[j].height, rects, j, false, score1, score2);
253
254 if (score1 > bestScore1 || (score1 == bestScore1 && score2 > bestScore2))
255 {
256 bestRect = j;
257 bestScore1 = score1;
258 bestScore2 = score2;
259 bestFlipped = false;
260 bestSplitHorizontal = false;
261 }
262
263 CountNumFitting(freeRect, rects[j].width, rects[j].height, rects, j, true, score1, score2);
264
265 if (score1 > bestScore1 || (score1 == bestScore1 && score2 > bestScore2))
266 {
267 bestRect = j;
268 bestScore1 = score1;
269 bestScore2 = score2;
270 bestFlipped = false;
271 bestSplitHorizontal = true;
272 }
273 }
274
275 if (rects[j].height == freeRect.width && rects[j].width == freeRect.height)
276 {
277 bestRect = j;
278 bestFlipped = true;
279 bestScore1 = bestScore2 = std::numeric_limits<int>::max();
280 break;
281 }
282 else if (rects[j].height <= freeRect.width && rects[j].width <= freeRect.height)
283 {
284 CountNumFitting(freeRect, rects[j].height, rects[j].width, rects, j, false, score1, score2);
285
286 if (score1 > bestScore1 || (score1 == bestScore1 && score2 > bestScore2))
287 {
288 bestRect = j;
289 bestScore1 = score1;
290 bestScore2 = score2;
291 bestFlipped = true;
292 bestSplitHorizontal = false;
293 }
294
295 CountNumFitting(freeRect, rects[j].height, rects[j].width, rects, j, true, score1, score2);
296
297 if (score1 > bestScore1 || (score1 == bestScore1 && score2 > bestScore2))
298 {
299 bestRect = j;
300 bestScore1 = score1;
301 bestScore2 = score2;
302 bestFlipped = true;
303 bestSplitHorizontal = true;
304 }
305 }
306 }
307
308 if (bestScore1 >= 0)
309 {
310 Rect newNode;
311 newNode.x = freeRect.x;
312 newNode.y = freeRect.y;
313 newNode.width = rects[bestRect].width;
314 newNode.height = rects[bestRect].height;
315 if (bestFlipped)
316 std::swap(newNode.width, newNode.height);
317
318 assert(disjointRects.Disjoint(newNode));
319 SplitFreeRectAlongAxis(freeRect, newNode, bestSplitHorizontal);
320
321 rects.erase(rects.begin() + bestRect);
322
323 if (merge)
324 MergeFreeList();
325
326 usedRectangles.push_back(newNode);
327 #ifdef _DEBUG
328 disjointRects.Add(newNode);
329 #endif
330 }
331
332 freeRectangles.erase(freeRectangles.begin());
333 }
334 }
335 */
336
Insert(int width,int height,bool merge,FreeRectChoiceHeuristic rectChoice,GuillotineSplitHeuristic splitMethod)337 Rect GuillotineBinPack::Insert(int width, int height, bool merge, FreeRectChoiceHeuristic rectChoice,
338 GuillotineSplitHeuristic splitMethod)
339 {
340 // Find where to put the new rectangle.
341 int freeNodeIndex = 0;
342 Rect newRect = FindPositionForNewNode(width, height, rectChoice, &freeNodeIndex);
343
344 // Abort if we didn't have enough space in the bin.
345 if (newRect.height == 0)
346 return newRect;
347
348 // Remove the space that was just consumed by the new rectangle.
349 SplitFreeRectByHeuristic(freeRectangles[freeNodeIndex], newRect, splitMethod);
350 freeRectangles.Delete(freeNodeIndex);
351
352 // Perform a Rectangle Merge step if desired.
353 if (merge)
354 MergeFreeList();
355
356 // Remember the new used rectangle.
357 usedRectangles.Push(newRect);
358
359 // Check that we're really producing correct packings here.
360 #ifdef _DEBUG
361 assert(disjointRects.Add(newRect) == true);
362 #endif
363 return newRect;
364 }
365
366 /// Computes the ratio of used surface area to the total bin area.
Occupancy() const367 float GuillotineBinPack::Occupancy() const
368 {
369 ///\todo The occupancy rate could be cached/tracked incrementally instead
370 /// of looping through the list of packed rectangles here.
371 unsigned long usedSurfaceArea = 0;
372 for(unsigned i = 0; i < usedRectangles.Size(); ++i)
373 usedSurfaceArea += usedRectangles[i].width * usedRectangles[i].height;
374
375 return (float)usedSurfaceArea / (binWidth * binHeight);
376 }
377
378 /// Returns the heuristic score value for placing a rectangle of size width*height into freeRect. Does not try to rotate.
ScoreByHeuristic(int width,int height,const Rect & freeRect,FreeRectChoiceHeuristic rectChoice)379 int GuillotineBinPack::ScoreByHeuristic(int width, int height, const Rect &freeRect, FreeRectChoiceHeuristic rectChoice)
380 {
381 switch(rectChoice)
382 {
383 case RectBestAreaFit: return ScoreBestAreaFit(width, height, freeRect);
384 case RectBestShortSideFit: return ScoreBestShortSideFit(width, height, freeRect);
385 case RectBestLongSideFit: return ScoreBestLongSideFit(width, height, freeRect);
386 case RectWorstAreaFit: return ScoreWorstAreaFit(width, height, freeRect);
387 case RectWorstShortSideFit: return ScoreWorstShortSideFit(width, height, freeRect);
388 case RectWorstLongSideFit: return ScoreWorstLongSideFit(width, height, freeRect);
389 default: assert(false); return INT_MAX;
390 }
391 }
392
ScoreBestAreaFit(int width,int height,const Rect & freeRect)393 int GuillotineBinPack::ScoreBestAreaFit(int width, int height, const Rect &freeRect)
394 {
395 return freeRect.width * freeRect.height - width * height;
396 }
397
ScoreBestShortSideFit(int width,int height,const Rect & freeRect)398 int GuillotineBinPack::ScoreBestShortSideFit(int width, int height, const Rect &freeRect)
399 {
400 int leftoverHoriz = abs(freeRect.width - width);
401 int leftoverVert = abs(freeRect.height - height);
402 int leftover = MIN(leftoverHoriz, leftoverVert);
403 return leftover;
404 }
405
ScoreBestLongSideFit(int width,int height,const Rect & freeRect)406 int GuillotineBinPack::ScoreBestLongSideFit(int width, int height, const Rect &freeRect)
407 {
408 int leftoverHoriz = abs(freeRect.width - width);
409 int leftoverVert = abs(freeRect.height - height);
410 int leftover = MAX(leftoverHoriz, leftoverVert);
411 return leftover;
412 }
413
ScoreWorstAreaFit(int width,int height,const Rect & freeRect)414 int GuillotineBinPack::ScoreWorstAreaFit(int width, int height, const Rect &freeRect)
415 {
416 return -ScoreBestAreaFit(width, height, freeRect);
417 }
418
ScoreWorstShortSideFit(int width,int height,const Rect & freeRect)419 int GuillotineBinPack::ScoreWorstShortSideFit(int width, int height, const Rect &freeRect)
420 {
421 return -ScoreBestShortSideFit(width, height, freeRect);
422 }
423
ScoreWorstLongSideFit(int width,int height,const Rect & freeRect)424 int GuillotineBinPack::ScoreWorstLongSideFit(int width, int height, const Rect &freeRect)
425 {
426 return -ScoreBestLongSideFit(width, height, freeRect);
427 }
428
FindPositionForNewNode(int width,int height,FreeRectChoiceHeuristic rectChoice,int * nodeIndex)429 Rect GuillotineBinPack::FindPositionForNewNode(int width, int height, FreeRectChoiceHeuristic rectChoice, int *nodeIndex)
430 {
431 Rect bestNode;
432 memset(&bestNode, 0, sizeof(Rect));
433
434 int bestScore = INT_MAX;
435
436 /// Try each free rectangle to find the best one for placement.
437 for(unsigned i = 0; i < freeRectangles.Size(); ++i)
438 {
439 // If this is a perfect fit upright, choose it immediately.
440 if (width == freeRectangles[i].width && height == freeRectangles[i].height)
441 {
442 bestNode.x = freeRectangles[i].x;
443 bestNode.y = freeRectangles[i].y;
444 bestNode.width = width;
445 bestNode.height = height;
446 bestScore = INT_MIN;
447 *nodeIndex = i;
448 #ifdef _DEBUG
449 assert(disjointRects.Disjoint(bestNode));
450 #endif
451 break;
452 }
453 // If this is a perfect fit sideways, choose it.
454 /* else if (height == freeRectangles[i].width && width == freeRectangles[i].height)
455 {
456 bestNode.x = freeRectangles[i].x;
457 bestNode.y = freeRectangles[i].y;
458 bestNode.width = height;
459 bestNode.height = width;
460 bestScore = INT_MIN;
461 *nodeIndex = i;
462 assert(disjointRects.Disjoint(bestNode));
463 break;
464 }
465 */ // Does the rectangle fit upright?
466 else if (width <= freeRectangles[i].width && height <= freeRectangles[i].height)
467 {
468 int score = ScoreByHeuristic(width, height, freeRectangles[i], rectChoice);
469
470 if (score < bestScore)
471 {
472 bestNode.x = freeRectangles[i].x;
473 bestNode.y = freeRectangles[i].y;
474 bestNode.width = width;
475 bestNode.height = height;
476 bestScore = score;
477 *nodeIndex = i;
478 #ifdef _DEBUG
479 assert(disjointRects.Disjoint(bestNode));
480 #endif
481 }
482 }
483 // Does the rectangle fit sideways?
484 /* else if (height <= freeRectangles[i].width && width <= freeRectangles[i].height)
485 {
486 int score = ScoreByHeuristic(height, width, freeRectangles[i], rectChoice);
487
488 if (score < bestScore)
489 {
490 bestNode.x = freeRectangles[i].x;
491 bestNode.y = freeRectangles[i].y;
492 bestNode.width = height;
493 bestNode.height = width;
494 bestScore = score;
495 *nodeIndex = i;
496 assert(disjointRects.Disjoint(bestNode));
497 }
498 }
499 */ }
500 return bestNode;
501 }
502
SplitFreeRectByHeuristic(const Rect & freeRect,const Rect & placedRect,GuillotineSplitHeuristic method)503 void GuillotineBinPack::SplitFreeRectByHeuristic(const Rect &freeRect, const Rect &placedRect, GuillotineSplitHeuristic method)
504 {
505 // Compute the lengths of the leftover area.
506 const int w = freeRect.width - placedRect.width;
507 const int h = freeRect.height - placedRect.height;
508
509 // Placing placedRect into freeRect results in an L-shaped free area, which must be split into
510 // two disjoint rectangles. This can be achieved with by splitting the L-shape using a single line.
511 // We have two choices: horizontal or vertical.
512
513 // Use the given heuristic to decide which choice to make.
514
515 bool splitHorizontal;
516 switch(method)
517 {
518 case SplitShorterLeftoverAxis:
519 // Split along the shorter leftover axis.
520 splitHorizontal = (w <= h);
521 break;
522 case SplitLongerLeftoverAxis:
523 // Split along the longer leftover axis.
524 splitHorizontal = (w > h);
525 break;
526 case SplitMinimizeArea:
527 // Maximize the larger area == minimize the smaller area.
528 // Tries to make the single bigger rectangle.
529 splitHorizontal = (placedRect.width * h > w * placedRect.height);
530 break;
531 case SplitMaximizeArea:
532 // Maximize the smaller area == minimize the larger area.
533 // Tries to make the rectangles more even-sized.
534 splitHorizontal = (placedRect.width * h <= w * placedRect.height);
535 break;
536 case SplitShorterAxis:
537 // Split along the shorter total axis.
538 splitHorizontal = (freeRect.width <= freeRect.height);
539 break;
540 case SplitLongerAxis:
541 // Split along the longer total axis.
542 splitHorizontal = (freeRect.width > freeRect.height);
543 break;
544 default:
545 splitHorizontal = true;
546 assert(false);
547 }
548
549 // Perform the actual split.
550 SplitFreeRectAlongAxis(freeRect, placedRect, splitHorizontal);
551 }
552
553 /// This function will add the two generated rectangles into the freeRectangles array. The caller is expected to
554 /// remove the original rectangle from the freeRectangles array after that.
SplitFreeRectAlongAxis(const Rect & freeRect,const Rect & placedRect,bool splitHorizontal)555 void GuillotineBinPack::SplitFreeRectAlongAxis(const Rect &freeRect, const Rect &placedRect, bool splitHorizontal)
556 {
557 // Form the two new rectangles.
558 Rect bottom;
559 bottom.x = freeRect.x;
560 bottom.y = freeRect.y + placedRect.height;
561 bottom.height = freeRect.height - placedRect.height;
562
563 Rect right;
564 right.x = freeRect.x + placedRect.width;
565 right.y = freeRect.y;
566 right.width = freeRect.width - placedRect.width;
567
568 if (splitHorizontal)
569 {
570 bottom.width = freeRect.width;
571 right.height = placedRect.height;
572 }
573 else // Split vertically
574 {
575 bottom.width = placedRect.width;
576 right.height = freeRect.height;
577 }
578
579 // Add the new rectangles into the free rectangle pool if they weren't degenerate.
580 if (bottom.width > 0 && bottom.height > 0)
581 freeRectangles.Push(bottom);
582 if (right.width > 0 && right.height > 0)
583 freeRectangles.Push(right);
584
585 #ifdef _DEBUG
586 assert(disjointRects.Disjoint(bottom));
587 assert(disjointRects.Disjoint(right));
588 #endif
589 }
590
MergeFreeList()591 void GuillotineBinPack::MergeFreeList()
592 {
593 #ifdef _DEBUG
594 DisjointRectCollection test;
595 for(unsigned i = 0; i < freeRectangles.Size(); ++i)
596 assert(test.Add(freeRectangles[i]) == true);
597 #endif
598
599 // Do a Theta(n^2) loop to see if any pair of free rectangles could me merged into one.
600 // Note that we miss any opportunities to merge three rectangles into one. (should call this function again to detect that)
601 for(unsigned i = 0; i < freeRectangles.Size(); ++i)
602 for(unsigned j = i+1; j < freeRectangles.Size(); ++j)
603 {
604 if (freeRectangles[i].width == freeRectangles[j].width && freeRectangles[i].x == freeRectangles[j].x)
605 {
606 if (freeRectangles[i].y == freeRectangles[j].y + freeRectangles[j].height)
607 {
608 freeRectangles[i].y -= freeRectangles[j].height;
609 freeRectangles[i].height += freeRectangles[j].height;
610 freeRectangles.Delete(j);
611 --j;
612 }
613 else if (freeRectangles[i].y + freeRectangles[i].height == freeRectangles[j].y)
614 {
615 freeRectangles[i].height += freeRectangles[j].height;
616 freeRectangles.Delete(j);
617 --j;
618 }
619 }
620 else if (freeRectangles[i].height == freeRectangles[j].height && freeRectangles[i].y == freeRectangles[j].y)
621 {
622 if (freeRectangles[i].x == freeRectangles[j].x + freeRectangles[j].width)
623 {
624 freeRectangles[i].x -= freeRectangles[j].width;
625 freeRectangles[i].width += freeRectangles[j].width;
626 freeRectangles.Delete(j);
627 --j;
628 }
629 else if (freeRectangles[i].x + freeRectangles[i].width == freeRectangles[j].x)
630 {
631 freeRectangles[i].width += freeRectangles[j].width;
632 freeRectangles.Delete(j);
633 --j;
634 }
635 }
636 }
637
638 #ifdef _DEBUG
639 test.Clear();
640 for(unsigned i = 0; i < freeRectangles.Size(); ++i)
641 assert(test.Add(freeRectangles[i]) == true);
642 #endif
643 }
644