Skip to content

Instantly share code, notes, and snippets.

@claus

claus/MaxRectsBinPack.as

Created Aug 22, 2010
Star
Embed
What would you like to do?
Learn more about clone URLs
Download ZIP
Raw
MaxRectsBinPack.as
/*
Implements different bin packer algorithms that use the MAXRECTS data structure.
See http://clb.demon.fi/projects/even-more-rectangle-bin-packing
Author: Jukka Jylänki
- Original
Author: Claus Wahlers
- Ported to ActionScript3
This work is released to Public Domain, do whatever you want with it.
*/
package
{
import flash.display.Shape;
import flash.utils.getTimer;
import flash.events.Event;
import flash.display.DisplayObject;
import flash.events.EventDispatcher;
import flash.geom.Rectangle;
public class MaxRectsBinPack extends EventDispatcher
{
public static const METHOD_RECT_BEST_SHORT_SIDE_FIT:uint = 1;
public static const METHOD_RECT_BOTTOM_LEFT_RULE:uint = 2;
public static const METHOD_RECT_CONTACT_POINT_RULE:uint = 3;
public static const METHOD_RECT_BEST_LONG_SIDE_FIT:uint = 4;
public static const METHOD_RECT_BEST_AREA_FIT:uint = 5;
public var timeLimit:int = 25;
public var allowFlip:Boolean = false;
public var usedRectangles:Vector.<Rectangle>;
public var freeRectangles:Vector.<Rectangle>;
protected var binWidth:Number = 0;
protected var binHeight:Number = 0;
protected var enterFrameProvider:Shape;
protected var tmpRects:Vector.<Rectangle>;
protected var tmpMethod:uint;
public function MaxRectsBinPack(width:Number, height:Number) {
enterFrameProvider = new Shape();
init(width, height);
}
public function init(width:Number, height:Number):void {
binWidth = width;
binHeight = height;
usedRectangles = new Vector.<Rectangle>();
freeRectangles = new Vector.<Rectangle>();
freeRectangles.push(new Rectangle(0, 0, width, height));
}
public function insert(width:Number, height:Number, method:uint):Rectangle {
if(enterFrameProvider.hasEventListener(Event.ENTER_FRAME)) {
throw(new Error("Bulk insert in progress."));
}
var newNode:Rectangle;
switch(method) {
case METHOD_RECT_BEST_SHORT_SIDE_FIT:
newNode = findPositionForNewNodeBestShortSideFit(width, height);
break;
case METHOD_RECT_BOTTOM_LEFT_RULE:
newNode = findPositionForNewNodeBottomLeft(width, height);
break;
case METHOD_RECT_CONTACT_POINT_RULE:
newNode = findPositionForNewNodeContactPoint(width, height);
break;
case METHOD_RECT_BEST_LONG_SIDE_FIT:
newNode = findPositionForNewNodeBestLongSideFit(width, height);
break;
case METHOD_RECT_BEST_AREA_FIT:
newNode = findPositionForNewNodeBestAreaFit(width, height);
break;
default:
throw(new Error("Invalid method."));
break;
}
if (newNode.height == 0) {
return newNode;
}
var numRectanglesToProcess:uint = freeRectangles.length;
for(var i:uint = 0; i < numRectanglesToProcess; ++i) {
if (splitFreeNode(freeRectangles[i], newNode)) {
freeRectangles.splice(i, 1);
--numRectanglesToProcess;
--i;
}
}
pruneFreeList();
usedRectangles.push(newNode);
return newNode;
}
public function insertBulk(rects:Vector.<Rectangle>, method:uint):void {
if(enterFrameProvider.hasEventListener(Event.ENTER_FRAME)) {
throw(new Error("Bulk insert in progress."));
}
tmpRects = rects;
tmpMethod = method;
enterFrameProvider.addEventListener(Event.ENTER_FRAME, insertBulkWorker);
insertBulkWorker(null);
}
public function insertBulkWorker(event:Event):void {
var t:int = getTimer();
while(tmpRects.length > 0) {
if(getTimer() - t < timeLimit) {
var bestScore:Score = new Score();
var bestRectIndex:int = -1;
var bestNode:Rectangle = rectFactory();
for(var i:uint = 0; i < tmpRects.length; ++i) {
var score:Score = new Score();
var newNode:Rectangle = scoreRect(tmpRects[i].width, tmpRects[i].height, tmpMethod, score);
if (score.score1 < bestScore.score1 || (score.score1 == bestScore.score1 && score.score2 < bestScore.score2)) {
bestScore.score1 = score.score1;
bestScore.score2 = score.score2;
bestNode = newNode;
bestRectIndex = i;
}
}
if (bestRectIndex == -1) {
// Rect didn't fit, break out of the loop and terminate
break;
}
placeRect(bestNode);
tmpRects.splice(bestRectIndex, 1);
} else {
// time limit exceeded, break out of the function, wait for next enterframe
trace((getTimer() - t) + "ms");
dispatchEvent(new Event("progress"));
return;
}
}
tmpRects = null;
enterFrameProvider.removeEventListener(Event.ENTER_FRAME, insertBulkWorker);
dispatchEvent(new Event("complete"));
}
protected function scoreRect(width:Number, height:Number, method:uint, score:Score):Rectangle {
var newNode:Rectangle = rectFactory();
score.score1 = Number.MAX_VALUE;
score.score2 = Number.MAX_VALUE;
switch(method) {
case METHOD_RECT_BEST_SHORT_SIDE_FIT:
newNode = findPositionForNewNodeBestShortSideFit(width, height, score);
break;
case METHOD_RECT_BOTTOM_LEFT_RULE:
newNode = findPositionForNewNodeBottomLeft(width, height, score);
break;
case METHOD_RECT_CONTACT_POINT_RULE:
newNode = findPositionForNewNodeContactPoint(width, height, score);
// Reverse since we are minimizing, but for contact point score bigger is better.
score.score1 = -score.score1;
break;
case METHOD_RECT_BEST_LONG_SIDE_FIT:
newNode = findPositionForNewNodeBestLongSideFit(width, height, score);
break;
case METHOD_RECT_BEST_AREA_FIT:
newNode = findPositionForNewNodeBestAreaFit(width, height, score);
break;
default:
throw(new Error("Invalid method."));
break;
}
// Cannot fit the current rectangle.
if (newNode.isEmpty()) {
score.score1 = Number.MAX_VALUE;
score.score2 = Number.MAX_VALUE;
}
return newNode;
}
protected function placeRect(node:Rectangle):void {
var numRectanglesToProcess:uint = freeRectangles.length;
for(var i:uint = 0; i < numRectanglesToProcess; ++i) {
if (splitFreeNode(freeRectangles[i], node)) {
freeRectangles.splice(i, 1);
--numRectanglesToProcess;
--i;
}
}
pruneFreeList();
usedRectangles.push(node);
}
protected function findPositionForNewNodeBestShortSideFit(width:Number, height:Number, score:Score = null):Rectangle {
if(score == null) {
score = new Score();
}
score.score1 = Number.MAX_VALUE;
var bestNode:Rectangle = rectFactory();
for(var i:uint = 0; i < freeRectangles.length; ++i) {
// Try to place the rectangle in upright (non-flipped) orientation.
if (freeRectangles[i].width >= width && freeRectangles[i].height >= height) {
var leftoverHoriz:Number = Math.abs(freeRectangles[i].width - width);
var leftoverVert:Number = Math.abs(freeRectangles[i].height - height);
var shortSideFit:Number = Math.min(leftoverHoriz, leftoverVert);
var longSideFit:Number = Math.max(leftoverHoriz, leftoverVert);
if (shortSideFit < score.score1 || (shortSideFit == score.score1 && longSideFit < score.score2)) {
bestNode.x = freeRectangles[i].x;
bestNode.y = freeRectangles[i].y;
bestNode.width = width;
bestNode.height = height;
score.score1 = shortSideFit;
score.score2 = longSideFit;
}
}
// Try to place the rectangle in flipped orientation.
if(allowFlip && height != width) {
if (freeRectangles[i].width >= height && freeRectangles[i].height >= width) {
var flippedLeftoverHoriz:Number = Math.abs(freeRectangles[i].width - height);
var flippedLeftoverVert:Number = Math.abs(freeRectangles[i].height - width);
var flippedShortSideFit:Number = Math.min(flippedLeftoverHoriz, flippedLeftoverVert);
var flippedLongSideFit:Number = Math.max(flippedLeftoverHoriz, flippedLeftoverVert);
if (flippedShortSideFit < score.score1 || (flippedShortSideFit == score.score1 && flippedLongSideFit < score.score2)) {
bestNode.x = freeRectangles[i].x;
bestNode.y = freeRectangles[i].y;
bestNode.width = height;
bestNode.height = width;
score.score1 = flippedShortSideFit;
score.score2 = flippedLongSideFit;
}
}
}
}
return bestNode;
}
protected function findPositionForNewNodeBottomLeft(width:Number, height:Number, score:Score = null):Rectangle {
if(score == null) {
score = new Score();
}
score.score1 = Number.MAX_VALUE;
var topSideY:Number;
var bestNode:Rectangle = rectFactory();
for(var i:uint = 0; i < freeRectangles.length; ++i) {
// Try to place the rectangle in upright (non-flipped) orientation.
if (freeRectangles[i].width >= width && freeRectangles[i].height >= height) {
topSideY = freeRectangles[i].y + height;
if (topSideY < score.score1 || (topSideY == score.score1 && freeRectangles[i].x < score.score2)) {
bestNode.x = freeRectangles[i].x;
bestNode.y = freeRectangles[i].y;
bestNode.width = width;
bestNode.height = height;
score.score1 = topSideY;
score.score2 = freeRectangles[i].x;
}
}
if(allowFlip && height != width) {
if (freeRectangles[i].width >= height && freeRectangles[i].height >= width) {
topSideY = freeRectangles[i].y + width;
if (topSideY < score.score1 || (topSideY == score.score1 && freeRectangles[i].x < score.score2)) {
bestNode.x = freeRectangles[i].x;
bestNode.y = freeRectangles[i].y;
bestNode.width = height;
bestNode.height = width;
score.score1 = topSideY;
score.score2 = freeRectangles[i].x;
}
}
}
}
return bestNode;
}
protected function findPositionForNewNodeContactPoint(width:Number, height:Number, score:Score = null):Rectangle {
if(score == null) {
score = new Score();
}
score.score1 = -1;
var bestContactScore:Number;
var bestNode:Rectangle = rectFactory();
for(var i:uint = 0; i < freeRectangles.length; ++i) {
// Try to place the rectangle in upright (non-flipped) orientation.
if (freeRectangles[i].width >= width && freeRectangles[i].height >= height) {
bestContactScore = contactPointScoreNode(freeRectangles[i].x, freeRectangles[i].y, width, height);
if (bestContactScore > score.score1) {
bestNode.x = freeRectangles[i].x;
bestNode.y = freeRectangles[i].y;
bestNode.width = width;
bestNode.height = height;
score.score1 = bestContactScore;
}
}
if(allowFlip && height != width) {
if (freeRectangles[i].width >= height && freeRectangles[i].height >= width) {
bestContactScore = contactPointScoreNode(freeRectangles[i].x, freeRectangles[i].y, width, height);
if (bestContactScore > score.score1) {
bestNode.x = freeRectangles[i].x;
bestNode.y = freeRectangles[i].y;
bestNode.width = height;
bestNode.height = width;
score.score1 = bestContactScore;
}
}
}
}
return bestNode;
}
protected function findPositionForNewNodeBestLongSideFit(width:Number, height:Number, score:Score = null):Rectangle {
if(score == null) {
score = new Score();
}
score.score2 = Number.MAX_VALUE;
var shortSideFit:Number, longSideFit:Number;
var leftoverHoriz:Number, leftoverVert:Number;
var bestNode:Rectangle = rectFactory();
for(var i:uint = 0; i < freeRectangles.length; ++i) {
// Try to place the rectangle in upright (non-flipped) orientation.
if (freeRectangles[i].width >= width && freeRectangles[i].height >= height) {
leftoverHoriz = Math.abs(freeRectangles[i].width - width);
leftoverVert = Math.abs(freeRectangles[i].height - height);
shortSideFit = Math.min(leftoverHoriz, leftoverVert);
longSideFit = Math.max(leftoverHoriz, leftoverVert);
if (longSideFit < score.score2 || (longSideFit == score.score2 && shortSideFit < score.score1)) {
bestNode.x = freeRectangles[i].x;
bestNode.y = freeRectangles[i].y;
bestNode.width = width;
bestNode.height = height;
score.score1 = shortSideFit;
score.score2 = longSideFit;
}
}
if(allowFlip && height != width) {
if (freeRectangles[i].width >= height && freeRectangles[i].height >= width) {
leftoverHoriz = Math.abs(freeRectangles[i].width - height);
leftoverVert = Math.abs(freeRectangles[i].height - width);
shortSideFit = Math.min(leftoverHoriz, leftoverVert);
longSideFit = Math.max(leftoverHoriz, leftoverVert);
if (longSideFit < score.score2 || (longSideFit == score.score2 && shortSideFit < score.score1)) {
bestNode.x = freeRectangles[i].x;
bestNode.y = freeRectangles[i].y;
bestNode.width = height;
bestNode.height = width;
score.score1 = shortSideFit;
score.score2 = longSideFit;
}
}
}
}
return bestNode;
}
protected function findPositionForNewNodeBestAreaFit(width:Number, height:Number, score:Score = null):Rectangle {
if(score == null) {
score = new Score();
}
score.score1 = Number.MAX_VALUE;
var areaFit:Number;
var shortSideFit:Number;
var leftoverHoriz:Number, leftoverVert:Number;
var bestNode:Rectangle = rectFactory();
for(var i:uint = 0; i < freeRectangles.length; ++i) {
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) {
leftoverHoriz = Math.abs(freeRectangles[i].width - width);
leftoverVert = Math.abs(freeRectangles[i].height - height);
shortSideFit = Math.min(leftoverHoriz, leftoverVert);
if (areaFit < score.score1 || (areaFit == score.score1 && shortSideFit < score.score2)) {
bestNode.x = freeRectangles[i].x;
bestNode.y = freeRectangles[i].y;
bestNode.width = width;
bestNode.height = height;
score.score1 = areaFit;
score.score2 = shortSideFit;
}
}
if(allowFlip && height != width) {
if (freeRectangles[i].width >= height && freeRectangles[i].height >= width) {
leftoverHoriz = Math.abs(freeRectangles[i].width - height);
leftoverVert = Math.abs(freeRectangles[i].height - width);
shortSideFit = Math.min(leftoverHoriz, leftoverVert);
if (areaFit < score.score1 || (areaFit == score.score1 && shortSideFit < score.score2)) {
bestNode.x = freeRectangles[i].x;
bestNode.y = freeRectangles[i].y;
bestNode.width = height;
bestNode.height = width;
score.score1 = areaFit;
score.score2 = shortSideFit;
}
}
}
}
return bestNode;
}
protected function contactPointScoreNode(x:Number, y:Number, width:Number, height:Number):Number {
var score:Number = 0;
if (x == 0 || x + width == binWidth) {
score += height;
}
if (y == 0 || y + height == binHeight) {
score += width;
}
for(var i:uint = 0; i < usedRectangles.length; ++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;
}
// Returns 0 if the two intervals i1 and i2 are disjoint,
// or the length of their overlap otherwise.
protected function commonIntervalLength(i1start:Number, i1end:Number, i2start:Number, i2end:Number):Number {
if (i1end < i2start || i2end < i1start) {
return 0;
}
return Math.min(i1end, i2end) - Math.max(i1start, i2start);
}
protected function splitFreeNode(freeNode:Rectangle, usedNode:Rectangle):Boolean {
var newNode:Rectangle;
// 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) {
newNode = freeNode.clone();
newNode.height = usedNode.y - newNode.y;
freeRectangles.push(newNode);
}
// New node at the bottom side of the used node.
if (usedNode.y + usedNode.height < freeNode.y + freeNode.height) {
newNode = freeNode.clone();
newNode.y = usedNode.y + usedNode.height;
newNode.height = freeNode.y + freeNode.height - (usedNode.y + usedNode.height);
freeRectangles.push(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) {
newNode = freeNode.clone();
newNode.width = usedNode.x - newNode.x;
freeRectangles.push(newNode);
}
// New node at the right side of the used node.
if (usedNode.x + usedNode.width < freeNode.x + freeNode.width) {
newNode = freeNode.clone();
newNode.x = usedNode.x + usedNode.width;
newNode.width = freeNode.x + freeNode.width - (usedNode.x + usedNode.width);
freeRectangles.push(newNode);
}
}
return true;
}
protected function pruneFreeList():void {
// Go through each pair and remove any rectangle that is redundant.
for(var i:uint = 0; i < freeRectangles.length; ++i) {
for(var j:uint = i + 1; j < freeRectangles.length; ++j) {
if (freeRectangles[j].containsRect(freeRectangles[i])) {
freeRectangles.splice(i, 1);
--i;
break;
}
if (freeRectangles[i].containsRect(freeRectangles[j])) {
freeRectangles.splice(j, 1);
--j;
}
}
}
}
protected function rectFactory():Rectangle {
return new Rectangle();
}
}
}
class Score
{
public var score1:Number;
public var score2:Number;
public function Score(score1:Number = Number.MAX_VALUE, score2:Number = Number.MAX_VALUE)
{
this.score1 = score1;
this.score2 = score2;
}
}
Raw
Test.as
package
{
import flash.display.Sprite;
import flash.events.Event;
import flash.geom.Rectangle;
[SWF(backgroundColor="#ffffff", frameRate="31", width="512", height="512")]
public class Test extends Sprite
{
private var packer:MaxRectsBinPack;
public function Test()
{
packer = new MaxRectsBinPack(512, 512);
packer.addEventListener("progress", progressHandler);
packer.addEventListener("complete", completeHandler);
packer.allowFlip = false;
var rects:Vector.<Rectangle> = new Vector.<Rectangle>();
for(var i:uint = 0; i < 100; i++) {
rects.push(new Rectangle(
0,
0,
Math.round(10 + Math.random() * 90),
Math.round(10 + Math.random() * 90)
));
}
packer.insertBulk(rects, MaxRectsBinPack.METHOD_RECT_BEST_AREA_FIT);
}
private function progressHandler(event:Event):void {
drawResults();
}
private function completeHandler(event:Event):void {
drawResults();
}
private function drawResults():void {
graphics.clear();
for each(var usedRect:Rectangle in packer.usedRectangles) {
drawRect(usedRect, 0xff0000);
}
for each(var freeRect:Rectangle in packer.freeRectangles) {
drawRect(freeRect, 0xdddddd);
}
}
private function drawRect(rect:Rectangle, color:uint):void {
if(!rect.isEmpty()) {
graphics.lineStyle(1, 0);
graphics.beginFill(color);
graphics.drawRect(rect.x, rect.y, rect.width, rect.height);
graphics.endFill();
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment