Commits

Lars Viklund committed b77c1bc

Import newest clb bin packing

Comments (0)

Files changed (13)

CLB/CMakeLists.txt

 cmake_minimum_required(VERSION 2.8)
 
-add_library(CLBRectBinPack STATIC src/RectangleBinPack.cpp src/RectangleBinPack.h)
+add_library(CLBRectBinPack STATIC
+		src/GuillotineBinPack.cpp
+		src/GuillotineBinPack.h
+		src/MaxRectsBinPack.cpp
+		src/MaxRectsBinPack.h
+		src/Rect.cpp
+		src/Rect.h
+		src/ShelfBinPack.cpp
+		src/ShelfBinPack.h
+		src/SkylineBinPack.cpp
+		src/SkylineBinPack.h
+		)

CLB/src/GuillotineBinPack.cpp

+/** @file GuillotineBinPack.cpp
+	@author Jukka Jylänki
+
+	@brief Implements different bin packer algorithms that use the GUILLOTINE data structure.
+
+	This work is released to Public Domain, do whatever you want with it.
+*/
+#include <utility>
+#include <iostream>
+
+#include <cassert>
+#include <cmath>
+#include <cstring>
+#include <limits>
+
+#include "GuillotineBinPack.h"
+
+using namespace std;
+
+GuillotineBinPack::GuillotineBinPack()
+:binWidth(0),
+binHeight(0)
+{
+}
+
+GuillotineBinPack::GuillotineBinPack(int width, int height)
+{
+	Init(width, height);
+}
+
+void GuillotineBinPack::Init(int width, int height)
+{
+	binWidth = width;
+	binHeight = height;
+
+#ifdef _DEBUG
+	disjointRects.Clear();
+#endif
+
+	// Clear any memory of previously packed rectangles.
+	usedRectangles.clear();
+
+	// We start with a single big free rectangle that spans the whole bin.
+	Rect n;
+	n.x = 0;
+	n.y = 0;
+	n.width = width;
+	n.height = height;
+
+	freeRectangles.clear();
+	freeRectangles.push_back(n);
+}
+
+void GuillotineBinPack::Insert(std::vector<RectSize> &rects, std::vector<Rect> &dst, bool merge, 
+	FreeRectChoiceHeuristic rectChoice, GuillotineSplitHeuristic splitMethod)
+{
+	dst.clear();
+
+	// Remember variables about the best packing choice we have made so far during the iteration process.
+	int bestFreeRect = 0;
+	int bestRect = 0;
+	bool bestFlipped = false;
+
+	// Pack rectangles one at a time until we have cleared the rects array of all rectangles.
+	// rects will get destroyed in the process.
+	while(rects.size() > 0)
+	{
+		// Stores the penalty score of the best rectangle placement - bigger=worse, smaller=better.
+		int bestScore = std::numeric_limits<int>::max();
+
+		for(size_t i = 0; i < freeRectangles.size(); ++i)
+		{
+			for(size_t j = 0; j < rects.size(); ++j)
+			{
+				// If this rectangle is a perfect match, we pick it instantly.
+				if (rects[j].width == freeRectangles[i].width && rects[j].height == freeRectangles[i].height)
+				{
+					bestFreeRect = i;
+					bestRect = j;
+					bestFlipped = false;
+					bestScore = std::numeric_limits<int>::min();
+					i = freeRectangles.size(); // Force a jump out of the outer loop as well - we got an instant fit.
+					break;
+				}
+				// If flipping this rectangle is a perfect match, pick that then.
+				else if (rects[j].height == freeRectangles[i].width && rects[j].width == freeRectangles[i].height)
+				{
+					bestFreeRect = i;
+					bestRect = j;
+					bestFlipped = true;
+					bestScore = std::numeric_limits<int>::min();
+					i = freeRectangles.size(); // Force a jump out of the outer loop as well - we got an instant fit.
+					break;
+				}
+				// Try if we can fit the rectangle upright.
+				else if (rects[j].width <= freeRectangles[i].width && rects[j].height <= freeRectangles[i].height)
+				{
+					int score = ScoreByHeuristic(rects[j].width, rects[j].height, freeRectangles[i], rectChoice);
+					if (score < bestScore)
+					{
+						bestFreeRect = i;
+						bestRect = j;
+						bestFlipped = false;
+						bestScore = score;
+					}
+				}
+				// If not, then perhaps flipping sideways will make it fit?
+				else if (rects[j].height <= freeRectangles[i].width && rects[j].width <= freeRectangles[i].height)
+				{
+					int score = ScoreByHeuristic(rects[j].height, rects[j].width, freeRectangles[i], rectChoice);
+					if (score < bestScore)
+					{
+						bestFreeRect = i;
+						bestRect = j;
+						bestFlipped = true;
+						bestScore = score;
+					}
+				}
+			}
+		}
+
+		// If we didn't manage to find any rectangle to pack, abort.
+		if (bestScore == std::numeric_limits<int>::max())
+			return;
+
+		// Otherwise, we're good to go and do the actual packing.
+		Rect newNode;
+		newNode.x = freeRectangles[bestFreeRect].x;
+		newNode.y = freeRectangles[bestFreeRect].y;
+		newNode.width = rects[bestRect].width;
+		newNode.height = rects[bestRect].height;
+
+		if (bestFlipped)
+			std::swap(newNode.width, newNode.height);
+
+		// Remove the free space we lost in the bin.
+		SplitFreeRectByHeuristic(freeRectangles[bestFreeRect], newNode, splitMethod);
+		freeRectangles.erase(freeRectangles.begin() + bestFreeRect);
+
+		// Remove the rectangle we just packed from the input list.
+		rects.erase(rects.begin() + bestRect);
+
+		// Perform a Rectangle Merge step if desired.
+		if (merge)
+			MergeFreeList();
+
+		// Remember the new used rectangle.
+		usedRectangles.push_back(newNode);
+
+#ifdef _DEBUG
+		// Check that we're really producing correct packings here.
+		assert(disjointRects.Add(newNode) == true);
+#endif
+	}
+}
+
+/// @return True if r fits inside freeRect (possibly rotated).
+bool Fits(const RectSize &r, const Rect &freeRect)
+{
+	return (r.width <= freeRect.width && r.height <= freeRect.height) ||
+		(r.height <= freeRect.width && r.width <= freeRect.height);
+}
+
+/// @return True if r fits perfectly inside freeRect, i.e. the leftover area is 0.
+bool FitsPerfectly(const RectSize &r, const Rect &freeRect)
+{
+	return (r.width == freeRect.width && r.height == freeRect.height) ||
+		(r.height == freeRect.width && r.width == freeRect.height);
+}
+
+/*
+// A helper function for GUILLOTINE-MAXFITTING. Counts how many rectangles fit into the given rectangle
+// after it has been split.
+void CountNumFitting(const Rect &freeRect, int width, int height, const std::vector<RectSize> &rects, 
+	int usedRectIndex, bool splitHorizontal, int &score1, int &score2)
+{
+	const int w = freeRect.width - width;
+	const int h = freeRect.height - height;
+
+	Rect bottom;
+	bottom.x = freeRect.x;
+	bottom.y = freeRect.y + height;
+	bottom.height = h;
+
+	Rect right;
+	right.x = freeRect.x + width;
+	right.y = freeRect.y;
+	right.width = w;
+
+	if (splitHorizontal)
+	{
+		bottom.width = freeRect.width;
+		right.height = height;
+	}
+	else // Split vertically
+	{
+		bottom.width = width;
+		right.height = freeRect.height;
+	}
+
+	int fitBottom = 0;
+	int fitRight = 0;
+	for(size_t i = 0; i < rects.size(); ++i)
+		if (i != usedRectIndex)
+		{
+			if (FitsPerfectly(rects[i], bottom))
+				fitBottom |= 0x10000000;
+			if (FitsPerfectly(rects[i], right))
+				fitRight |= 0x10000000;
+
+			if (Fits(rects[i], bottom))
+				++fitBottom;
+			if (Fits(rects[i], right))
+				++fitRight;
+		}
+
+	score1 = min(fitBottom, fitRight);
+	score2 = max(fitBottom, fitRight);
+}
+*/
+/*
+// Implements GUILLOTINE-MAXFITTING, an experimental heuristic that's really cool but didn't quite work in practice.
+void GuillotineBinPack::InsertMaxFitting(std::vector<RectSize> &rects, std::vector<Rect> &dst, bool merge, 
+	FreeRectChoiceHeuristic rectChoice, GuillotineSplitHeuristic splitMethod)
+{
+	dst.clear();
+	int bestRect = 0;
+	bool bestFlipped = false;
+	bool bestSplitHorizontal = false;
+
+	// Pick rectangles one at a time and pack the one that leaves the most choices still open.
+	while(rects.size() > 0 && freeRectangles.size() > 0)
+	{
+		int bestScore1 = -1;
+		int bestScore2 = -1;
+
+		///\todo Different sort predicates.
+		clb::sort::QuickSort(&freeRectangles[0], freeRectangles.size(), CompareRectShortSide);
+
+		Rect &freeRect = freeRectangles[0];
+
+		for(size_t j = 0; j < rects.size(); ++j)
+		{
+			int score1;
+			int score2;
+
+			if (rects[j].width == freeRect.width && rects[j].height == freeRect.height)
+			{
+				bestRect = j;
+				bestFlipped = false;
+				bestScore1 = bestScore2 = std::numeric_limits<int>::max();
+				break;
+			}
+			else if (rects[j].width <= freeRect.width && rects[j].height <= freeRect.height)
+			{
+				CountNumFitting(freeRect, rects[j].width, rects[j].height, rects, j, false, score1, score2);
+
+				if (score1 > bestScore1 || (score1 == bestScore1 && score2 > bestScore2))
+				{
+					bestRect = j;
+					bestScore1 = score1;
+					bestScore2 = score2;
+					bestFlipped = false;
+					bestSplitHorizontal = false;
+				}
+
+				CountNumFitting(freeRect, rects[j].width, rects[j].height, rects, j, true, score1, score2);
+
+				if (score1 > bestScore1 || (score1 == bestScore1 && score2 > bestScore2))
+				{
+					bestRect = j;
+					bestScore1 = score1;
+					bestScore2 = score2;
+					bestFlipped = false;
+					bestSplitHorizontal = true;
+				}
+			}
+
+			if (rects[j].height == freeRect.width && rects[j].width == freeRect.height)
+			{
+				bestRect = j;
+				bestFlipped = true;
+				bestScore1 = bestScore2 = std::numeric_limits<int>::max();
+				break;
+			}
+			else if (rects[j].height <= freeRect.width && rects[j].width <= freeRect.height)
+			{
+				CountNumFitting(freeRect, rects[j].height, rects[j].width, rects, j, false, score1, score2);
+
+				if (score1 > bestScore1 || (score1 == bestScore1 && score2 > bestScore2))
+				{
+					bestRect = j;
+					bestScore1 = score1;
+					bestScore2 = score2;
+					bestFlipped = true;
+					bestSplitHorizontal = false;
+				}
+
+				CountNumFitting(freeRect, rects[j].height, rects[j].width, rects, j, true, score1, score2);
+
+				if (score1 > bestScore1 || (score1 == bestScore1 && score2 > bestScore2))
+				{
+					bestRect = j;
+					bestScore1 = score1;
+					bestScore2 = score2;
+					bestFlipped = true;
+					bestSplitHorizontal = true;
+				}
+			}
+		}
+
+		if (bestScore1 >= 0)
+		{
+			Rect newNode;
+			newNode.x = freeRect.x;
+			newNode.y = freeRect.y;
+			newNode.width = rects[bestRect].width;
+			newNode.height = rects[bestRect].height;
+			if (bestFlipped)
+				std::swap(newNode.width, newNode.height);
+
+			assert(disjointRects.Disjoint(newNode));
+			SplitFreeRectAlongAxis(freeRect, newNode, bestSplitHorizontal);
+
+			rects.erase(rects.begin() + bestRect);
+
+			if (merge)
+				MergeFreeList();
+
+			usedRectangles.push_back(newNode);
+#ifdef _DEBUG
+			disjointRects.Add(newNode);
+#endif
+		}
+
+		freeRectangles.erase(freeRectangles.begin());
+	}
+}
+*/
+
+Rect GuillotineBinPack::Insert(int width, int height, bool merge, FreeRectChoiceHeuristic rectChoice, 
+	GuillotineSplitHeuristic splitMethod)
+{
+	// Find where to put the new rectangle.
+	int freeNodeIndex = 0;
+	Rect newRect = FindPositionForNewNode(width, height, rectChoice, &freeNodeIndex);
+
+	// Abort if we didn't have enough space in the bin.
+	if (newRect.height == 0)
+		return newRect;
+
+	// Remove the space that was just consumed by the new rectangle.
+	SplitFreeRectByHeuristic(freeRectangles[freeNodeIndex], newRect, splitMethod);
+	freeRectangles.erase(freeRectangles.begin() + freeNodeIndex);
+
+	// Perform a Rectangle Merge step if desired.
+	if (merge)
+		MergeFreeList();
+
+	// Remember the new used rectangle.
+	usedRectangles.push_back(newRect);
+
+#ifdef _DEBUG
+	// Check that we're really producing correct packings here.
+	assert(disjointRects.Add(newRect) == true);
+#endif
+
+	return newRect;
+}
+
+/// Computes the ratio of used surface area to the total bin area.
+float GuillotineBinPack::Occupancy() const
+{
+	///\todo The occupancy rate could be cached/tracked incrementally instead
+	///      of looping through the list of packed rectangles here.
+	unsigned long usedSurfaceArea = 0;
+	for(size_t i = 0; i < usedRectangles.size(); ++i)
+		usedSurfaceArea += usedRectangles[i].width * usedRectangles[i].height;
+
+	return (float)usedSurfaceArea / (binWidth * binHeight);
+}
+
+/// Returns the heuristic score value for placing a rectangle of size width*height into freeRect. Does not try to rotate.
+int GuillotineBinPack::ScoreByHeuristic(int width, int height, const Rect &freeRect, FreeRectChoiceHeuristic rectChoice)
+{
+	switch(rectChoice)
+	{
+	case RectBestAreaFit: return ScoreBestAreaFit(width, height, freeRect);
+	case RectBestShortSideFit: return ScoreBestShortSideFit(width, height, freeRect);
+	case RectBestLongSideFit: return ScoreBestLongSideFit(width, height, freeRect);
+	case RectWorstAreaFit: return ScoreWorstAreaFit(width, height, freeRect);
+	case RectWorstShortSideFit: return ScoreWorstShortSideFit(width, height, freeRect);
+	case RectWorstLongSideFit: return ScoreWorstLongSideFit(width, height, freeRect);
+	default: assert(false); return std::numeric_limits<int>::max();
+	}
+}
+
+int GuillotineBinPack::ScoreBestAreaFit(int width, int height, const Rect &freeRect)
+{
+	return freeRect.width * freeRect.height - width * height;
+}
+
+int GuillotineBinPack::ScoreBestShortSideFit(int width, int height, const Rect &freeRect)
+{
+	int leftoverHoriz = abs(freeRect.width - width);
+	int leftoverVert = abs(freeRect.height - height);
+	int leftover = min(leftoverHoriz, leftoverVert);
+	return leftover;
+}
+
+int GuillotineBinPack::ScoreBestLongSideFit(int width, int height, const Rect &freeRect)
+{
+	int leftoverHoriz = abs(freeRect.width - width);
+	int leftoverVert = abs(freeRect.height - height);
+	int leftover = max(leftoverHoriz, leftoverVert);
+	return leftover;
+}
+
+int GuillotineBinPack::ScoreWorstAreaFit(int width, int height, const Rect &freeRect)
+{
+	return -ScoreBestAreaFit(width, height, freeRect);
+}
+
+int GuillotineBinPack::ScoreWorstShortSideFit(int width, int height, const Rect &freeRect)
+{
+	return -ScoreBestShortSideFit(width, height, freeRect);
+}
+
+int GuillotineBinPack::ScoreWorstLongSideFit(int width, int height, const Rect &freeRect)
+{
+	return -ScoreBestLongSideFit(width, height, freeRect);
+}
+
+Rect GuillotineBinPack::FindPositionForNewNode(int width, int height, FreeRectChoiceHeuristic rectChoice, int *nodeIndex)
+{
+	Rect bestNode;
+	memset(&bestNode, 0, sizeof(Rect));
+
+	int bestScore = std::numeric_limits<int>::max();
+
+	/// Try each free rectangle to find the best one for placement.
+	for(size_t i = 0; i < freeRectangles.size(); ++i)
+	{
+		// If this is a perfect fit upright, choose it immediately.
+		if (width == freeRectangles[i].width && height == freeRectangles[i].height)
+		{
+			bestNode.x = freeRectangles[i].x;
+			bestNode.y = freeRectangles[i].y;
+			bestNode.width = width;
+			bestNode.height = height;
+			bestScore = std::numeric_limits<int>::min();
+			*nodeIndex = i;
+#ifdef _DEBUG
+			assert(disjointRects.Disjoint(bestNode));
+#endif
+			break;
+		}
+		// If this is a perfect fit sideways, choose it.
+		else if (height == freeRectangles[i].width && width == freeRectangles[i].height)
+		{
+			bestNode.x = freeRectangles[i].x;
+			bestNode.y = freeRectangles[i].y;
+			bestNode.width = height;
+			bestNode.height = width;
+			bestScore = std::numeric_limits<int>::min();
+			*nodeIndex = i;
+#ifdef _DEBUG
+			assert(disjointRects.Disjoint(bestNode));
+#endif
+			break;
+		}
+		// Does the rectangle fit upright?
+		else if (width <= freeRectangles[i].width && height <= freeRectangles[i].height)
+		{
+			int score = ScoreByHeuristic(width, height, freeRectangles[i], rectChoice);
+
+			if (score < bestScore)
+			{
+				bestNode.x = freeRectangles[i].x;
+				bestNode.y = freeRectangles[i].y;
+				bestNode.width = width;
+				bestNode.height = height;
+				bestScore = score;
+				*nodeIndex = i;
+#ifdef _DEBUG
+				assert(disjointRects.Disjoint(bestNode));
+#endif
+			}
+		}
+		// Does the rectangle fit sideways?
+		else if (height <= freeRectangles[i].width && width <= freeRectangles[i].height)
+		{
+			int score = ScoreByHeuristic(height, width, freeRectangles[i], rectChoice);
+
+			if (score < bestScore)
+			{
+				bestNode.x = freeRectangles[i].x;
+				bestNode.y = freeRectangles[i].y;
+				bestNode.width = height;
+				bestNode.height = width;
+				bestScore = score;
+				*nodeIndex = i;
+#ifdef _DEBUG
+				assert(disjointRects.Disjoint(bestNode));
+#endif
+			}
+		}
+	}
+	return bestNode;
+}
+
+void GuillotineBinPack::SplitFreeRectByHeuristic(const Rect &freeRect, const Rect &placedRect, GuillotineSplitHeuristic method)
+{
+	// Compute the lengths of the leftover area.
+	const int w = freeRect.width - placedRect.width;
+	const int h = freeRect.height - placedRect.height;
+
+	// Placing placedRect into freeRect results in an L-shaped free area, which must be split into
+	// two disjoint rectangles. This can be achieved with by splitting the L-shape using a single line.
+	// We have two choices: horizontal or vertical.	
+
+	// Use the given heuristic to decide which choice to make.
+
+	bool splitHorizontal;
+	switch(method)
+	{
+	case SplitShorterLeftoverAxis:
+		// Split along the shorter leftover axis.
+		splitHorizontal = (w <= h);
+		break;
+	case SplitLongerLeftoverAxis:
+		// Split along the longer leftover axis.
+		splitHorizontal = (w > h);
+		break;
+	case SplitMinimizeArea:
+		// Maximize the larger area == minimize the smaller area.
+		// Tries to make the single bigger rectangle.
+		splitHorizontal = (placedRect.width * h > w * placedRect.height);
+		break;
+	case SplitMaximizeArea:
+		// Maximize the smaller area == minimize the larger area.
+		// Tries to make the rectangles more even-sized.
+		splitHorizontal = (placedRect.width * h <= w * placedRect.height);
+		break;
+	case SplitShorterAxis:
+		// Split along the shorter total axis.
+		splitHorizontal = (freeRect.width <= freeRect.height);
+		break;
+	case SplitLongerAxis:
+		// Split along the longer total axis.
+		splitHorizontal = (freeRect.width > freeRect.height);
+		break;
+	default:
+		splitHorizontal = true;
+		assert(false);
+	}
+
+	// Perform the actual split.
+	SplitFreeRectAlongAxis(freeRect, placedRect, splitHorizontal);
+}
+
+/// This function will add the two generated rectangles into the freeRectangles array. The caller is expected to
+/// remove the original rectangle from the freeRectangles array after that.
+void GuillotineBinPack::SplitFreeRectAlongAxis(const Rect &freeRect, const Rect &placedRect, bool splitHorizontal)
+{
+	// Form the two new rectangles.
+	Rect bottom;
+	bottom.x = freeRect.x;
+	bottom.y = freeRect.y + placedRect.height;
+	bottom.height = freeRect.height - placedRect.height;
+
+	Rect right;
+	right.x = freeRect.x + placedRect.width;
+	right.y = freeRect.y;
+	right.width = freeRect.width - placedRect.width;
+
+	if (splitHorizontal)
+	{
+		bottom.width = freeRect.width;
+		right.height = placedRect.height;
+	}
+	else // Split vertically
+	{
+		bottom.width = placedRect.width;
+		right.height = freeRect.height;
+	}
+
+	// Add the new rectangles into the free rectangle pool if they weren't degenerate.
+	if (bottom.width > 0 && bottom.height > 0)
+		freeRectangles.push_back(bottom);
+	if (right.width > 0 && right.height > 0)
+		freeRectangles.push_back(right);
+
+#ifdef _DEBUG
+	assert(disjointRects.Disjoint(bottom));
+	assert(disjointRects.Disjoint(right));
+#endif
+}
+
+void GuillotineBinPack::MergeFreeList()
+{
+#ifdef _DEBUG
+	DisjointRectCollection test;
+	for(size_t i = 0; i < freeRectangles.size(); ++i)
+		assert(test.Add(freeRectangles[i]) == true);
+#endif
+
+	// Do a Theta(n^2) loop to see if any pair of free rectangles could me merged into one.
+	// Note that we miss any opportunities to merge three rectangles into one. (should call this function again to detect that)
+	for(size_t i = 0; i < freeRectangles.size(); ++i)
+		for(size_t j = i+1; j < freeRectangles.size(); ++j)
+		{
+			if (freeRectangles[i].width == freeRectangles[j].width && freeRectangles[i].x == freeRectangles[j].x)
+			{
+				if (freeRectangles[i].y == freeRectangles[j].y + freeRectangles[j].height)
+				{
+					freeRectangles[i].y -= freeRectangles[j].height;
+					freeRectangles[i].height += freeRectangles[j].height;
+					freeRectangles.erase(freeRectangles.begin() + j);
+					--j;
+				}
+				else if (freeRectangles[i].y + freeRectangles[i].height == freeRectangles[j].y)
+				{
+					freeRectangles[i].height += freeRectangles[j].height;
+					freeRectangles.erase(freeRectangles.begin() + j);
+					--j;
+				}
+			}
+			else if (freeRectangles[i].height == freeRectangles[j].height && freeRectangles[i].y == freeRectangles[j].y)
+			{
+				if (freeRectangles[i].x == freeRectangles[j].x + freeRectangles[j].width)
+				{
+					freeRectangles[i].x -= freeRectangles[j].width;
+					freeRectangles[i].width += freeRectangles[j].width;
+					freeRectangles.erase(freeRectangles.begin() + j);
+					--j;
+				}
+				else if (freeRectangles[i].x + freeRectangles[i].width == freeRectangles[j].x)
+				{
+					freeRectangles[i].width += freeRectangles[j].width;
+					freeRectangles.erase(freeRectangles.begin() + j);
+					--j;
+				}
+			}
+		}
+
+#ifdef _DEBUG
+	test.Clear();
+	for(size_t i = 0; i < freeRectangles.size(); ++i)
+		assert(test.Add(freeRectangles[i]) == true);
+#endif
+}

CLB/src/GuillotineBinPack.h

+/** @file GuillotineBinPack.h
+	@author Jukka Jylänki
+
+	@brief Implements different bin packer algorithms that use the GUILLOTINE data structure.
+
+	This work is released to Public Domain, do whatever you want with it.
+*/
+#pragma once
+
+#include <vector>
+
+#include "Rect.h"
+
+/** GuillotineBinPack implements different variants of bin packer algorithms that use the GUILLOTINE data structure
+	to keep track of the free space of the bin where rectangles may be placed. */
+class GuillotineBinPack
+{
+public:
+	/// The initial bin size will be (0,0). Call Init to set the bin size.
+	GuillotineBinPack();
+
+	/// Initializes a new bin of the given size.
+	GuillotineBinPack(int width, int height);
+
+	/// (Re)initializes the packer to an empty bin of width x height units. Call whenever
+	/// you need to restart with a new bin.
+	void Init(int width, int height);
+
+	/// Specifies the different choice heuristics that can be used when deciding which of the free subrectangles
+	/// to place the to-be-packed rectangle into.
+	enum FreeRectChoiceHeuristic
+	{
+		RectBestAreaFit, ///< -BAF
+		RectBestShortSideFit, ///< -BSSF
+		RectBestLongSideFit, ///< -BLSF
+		RectWorstAreaFit, ///< -WAF
+		RectWorstShortSideFit, ///< -WSSF
+		RectWorstLongSideFit ///< -WLSF
+	};
+
+	/// Specifies the different choice heuristics that can be used when the packer needs to decide whether to
+	/// subdivide the remaining free space in horizontal or vertical direction.
+	enum GuillotineSplitHeuristic
+	{
+		SplitShorterLeftoverAxis, ///< -SLAS
+		SplitLongerLeftoverAxis, ///< -LLAS
+		SplitMinimizeArea, ///< -MINAS, Try to make a single big rectangle at the expense of making the other small.
+		SplitMaximizeArea, ///< -MAXAS, Try to make both remaining rectangles as even-sized as possible.
+		SplitShorterAxis, ///< -SAS
+		SplitLongerAxis ///< -LAS
+	};
+
+	/// Inserts a single rectangle into the bin. The packer might rotate the rectangle, in which case the returned
+	/// struct will have the width and height values swapped.
+	/// @param merge If true, performs free Rectangle Merge procedure after packing the new rectangle. This procedure
+	///		tries to defragment the list of disjoint free rectangles to improve packing performance, but also takes up 
+	///		some extra time.
+	/// @param rectChoice The free rectangle choice heuristic rule to use.
+	/// @param splitMethod The free rectangle split heuristic rule to use.
+	Rect Insert(int width, int height, bool merge, FreeRectChoiceHeuristic rectChoice, GuillotineSplitHeuristic splitMethod);
+
+	/// Inserts a list of rectangles into the bin.
+	/// @param rects The list of rectangles to add. This list will be destroyed in the packing process.
+	/// @param dst The outputted list of rectangles. Note that the indices will not correspond to the input indices.
+	/// @param merge If true, performs Rectangle Merge operations during the packing process.
+	/// @param rectChoice The free rectangle choice heuristic rule to use.
+	/// @param splitMethod The free rectangle split heuristic rule to use.
+	void Insert(std::vector<RectSize> &rects, std::vector<Rect> &dst, bool merge, 
+		FreeRectChoiceHeuristic rectChoice, GuillotineSplitHeuristic splitMethod);
+
+// Implements GUILLOTINE-MAXFITTING, an experimental heuristic that's really cool but didn't quite work in practice.
+//	void InsertMaxFitting(std::vector<RectSize> &rects, std::vector<Rect> &dst, bool merge, 
+//		FreeRectChoiceHeuristic rectChoice, GuillotineSplitHeuristic splitMethod);
+
+	/// Computes the ratio of used/total surface area. 0.00 means no space is yet used, 1.00 means the whole bin is used.
+	float Occupancy() const;
+
+	/// Returns the internal list of disjoint rectangles that track the free area of the bin. You may alter this vector
+	/// any way desired, as long as the end result still is a list of disjoint rectangles.
+	std::vector<Rect> &GetFreeRectangles() { return freeRectangles; }
+
+	/// Returns the list of packed rectangles. You may alter this vector at will, for example, you can move a Rect from
+	/// this list to the Free Rectangles list to free up space on-the-fly, but notice that this causes fragmentation.
+	std::vector<Rect> &GetUsedRectangles() { return usedRectangles; }
+
+	/// Performs a Rectangle Merge operation. This procedure looks for adjacent free rectangles and merges them if they
+	/// can be represented with a single rectangle. Takes up Theta(|freeRectangles|^2) time.
+	void MergeFreeList();
+
+private:
+	int binWidth;
+	int binHeight;
+
+	/// Stores a list of all the rectangles that we have packed so far. This is used only to compute the Occupancy ratio,
+	/// so if you want to have the packer consume less memory, this can be removed.
+	std::vector<Rect> usedRectangles;
+
+	/// Stores a list of rectangles that represents the free area of the bin. This rectangles in this list are disjoint.
+	std::vector<Rect> freeRectangles;
+
+#ifdef _DEBUG
+	/// Used to track that the packer produces proper packings.
+	DisjointRectCollection disjointRects;
+#endif
+
+	/// Goes through the list of free rectangles and finds the best one to place a rectangle of given size into.
+	/// Running time is Theta(|freeRectangles|).
+	/// @param nodeIndex [out] The index of the free rectangle in the freeRectangles array into which the new
+	///		rect was placed.
+	/// @return A Rect structure that represents the placement of the new rect into the best free rectangle.
+	Rect FindPositionForNewNode(int width, int height, FreeRectChoiceHeuristic rectChoice, int *nodeIndex);
+
+	static int ScoreByHeuristic(int width, int height, const Rect &freeRect, FreeRectChoiceHeuristic rectChoice);
+	// The following functions compute (penalty) score values if a rect of the given size was placed into the 
+	// given free rectangle. In these score values, smaller is better.
+
+	static int ScoreBestAreaFit(int width, int height, const Rect &freeRect);
+	static int ScoreBestShortSideFit(int width, int height, const Rect &freeRect);
+	static int ScoreBestLongSideFit(int width, int height, const Rect &freeRect);
+
+	static int ScoreWorstAreaFit(int width, int height, const Rect &freeRect);
+	static int ScoreWorstShortSideFit(int width, int height, const Rect &freeRect);
+	static int ScoreWorstLongSideFit(int width, int height, const Rect &freeRect);
+
+	/// Splits the given L-shaped free rectangle into two new free rectangles after placedRect has been placed into it.
+	/// Determines the split axis by using the given heuristic.
+	void SplitFreeRectByHeuristic(const Rect &freeRect, const Rect &placedRect, GuillotineSplitHeuristic method);
+
+	/// Splits the given L-shaped free rectangle into two new free rectangles along the given fixed split axis.
+	void SplitFreeRectAlongAxis(const Rect &freeRect, const Rect &placedRect, bool splitHorizontal);
+};

CLB/src/MaxRectsBinPack.cpp

+/** @file MaxRectsBinPack.cpp
+	@author Jukka Jylänki
+
+	@brief Implements different bin packer algorithms that use the MAXRECTS data structure.
+
+	This work is released to Public Domain, do whatever you want with it.
+*/
+#include <utility>
+#include <iostream>
+
+#include <cassert>
+#include <cmath>
+#include <cstring>
+#include <limits>
+
+#include "MaxRectsBinPack.h"
+
+using namespace std;
+
+MaxRectsBinPack::MaxRectsBinPack()
+:binWidth(0),
+binHeight(0)
+{
+}
+
+MaxRectsBinPack::MaxRectsBinPack(int width, int height)
+{
+	Init(width, height);
+}
+
+void MaxRectsBinPack::Init(int width, int height)
+{
+	binWidth = width;
+	binHeight = height;
+
+	Rect n;
+	n.x = 0;
+	n.y = 0;
+	n.width = width;
+	n.height = height;
+
+	usedRectangles.clear();
+
+	freeRectangles.clear();
+	freeRectangles.push_back(n);
+}
+
+Rect MaxRectsBinPack::Insert(int width, int height, FreeRectChoiceHeuristic method)
+{
+	Rect newNode;
+	int score1; // Unused in this function. We don't need to know the score after finding the position.
+	int score2;
+	switch(method)
+	{
+		case RectBestShortSideFit: newNode = FindPositionForNewNodeBestShortSideFit(width, height, score1, score2); break;
+		case RectBottomLeftRule: newNode = FindPositionForNewNodeBottomLeft(width, height, score1, score2); break;
+		case RectContactPointRule: newNode = FindPositionForNewNodeContactPoint(width, height, score1); break;
+		case RectBestLongSideFit: newNode = FindPositionForNewNodeBestLongSideFit(width, height, score2, score1); break;
+		case RectBestAreaFit: newNode = FindPositionForNewNodeBestAreaFit(width, height, score1, score2); break;
+	}
+		
+	if (newNode.height == 0)
+		return newNode;
+
+	size_t numRectanglesToProcess = freeRectangles.size();
+	for(size_t i = 0; i < numRectanglesToProcess; ++i)
+	{
+		if (SplitFreeNode(freeRectangles[i], newNode))
+		{
+			freeRectangles.erase(freeRectangles.begin() + i);
+			--i;
+			--numRectanglesToProcess;
+		}
+	}
+
+	PruneFreeList();
+
+	usedRectangles.push_back(newNode);
+	return newNode;
+}
+
+void MaxRectsBinPack::Insert(std::vector<RectSize> &rects, std::vector<Rect> &dst, FreeRectChoiceHeuristic method)
+{
+	dst.clear();
+
+	while(rects.size() > 0)
+	{
+		int bestScore1 = std::numeric_limits<int>::max();
+		int bestScore2 = std::numeric_limits<int>::max();
+		int bestRectIndex = -1;
+		Rect bestNode;
+
+		for(size_t i = 0; i < rects.size(); ++i)
+		{
+			int score1;
+			int score2;
+			Rect newNode = ScoreRect(rects[i].width, rects[i].height, method, score1, score2);
+
+			if (score1 < bestScore1 || (score1 == bestScore1 && score2 < bestScore2))
+			{
+				bestScore1 = score1;
+				bestScore2 = score2;
+				bestNode = newNode;
+				bestRectIndex = i;
+			}
+		}
+
+		if (bestRectIndex == -1)
+			return;
+
+		PlaceRect(bestNode);
+		rects.erase(rects.begin() + bestRectIndex);
+	}
+}
+
+void MaxRectsBinPack::PlaceRect(const Rect &node)
+{
+	size_t numRectanglesToProcess = freeRectangles.size();
+	for(size_t i = 0; i < numRectanglesToProcess; ++i)
+	{
+		if (SplitFreeNode(freeRectangles[i], node))
+		{
+			freeRectangles.erase(freeRectangles.begin() + i);
+			--i;
+			--numRectanglesToProcess;
+		}
+	}
+
+	PruneFreeList();
+
+	usedRectangles.push_back(node);
+	//		dst.push_back(bestNode); ///\todo Refactor so that this compiles.
+}
+
+Rect MaxRectsBinPack::ScoreRect(int width, int height, FreeRectChoiceHeuristic method, int &score1, int &score2) const
+{
+	Rect newNode;
+	score1 = std::numeric_limits<int>::max();
+	score2 = std::numeric_limits<int>::max();
+	switch(method)
+	{
+	case RectBestShortSideFit: newNode = FindPositionForNewNodeBestShortSideFit(width, height, score1, score2); break;
+	case RectBottomLeftRule: newNode = FindPositionForNewNodeBottomLeft(width, height, score1, score2); break;
+	case RectContactPointRule: newNode = FindPositionForNewNodeContactPoint(width, height, score1); 
+		score1 = -score1; // Reverse since we are minimizing, but for contact point score bigger is better.
+		break;
+	case RectBestLongSideFit: newNode = FindPositionForNewNodeBestLongSideFit(width, height, score2, score1); break;
+	case RectBestAreaFit: newNode = FindPositionForNewNodeBestAreaFit(width, height, score1, score2); break;
+	}
+
+	// Cannot fit the current rectangle.
+	if (newNode.height == 0)
+	{
+		score1 = std::numeric_limits<int>::max();
+		score2 = std::numeric_limits<int>::max();
+	}
+
+	return newNode;
+}
+
+/// Computes the ratio of used surface area.
+float MaxRectsBinPack::Occupancy() const
+{
+	unsigned long usedSurfaceArea = 0;
+	for(size_t i = 0; i < usedRectangles.size(); ++i)
+		usedSurfaceArea += usedRectangles[i].width * usedRectangles[i].height;
+
+	return (float)usedSurfaceArea / (binWidth * binHeight);
+}
+
+Rect MaxRectsBinPack::FindPositionForNewNodeBottomLeft(int width, int height, int &bestY, int &bestX) const
+{
+	Rect bestNode;
+	memset(&bestNode, 0, sizeof(Rect));
+
+	bestY = std::numeric_limits<int>::max();
+
+	for(size_t i = 0; i < freeRectangles.size(); ++i)
+	{
+		// Try to place the rectangle in upright (non-flipped) orientation.
+		if (freeRectangles[i].width >= width && freeRectangles[i].height >= height)
+		{
+			int topSideY = freeRectangles[i].y + height;
+			if (topSideY < bestY || (topSideY == bestY && freeRectangles[i].x < bestX))
+			{
+				bestNode.x = freeRectangles[i].x;
+				bestNode.y = freeRectangles[i].y;
+				bestNode.width = width;
+				bestNode.height = height;
+				bestY = topSideY;
+				bestX = freeRectangles[i].x;
+			}
+		}
+		if (freeRectangles[i].width >= height && freeRectangles[i].height >= width)
+		{
+			int topSideY = freeRectangles[i].y + width;
+			if (topSideY < bestY || (topSideY == bestY && freeRectangles[i].x < bestX))
+			{
+				bestNode.x = freeRectangles[i].x;
+				bestNode.y = freeRectangles[i].y;
+				bestNode.width = height;
+				bestNode.height = width;
+				bestY = topSideY;
+				bestX = freeRectangles[i].x;
+			}
+		}
+	}
+	return bestNode;
+}
+
+Rect MaxRectsBinPack::FindPositionForNewNodeBestShortSideFit(int width, int height, 
+	int &bestShortSideFit, int &bestLongSideFit) const
+{
+	Rect bestNode;
+	memset(&bestNode, 0, sizeof(Rect));
+
+	bestShortSideFit = std::numeric_limits<int>::max();
+
+	for(size_t i = 0; i < freeRectangles.size(); ++i)
+	{
+		// Try to place the rectangle in upright (non-flipped) orientation.
+		if (freeRectangles[i].width >= width && freeRectangles[i].height >= height)
+		{
+			int leftoverHoriz = abs(freeRectangles[i].width - width);
+			int leftoverVert = abs(freeRectangles[i].height - height);
+			int shortSideFit = min(leftoverHoriz, leftoverVert);
+			int longSideFit = max(leftoverHoriz, leftoverVert);
+
+			if (shortSideFit < bestShortSideFit || (shortSideFit == bestShortSideFit && longSideFit < bestLongSideFit))
+			{
+				bestNode.x = freeRectangles[i].x;
+				bestNode.y = freeRectangles[i].y;
+				bestNode.width = width;
+				bestNode.height = height;
+				bestShortSideFit = shortSideFit;
+				bestLongSideFit = longSideFit;
+			}
+		}
+
+		if (freeRectangles[i].width >= height && freeRectangles[i].height >= width)
+		{
+			int flippedLeftoverHoriz = abs(freeRectangles[i].width - height);
+			int flippedLeftoverVert = abs(freeRectangles[i].height - width);
+			int flippedShortSideFit = min(flippedLeftoverHoriz, flippedLeftoverVert);
+			int flippedLongSideFit = max(flippedLeftoverHoriz, flippedLeftoverVert);
+
+			if (flippedShortSideFit < bestShortSideFit || (flippedShortSideFit == bestShortSideFit && flippedLongSideFit < bestLongSideFit))
+			{
+				bestNode.x = freeRectangles[i].x;
+				bestNode.y = freeRectangles[i].y;
+				bestNode.width = height;
+				bestNode.height = width;
+				bestShortSideFit = flippedShortSideFit;
+				bestLongSideFit = flippedLongSideFit;
+			}
+		}
+	}
+	return bestNode;
+}
+
+Rect MaxRectsBinPack::FindPositionForNewNodeBestLongSideFit(int width, int height, 
+	int &bestShortSideFit, int &bestLongSideFit) const
+{
+	Rect bestNode;
+	memset(&bestNode, 0, sizeof(Rect));
+
+	bestLongSideFit = std::numeric_limits<int>::max();
+
+	for(size_t i = 0; i < freeRectangles.size(); ++i)
+	{
+		// Try to place the rectangle in upright (non-flipped) orientation.
+		if (freeRectangles[i].width >= width && freeRectangles[i].height >= height)
+		{
+			int leftoverHoriz = abs(freeRectangles[i].width - width);
+			int leftoverVert = abs(freeRectangles[i].height - height);
+			int shortSideFit = min(leftoverHoriz, leftoverVert);
+			int longSideFit = max(leftoverHoriz, leftoverVert);
+
+			if (longSideFit < bestLongSideFit || (longSideFit == bestLongSideFit && shortSideFit < bestShortSideFit))
+			{
+				bestNode.x = freeRectangles[i].x;
+				bestNode.y = freeRectangles[i].y;
+				bestNode.width = width;
+				bestNode.height = height;
+				bestShortSideFit = shortSideFit;
+				bestLongSideFit = longSideFit;
+			}
+		}
+
+		if (freeRectangles[i].width >= height && freeRectangles[i].height >= width)
+		{
+			int leftoverHoriz = abs(freeRectangles[i].width - height);
+			int leftoverVert = abs(freeRectangles[i].height - width);
+			int shortSideFit = min(leftoverHoriz, leftoverVert);
+			int longSideFit = max(leftoverHoriz, leftoverVert);
+
+			if (longSideFit < bestLongSideFit || (longSideFit == bestLongSideFit && shortSideFit < bestShortSideFit))
+			{
+				bestNode.x = freeRectangles[i].x;
+				bestNode.y = freeRectangles[i].y;
+				bestNode.width = height;
+				bestNode.height = width;
+				bestShortSideFit = shortSideFit;
+				bestLongSideFit = longSideFit;
+			}
+		}
+	}
+	return bestNode;
+}
+
+Rect MaxRectsBinPack::FindPositionForNewNodeBestAreaFit(int width, int height, 
+	int &bestAreaFit, int &bestShortSideFit) const
+{
+	Rect bestNode;
+	memset(&bestNode, 0, sizeof(Rect));
+
+	bestAreaFit = std::numeric_limits<int>::max();
+
+	for(size_t i = 0; i < freeRectangles.size(); ++i)
+	{
+		int areaFit = freeRectangles[i].width * freeRectangles[i].height - width * height;
+
+		// Try to place the rectangle in upright (non-flipped) orientation.
+		if (freeRectangles[i].width >= width && freeRectangles[i].height >= height)
+		{
+			int leftoverHoriz = abs(freeRectangles[i].width - width);
+			int leftoverVert = abs(freeRectangles[i].height - height);
+			int shortSideFit = min(leftoverHoriz, leftoverVert);
+
+			if (areaFit < bestAreaFit || (areaFit == bestAreaFit && shortSideFit < bestShortSideFit))
+			{
+				bestNode.x = freeRectangles[i].x;
+				bestNode.y = freeRectangles[i].y;
+				bestNode.width = width;
+				bestNode.height = height;
+				bestShortSideFit = shortSideFit;
+				bestAreaFit = areaFit;
+			}
+		}
+
+		if (freeRectangles[i].width >= height && freeRectangles[i].height >= width)
+		{
+			int leftoverHoriz = abs(freeRectangles[i].width - height);
+			int leftoverVert = abs(freeRectangles[i].height - width);
+			int shortSideFit = min(leftoverHoriz, leftoverVert);
+
+			if (areaFit < bestAreaFit || (areaFit == bestAreaFit && shortSideFit < bestShortSideFit))
+			{
+				bestNode.x = freeRectangles[i].x;
+				bestNode.y = freeRectangles[i].y;
+				bestNode.width = height;
+				bestNode.height = width;
+				bestShortSideFit = shortSideFit;
+				bestAreaFit = areaFit;
+			}
+		}
+	}
+	return bestNode;
+}
+
+/// Returns 0 if the two intervals i1 and i2 are disjoint, or the length of their overlap otherwise.
+int CommonIntervalLength(int i1start, int i1end, int i2start, int i2end)
+{
+	if (i1end < i2start || i2end < i1start)
+		return 0;
+	return min(i1end, i2end) - max(i1start, i2start);
+}
+
+int MaxRectsBinPack::ContactPointScoreNode(int x, int y, int width, int height) const
+{
+	int score = 0;
+
+	if (x == 0 || x + width == binWidth)
+		score += height;
+	if (y == 0 || y + height == binHeight)
+		score += width;
+
+	for(size_t i = 0; i < usedRectangles.size(); ++i)
+	{
+		if (usedRectangles[i].x == x + width || usedRectangles[i].x + usedRectangles[i].width == x)
+			score += CommonIntervalLength(usedRectangles[i].y, usedRectangles[i].y + usedRectangles[i].height, y, y + height);
+		if (usedRectangles[i].y == y + height || usedRectangles[i].y + usedRectangles[i].height == y)
+			score += CommonIntervalLength(usedRectangles[i].x, usedRectangles[i].x + usedRectangles[i].width, x, x + width);
+	}
+	return score;
+}
+
+Rect MaxRectsBinPack::FindPositionForNewNodeContactPoint(int width, int height, int &bestContactScore) const
+{
+	Rect bestNode;
+	memset(&bestNode, 0, sizeof(Rect));
+
+	bestContactScore = -1;
+
+	for(size_t i = 0; i < freeRectangles.size(); ++i)
+	{
+		// Try to place the rectangle in upright (non-flipped) orientation.
+		if (freeRectangles[i].width >= width && freeRectangles[i].height >= height)
+		{
+			int score = ContactPointScoreNode(freeRectangles[i].x, freeRectangles[i].y, width, height);
+			if (score > bestContactScore)
+			{
+				bestNode.x = freeRectangles[i].x;
+				bestNode.y = freeRectangles[i].y;
+				bestNode.width = width;
+				bestNode.height = height;
+				bestContactScore = score;
+			}
+		}
+		if (freeRectangles[i].width >= height && freeRectangles[i].height >= width)
+		{
+			int score = ContactPointScoreNode(freeRectangles[i].x, freeRectangles[i].y, width, height);
+			if (score > bestContactScore)
+			{
+				bestNode.x = freeRectangles[i].x;
+				bestNode.y = freeRectangles[i].y;
+				bestNode.width = height;
+				bestNode.height = width;
+				bestContactScore = score;
+			}
+		}
+	}
+	return bestNode;
+}
+
+bool MaxRectsBinPack::SplitFreeNode(Rect freeNode, const Rect &usedNode)
+{
+	// Test with SAT if the rectangles even intersect.
+	if (usedNode.x >= freeNode.x + freeNode.width || usedNode.x + usedNode.width <= freeNode.x ||
+		usedNode.y >= freeNode.y + freeNode.height || usedNode.y + usedNode.height <= freeNode.y)
+		return false;
+
+	if (usedNode.x < freeNode.x + freeNode.width && usedNode.x + usedNode.width > freeNode.x)
+	{
+		// New node at the top side of the used node.
+		if (usedNode.y > freeNode.y && usedNode.y < freeNode.y + freeNode.height)
+		{
+			Rect newNode = freeNode;
+			newNode.height = usedNode.y - newNode.y;
+			freeRectangles.push_back(newNode);
+		}
+
+		// New node at the bottom side of the used node.
+		if (usedNode.y + usedNode.height < freeNode.y + freeNode.height)
+		{
+			Rect newNode = freeNode;
+			newNode.y = usedNode.y + usedNode.height;
+			newNode.height = freeNode.y + freeNode.height - (usedNode.y + usedNode.height);
+			freeRectangles.push_back(newNode);
+		}
+	}
+
+	if (usedNode.y < freeNode.y + freeNode.height && usedNode.y + usedNode.height > freeNode.y)
+	{
+		// New node at the left side of the used node.
+		if (usedNode.x > freeNode.x && usedNode.x < freeNode.x + freeNode.width)
+		{
+			Rect newNode = freeNode;
+			newNode.width = usedNode.x - newNode.x;
+			freeRectangles.push_back(newNode);
+		}
+
+		// New node at the right side of the used node.
+		if (usedNode.x + usedNode.width < freeNode.x + freeNode.width)
+		{
+			Rect newNode = freeNode;
+			newNode.x = usedNode.x + usedNode.width;
+			newNode.width = freeNode.x + freeNode.width - (usedNode.x + usedNode.width);
+			freeRectangles.push_back(newNode);
+		}
+	}
+
+	return true;
+}
+
+void MaxRectsBinPack::PruneFreeList()
+{
+	/* 
+	///  Would be nice to do something like this, to avoid a Theta(n^2) loop through each pair.
+	///  But unfortunately it doesn't quite cut it, since we also want to detect containment. 
+	///  Perhaps there's another way to do this faster than Theta(n^2).
+
+	if (freeRectangles.size() > 0)
+		clb::sort::QuickSort(&freeRectangles[0], freeRectangles.size(), NodeSortCmp);
+
+	for(size_t i = 0; i < freeRectangles.size()-1; ++i)
+		if (freeRectangles[i].x == freeRectangles[i+1].x &&
+		    freeRectangles[i].y == freeRectangles[i+1].y &&
+		    freeRectangles[i].width == freeRectangles[i+1].width &&
+		    freeRectangles[i].height == freeRectangles[i+1].height)
+		{
+			freeRectangles.erase(freeRectangles.begin() + i);
+			--i;
+		}
+	*/
+
+	/// Go through each pair and remove any rectangle that is redundant.
+	for(size_t i = 0; i < freeRectangles.size(); ++i)
+		for(size_t j = i+1; j < freeRectangles.size(); ++j)
+		{
+			if (IsContainedIn(freeRectangles[i], freeRectangles[j]))
+			{
+				freeRectangles.erase(freeRectangles.begin()+i);
+				--i;
+				break;
+			}
+			if (IsContainedIn(freeRectangles[j], freeRectangles[i]))
+			{
+				freeRectangles.erase(freeRectangles.begin()+j);
+				--j;
+			}
+		}
+}

CLB/src/MaxRectsBinPack.h

+/** @file MaxRectsBinPack.h
+	@author Jukka Jylänki
+
+	@brief Implements different bin packer algorithms that use the MAXRECTS data structure.
+
+	This work is released to Public Domain, do whatever you want with it.
+*/
+#pragma once
+
+#include <vector>
+
+#include "Rect.h"
+
+/** MaxRectsBinPack implements the MAXRECTS data structure and different bin packing algorithms that 
+	use this structure. */
+class MaxRectsBinPack
+{
+public:
+	/// Instantiates a bin of size (0,0). Call Init to create a new bin.
+	MaxRectsBinPack();
+
+	/// Instantiates a bin of the given size.
+	MaxRectsBinPack(int width, int height);
+
+	/// (Re)initializes the packer to an empty bin of width x height units. Call whenever
+	/// you need to restart with a new bin.
+	void Init(int width, int height);
+
+	/// Specifies the different heuristic rules that can be used when deciding where to place a new rectangle.
+	enum FreeRectChoiceHeuristic
+	{
+		RectBestShortSideFit, ///< -BSSF: Positions the rectangle against the short side of a free rectangle into which it fits the best.
+		RectBestLongSideFit, ///< -BLSF: Positions the rectangle against the long side of a free rectangle into which it fits the best.
+		RectBestAreaFit, ///< -BAF: Positions the rectangle into the smallest free rect into which it fits.
+		RectBottomLeftRule, ///< -BL: Does the Tetris placement.
+		RectContactPointRule ///< -CP: Choosest the placement where the rectangle touches other rects as much as possible.
+	};
+
+	/// Inserts the given list of rectangles in an offline/batch mode, possibly rotated.
+	/// @param rects The list of rectangles to insert. This vector will be destroyed in the process.
+	/// @param dst [out] This list will contain the packed rectangles. The indices will not correspond to that of rects.
+	/// @param method The rectangle placement rule to use when packing.
+	void Insert(std::vector<RectSize> &rects, std::vector<Rect> &dst, FreeRectChoiceHeuristic method);
+
+	/// Inserts a single rectangle into the bin, possibly rotated.
+	Rect Insert(int width, int height, FreeRectChoiceHeuristic method);
+
+	/// Computes the ratio of used surface area to the total bin area.
+	float Occupancy() const;
+
+private:
+	int binWidth;
+	int binHeight;
+
+	std::vector<Rect> usedRectangles;
+	std::vector<Rect> freeRectangles;
+
+	/// Computes the placement score for placing the given rectangle with the given method.
+	/// @param score1 [out] The primary placement score will be outputted here.
+	/// @param score2 [out] The secondary placement score will be outputted here. This isu sed to break ties.
+	/// @return This struct identifies where the rectangle would be placed if it were placed.
+	Rect ScoreRect(int width, int height, FreeRectChoiceHeuristic method, int &score1, int &score2) const;
+
+	/// Places the given rectangle into the bin.
+	void PlaceRect(const Rect &node);
+
+	/// Computes the placement score for the -CP variant.
+	int ContactPointScoreNode(int x, int y, int width, int height) const;
+
+	Rect FindPositionForNewNodeBottomLeft(int width, int height, int &bestY, int &bestX) const;
+	Rect FindPositionForNewNodeBestShortSideFit(int width, int height, int &bestShortSideFit, int &bestLongSideFit) const;
+	Rect FindPositionForNewNodeBestLongSideFit(int width, int height, int &bestShortSideFit, int &bestLongSideFit) const;
+	Rect FindPositionForNewNodeBestAreaFit(int width, int height, int &bestAreaFit, int &bestShortSideFit) const;
+	Rect FindPositionForNewNodeContactPoint(int width, int height, int &contactScore) const;
+
+	/// @return True if the free node was split.
+	bool SplitFreeNode(Rect freeNode, const Rect &usedNode);
+
+	/// Goes through the free rectangle list and removes any redundant entries.
+	void PruneFreeList();
+};
+/** @file Rect.cpp
+	@author Jukka Jylänki
+
+	This work is released to Public Domain, do whatever you want with it.
+*/
+#include <utility>
+
+#include "Rect.h"
+
+/*
+#include "clb/Algorithm/Sort.h"
+
+int CompareRectShortSide(const Rect &a, const Rect &b)
+{
+	using namespace std;
+
+	int smallerSideA = min(a.width, a.height);
+	int smallerSideB = min(b.width, b.height);
+
+	if (smallerSideA != smallerSideB)
+		return clb::sort::TriCmp(smallerSideA, smallerSideB);
+
+	// Tie-break on the larger side.
+	int largerSideA = max(a.width, a.height);
+	int largerSideB = max(b.width, b.height);
+
+	return clb::sort::TriCmp(largerSideA, largerSideB);
+}
+*/
+/*
+int NodeSortCmp(const Rect &a, const Rect &b)
+{
+	if (a.x != b.x)
+		return clb::sort::TriCmp(a.x, b.x);
+	if (a.y != b.y)
+		return clb::sort::TriCmp(a.y, b.y);
+	if (a.width != b.width)
+		return clb::sort::TriCmp(a.width, b.width);
+	return clb::sort::TriCmp(a.height, b.height);
+}
+*/
+bool IsContainedIn(const Rect &a, const Rect &b)
+{
+	return a.x >= b.x && a.y >= b.y 
+		&& a.x+a.width <= b.x+b.width 
+		&& a.y+a.height <= b.y+b.height;
+}
+/** @file Rect.h
+	@author Jukka Jylänki
+
+	This work is released to Public Domain, do whatever you want with it.
+*/
+#pragma once
+
+#include <cstddef>
+#include <vector>
+
+struct RectSize
+{
+	int width;
+	int height;
+};
+
+struct Rect
+{
+	int x;
+	int y;
+	int width;
+	int height;
+};
+
+/// Performs a lexicographic compare on (rect short side, rect long side).
+/// @return -1 if the smaller side of a is shorter than the smaller side of b, 1 if the other way around.
+///   If they are equal, the larger side length is used as a tie-breaker.
+///   If the rectangles are of same size, returns 0.
+int CompareRectShortSide(const Rect &a, const Rect &b);
+
+/// Performs a lexicographic compare on (x, y, width, height).
+int NodeSortCmp(const Rect &a, const Rect &b);
+
+/// Returns true if a is contained in b.
+bool IsContainedIn(const Rect &a, const Rect &b);
+
+class DisjointRectCollection
+{
+public:
+	std::vector<Rect> rects;
+
+	bool Add(const Rect &r)
+	{
+		// Degenerate rectangles are ignored.
+		if (r.width == 0 || r.height == 0)
+			return true;
+
+		if (!Disjoint(r))
+			return false;
+		rects.push_back(r);
+		return true;
+	}
+
+	void Clear()
+	{
+		rects.clear();
+	}
+
+	bool Disjoint(const Rect &r) const
+	{
+		// Degenerate rectangles are ignored.
+		if (r.width == 0 || r.height == 0)
+			return true;
+
+		for(size_t i = 0; i < rects.size(); ++i)
+			if (!Disjoint(rects[i], r))
+				return false;
+		return true;
+	}
+
+	static bool Disjoint(const Rect &a, const Rect &b)
+	{
+		if (a.x + a.width <= b.x ||
+			b.x + b.width <= a.x ||
+			a.y + a.height <= b.y ||
+			b.y + b.height <= a.y)
+			return true;
+		return false;
+	}
+};

CLB/src/RectangleBinPack.cpp

-/** @file RectangleBinPack.cpp
-	@author Jukka Jylänki
-
-	This work is released to Public Domain, do whatever you want with it.
-
-	@brief RectangleBinPack is a data structure for performing online rectangle bin packing.
-*/
-#include "RectangleBinPack.h"
-
-/** Restarts the packing process, clearing all previously packed rectangles and
-	sets up a new bin of a given initial size. These bin dimensions stay fixed during
-	the whole packing process, i.e. to change the bin size, the packing must be
-	restarted again with a new call to Init(). */
-void RectangleBinPack::Init(int width, int height)
-{
-	binWidth = width;
-	binHeight = height;
-	root.left = root.right = 0;
-	root.x = root.y = 0;
-	root.width = width;
-	root.height = height;
-}
-
-/** @return A value [0, 1] denoting the ratio of total surface area that is in use.
-	0.0f - the bin is totally empty, 1.0f - the bin is full. */
-float RectangleBinPack::Occupancy() const
-{
-	unsigned long totalSurfaceArea = binWidth * binHeight;
-	unsigned long usedSurfaceArea = UsedSurfaceArea(root);
-
-	return (float)usedSurfaceArea/totalSurfaceArea;
-}
-
-/** Recursively calls itself. */
-unsigned long RectangleBinPack::UsedSurfaceArea(const Node &node) const
-{
-	if (node.left || node.right)
-	{
-		unsigned long usedSurfaceArea = node.width * node.height;
-		if (node.left)
-			usedSurfaceArea += UsedSurfaceArea(*node.left);
-		if (node.right)
-			usedSurfaceArea += UsedSurfaceArea(*node.right);
-
-		return usedSurfaceArea;
-	}
-
-	// This is a leaf node, it doesn't constitute to the total surface area.
-	return 0;
-}
-
-/** Running time is linear to the number of rectangles already packed. Recursively calls itself.
-	@return 0 If the insertion didn't succeed. */
-RectangleBinPack::Node *RectangleBinPack::Insert(RectangleBinPack::Node *node, int width, int height)
-{
-	// If this node is an internal node, try both leaves for possible space.
-	// (The rectangle in an internal node stores used space, the leaves store free space)
-	if (node->left || node->right)
-	{
-		if (node->left)
-		{
-			Node *newNode = Insert(node->left, width, height);
-			if (newNode)
-				return newNode;
-		}
-		if (node->right)
-		{
-			Node *newNode = Insert(node->right, width, height);
-			if (newNode)
-				return newNode;
-		}
-		return 0; // Didn't fit into either subtree!
-	}
-
-	// This node is a leaf, but can we fit the new rectangle here?
-	if (width > node->width || height > node->height)
-		return 0; // Too bad, no space.
-
-	// The new cell will fit, split the remaining space along the shorter axis,
-	// that is probably more optimal.
-	int w = node->width - width;
-	int h = node->height - height;
-	node->left = new Node;
-	node->right = new Node;
-	if (w <= h) // Split the remaining space in horizontal direction.
-	{
-		node->left->x = node->x + width;
-		node->left->y = node->y;
-		node->left->width = w;
-		node->left->height = height;
-
-		node->right->x = node->x;
-		node->right->y = node->y + height;
-		node->right->width = node->width;
-		node->right->height = h;
-	}
-	else // Split the remaining space in vertical direction.
-	{
-		node->left->x = node->x;
-		node->left->y = node->y + height;
-		node->left->width = width;
-		node->left->height = h;
-
-		node->right->x = node->x + width;
-		node->right->y = node->y;
-		node->right->width = w;
-		node->right->height = node->height;
-	}
-	// Note that as a result of the above, it can happen that node->left or node->right
-	// is now a degenerate (zero area) rectangle. No need to do anything about it,
-	// like remove the nodes as "unnecessary" since they need to exist as children of
-	// this node (this node can't be a leaf anymore).
-
-	// This node is now a non-leaf, so shrink its area - it now denotes
-	// *occupied* space instead of free space. Its children spawn the resulting
-	// area of free space.
-	node->width = width;
-	node->height = height;
-	return node;
-}

CLB/src/RectangleBinPack.h

-/** @file RectangleBinPack.h
-	@author Jukka Jylänki
-
-	This work is released to Public Domain, do whatever you want with it.
-
-	@brief RectangleBinPack is a data structure for performing online rectangle bin packing.
-*/
-#ifndef RectangleBinPack_h
-#define RectangleBinPack_h
-
-namespace clb
-{
-	struct RefCountable
-	{
-	};
-}
-
-#define Ptr(T) T*
-
-/** Performs 'discrete online rectangle packing into a rectangular bin' by maintaining 
-	a binary tree of used and free rectangles of the bin. There are several variants
-	of bin packing problems, and this packer is characterized by:
-	- We're solving the 'online' version of the problem, which means that when we're adding
-	  a rectangle, we have no information of the sizes of the rectangles that are going to
-	  be packed after this one.
-	- We are packing rectangles that are not rotated. I.e. the algorithm will not flip
-	  a rectangle of (w,h) to be stored if it were a rectangle of size (h, w). There is no
-	  restriction conserning UV mapping why this couldn't be done to achieve better
-	  occupancy, but it's more work. Feel free to try it out.
-	- The packing is done in discrete integer coordinates and not in rational/real numbers (floats).
-
-	Internal memory usage is linear to the number of rectangles we've already packed.
-
-	For more information, see
-	- Rectangle packing: http://www.gamedev.net/community/forums/topic.asp?topic_id=392413
-	- Packing lightmaps: http://www.blackpawn.com/texts/lightmaps/default.html
-	
-	Idea: Instead of just picking the first free rectangle to insert the new rect into,
-	      check all free ones (or maintain a sorted order) and pick the one that minimizes 
-			the resulting leftover area. There is no real reason to maintain a tree - in fact 
-			it's just redundant structuring. We could as well have two lists - one for free 
-			rectangles and one for used rectangles. This method would be faster and might
-			even achieve a considerably better occupancy rate. */
-class RectangleBinPack
-{
-public:
-	/** A node of a binary tree. Each node represents a rectangular area of the texture
-	    we surface. Internal nodes store rectangles of used data, whereas leaf nodes track 
-	    rectangles of free space. All the rectangles stored in the tree are disjoint. */
-	struct Node : public clb::RefCountable
-	{
-		// Left and right child. We don't really distinguish which is which, so these could
-		// as well be child1 and child2.
-		Ptr(Node) left;
-		Ptr(Node) right;
-
-		// The top-left coordinate of the rectangle.
-		int x;
-		int y;
-
-		// The dimension of the rectangle.
-		int width;
-		int height;
-	};
-
-	/// Starts a new packing process to a bin of the given dimension.
-	void Init(int width, int height);
-
-	/// Inserts a new rectangle of the given size into the bin.
-	/** Running time is linear to the number of rectangles that have been already packed.
-		@return A pointer to the node that stores the newly added rectangle, or 0 
-			if it didn't fit. */
-	Node *Insert(int width, int height)
-	{
-		return Insert(&root, width, height);
-	}
-
-	/// Computes the ratio of used surface area.
-	float Occupancy() const;
-
-private:
-	Node root;
-
-	// The total size of the bin we started with.
-	int binWidth;
-	int binHeight;
-
-	/// @return The surface area used by the subtree rooted at node.
-	unsigned long UsedSurfaceArea(const Node &node) const;
-
-	/// Inserts a new rectangle in the subtree rooted at the given node.
-	Node *Insert(Node *node, int width, int height);
-};
-
-#endif

CLB/src/ShelfBinPack.cpp

+/** @file ShelfBinPack.cpp
+	@author Jukka Jylänki
+
+	@brief Implements different bin packer algorithms that use the SHELF data structure.
+
+	This work is released to Public Domain, do whatever you want with it.
+*/
+#include <utility>
+#include <iostream>
+
+#include <cassert>
+#include <cstring>
+
+#include "ShelfBinPack.h"
+
+using namespace std;
+
+ShelfBinPack::ShelfBinPack()
+:binWidth(0),
+binHeight(0),
+useWasteMap(false),
+currentY(0),
+usedSurfaceArea(0)
+{
+}
+
+ShelfBinPack::ShelfBinPack(int width, int height, bool useWasteMap)
+{
+	Init(width, height, useWasteMap);
+}
+
+void ShelfBinPack::Init(int width, int height, bool useWasteMap_)
+{
+	useWasteMap = useWasteMap_;
+	binWidth = width;
+	binHeight = height;
+
+	currentY = 0;
+	usedSurfaceArea = 0;
+
+	shelves.clear();
+	StartNewShelf(0);
+
+	if (useWasteMap)
+	{
+		wasteMap.Init(width, height);
+		wasteMap.GetFreeRectangles().clear();
+	}
+}
+
+bool ShelfBinPack::CanStartNewShelf(int height) const
+{
+	return shelves.back().startY + shelves.back().height + height <= binHeight;
+}
+
+void ShelfBinPack::StartNewShelf(int startingHeight)
+{
+	if (shelves.size() > 0)
+	{
+		assert(shelves.back().height != 0);
+		currentY += shelves.back().height;
+		
+		assert(currentY < binHeight);
+	}
+
+	Shelf shelf;
+	shelf.currentX = 0;
+	shelf.height = startingHeight;
+	shelf.startY = currentY;
+
+	assert(shelf.startY + shelf.height <= binHeight);
+	shelves.push_back(shelf);
+}
+
+bool ShelfBinPack::FitsOnShelf(const Shelf &shelf, int width, int height, bool canResize) const
+{
+	const int shelfHeight = canResize ? (binHeight - shelf.startY) : shelf.height;
+	if ((shelf.currentX + width <= binWidth && height <= shelfHeight) ||
+		(shelf.currentX + height <= binWidth && width <= shelfHeight))
+		return true;
+	else
+		return false;
+}
+
+void ShelfBinPack::RotateToShelf(const Shelf &shelf, int &width, int &height) const
+{	
+	// If the width > height and the long edge of the new rectangle fits vertically onto the current shelf,
+	// flip it. If the short edge is larger than the current shelf height, store
+	// the short edge vertically.
+	if ((width > height && width > binWidth - shelf.currentX) ||
+		(width > height && width < shelf.height) ||
+		(width < height && height > shelf.height && height <= binWidth - shelf.currentX))
+		swap(width, height);
+}
+
+void ShelfBinPack::AddToShelf(Shelf &shelf, int width, int height, Rect &newNode)
+{
+	assert(FitsOnShelf(shelf, width, height, true));
+
+	// Swap width and height if the rect fits better that way.
+	RotateToShelf(shelf, width, height);
+
+	// Add the rectangle to the shelf.
+	newNode.x = shelf.currentX;
+	newNode.y = shelf.startY;
+	newNode.width = width;
+	newNode.height = height;
+	shelf.usedRectangles.push_back(newNode);
+
+	// Advance the shelf end position horizontally.
+	shelf.currentX += width;
+	assert(shelf.currentX <= binWidth);
+
+	// Grow the shelf height.
+	shelf.height = max(shelf.height, height);
+	assert(shelf.height <= binHeight);
+
+	usedSurfaceArea += width * height;
+}
+
+Rect ShelfBinPack::Insert(int width, int height, ShelfChoiceHeuristic method)
+{
+	Rect newNode;
+
+	// First try to pack this rectangle into the waste map, if it fits.
+	if (useWasteMap)
+	{
+		newNode = wasteMap.Insert(width, height, true, GuillotineBinPack::RectBestShortSideFit, 
+			GuillotineBinPack::SplitMaximizeArea);
+		if (newNode.height != 0)
+		{
+			// Track the space we just used.
+			usedSurfaceArea += width * height;
+
+			return newNode;
+		}
+	}
+
+	switch(method)
+	{
+	case ShelfNextFit:		
+		if (FitsOnShelf(shelves.back(), width, height, true))
+		{
+			AddToShelf(shelves.back(), width, height, newNode);
+			return newNode;
+		}
+		break;
+	case ShelfFirstFit:		
+		for(size_t i = 0; i < shelves.size(); ++i)
+			if (FitsOnShelf(shelves[i], width, height, i == shelves.size()-1))
+			{
+				AddToShelf(shelves[i], width, height, newNode);
+				return newNode;
+			}
+		break;
+
+	case ShelfBestAreaFit:
+		{
+			// Best Area Fit rule: Choose the shelf with smallest remaining shelf area.
+			Shelf *bestShelf = 0;
+			unsigned long bestShelfSurfaceArea = (unsigned long)-1;
+			for(size_t i = 0; i < shelves.size(); ++i)
+			{
+				// Pre-rotate the rect onto the shelf here already so that the area fit computation
+				// is done correctly.
+				RotateToShelf(shelves[i], width, height);
+				if (FitsOnShelf(shelves[i], width, height, i == shelves.size()-1))
+				{
+					unsigned long surfaceArea = (binWidth - shelves[i].currentX) * shelves[i].height;
+					if (surfaceArea < bestShelfSurfaceArea)
+					{
+						bestShelf = &shelves[i];
+						bestShelfSurfaceArea = surfaceArea;
+					}
+				}
+			}
+
+			if (bestShelf)
+			{
+				AddToShelf(*bestShelf, width, height, newNode);
+				return newNode;
+			}
+		}
+		break;
+
+	case ShelfWorstAreaFit:
+		{
+			// Worst Area Fit rule: Choose the shelf with smallest remaining shelf area.
+			Shelf *bestShelf = 0;
+			int bestShelfSurfaceArea = -1;
+			for(size_t i = 0; i < shelves.size(); ++i)
+			{
+				// Pre-rotate the rect onto the shelf here already so that the area fit computation
+				// is done correctly.
+				RotateToShelf(shelves[i], width, height);
+				if (FitsOnShelf(shelves[i], width, height, i == shelves.size()-1))
+				{
+					int surfaceArea = (binWidth - shelves[i].currentX) * shelves[i].height;
+					if (surfaceArea > bestShelfSurfaceArea)
+					{
+						bestShelf = &shelves[i];
+						bestShelfSurfaceArea = surfaceArea;
+					}
+				}
+			}
+
+			if (bestShelf)
+			{
+				AddToShelf(*bestShelf, width, height, newNode);
+				return newNode;
+			}
+		}
+		break;
+
+	case ShelfBestHeightFit:
+		{
+			// Best Height Fit rule: Choose the shelf with best-matching height.
+			Shelf *bestShelf = 0;
+			int bestShelfHeightDifference = 0x7FFFFFFF;
+			for(size_t i = 0; i < shelves.size(); ++i)
+			{
+				// Pre-rotate the rect onto the shelf here already so that the height fit computation
+				// is done correctly.
+				RotateToShelf(shelves[i], width, height);
+				if (FitsOnShelf(shelves[i], width, height, i == shelves.size()-1))
+				{
+					int heightDifference = max(shelves[i].height - height, 0);
+					assert(heightDifference >= 0);
+
+					if (heightDifference < bestShelfHeightDifference)
+					{
+						bestShelf = &shelves[i];
+						bestShelfHeightDifference = heightDifference;
+					}
+				}
+			}
+
+			if (bestShelf)
+			{
+				AddToShelf(*bestShelf, width, height, newNode);
+				return newNode;
+			}
+		}
+		break;
+
+	case ShelfBestWidthFit:
+		{
+			// Best Width Fit rule: Choose the shelf with smallest remaining shelf width.
+			Shelf *bestShelf = 0;
+			int bestShelfWidthDifference = 0x7FFFFFFF;
+			for(size_t i = 0; i < shelves.size(); ++i)
+			{
+				// Pre-rotate the rect onto the shelf here already so that the height fit computation
+				// is done correctly.
+				RotateToShelf(shelves[i], width, height);
+				if (FitsOnShelf(shelves[i], width, height, i == shelves.size()-1))
+				{
+					int widthDifference = binWidth - shelves[i].currentX - width;
+					assert(widthDifference >= 0);
+
+					if (widthDifference < bestShelfWidthDifference)
+					{
+						bestShelf = &shelves[i];
+						bestShelfWidthDifference = widthDifference;
+					}
+				}
+			}
+
+			if (bestShelf)
+			{
+				AddToShelf(*bestShelf, width, height, newNode);
+				return newNode;
+			}
+		}
+		break;
+
+	case ShelfWorstWidthFit:
+		{
+			// Worst Width Fit rule: Choose the shelf with smallest remaining shelf width.
+			Shelf *bestShelf = 0;
+			int bestShelfWidthDifference = -1;
+			for(size_t i = 0; i < shelves.size(); ++i)
+			{
+				// Pre-rotate the rect onto the shelf here already so that the height fit computation
+				// is done correctly.
+				RotateToShelf(shelves[i], width, height);
+				if (FitsOnShelf(shelves[i], width, height, i == shelves.size()-1))
+				{
+					int widthDifference = binWidth - shelves[i].currentX - width;
+					assert(widthDifference >= 0);
+
+					if (widthDifference > bestShelfWidthDifference)
+					{
+						bestShelf = &shelves[i];
+						bestShelfWidthDifference = widthDifference;
+					}
+				}
+			}
+
+			if (bestShelf)
+			{
+				AddToShelf(*bestShelf, width, height, newNode);
+				return newNode;
+			}
+		}
+		break;
+
+	}
+
+	// The rectangle did not fit on any of the shelves. Open a new shelf.
+
+	// Flip the rectangle so that the long side is horizontal.
+	if (width < height && height <= binWidth)
+		swap(width, height);
+
+	if (CanStartNewShelf(height))
+	{
+		if (useWasteMap)
+			MoveShelfToWasteMap(shelves.back());
+		StartNewShelf(height);
+		assert(FitsOnShelf(shelves.back(), width, height, true));
+		AddToShelf(shelves.back(), width, height, newNode);
+		return newNode;
+	}
+/*
+	///\todo This is problematic: If we couldn't start a new shelf - should we give up
+	///      and move all the remaining space of the bin for the waste map to track,
+	///      or should we just wait if the next rectangle would fit better? For now,
+	///      don't add the leftover space to the waste map. 
+	else if (useWasteMap)
+	{
+		assert(binHeight - shelves.back().startY >= shelves.back().height);
+		shelves.back().height = binHeight - shelves.back().startY;
+		if (shelves.back().height > 0)
+			MoveShelfToWasteMap(shelves.back());
+
+		// Try to pack the rectangle again to the waste map.
+		GuillotineBinPack::Node node = wasteMap.Insert(width, height, true, 1, 3);
+		if (node.height != 0)
+		{
+			newNode.x = node.x;
+			newNode.y = node.y;
+			newNode.width = node.width;
+			newNode.height = node.height;
+			return newNode;
+		}
+	}
+*/
+
+	// The rectangle didn't fit.
+	memset(&newNode, 0, sizeof(Rect));