早上，在微博发现一条信息，关于MaxRects算法的，@杜增强DzQ 移植的关于AS3版本的MaxRects算法，具体地址是：http://www.duzengqiang.com/blog/post/971.html
/*
Based on the Public Domain MaxRectanglesBinPack.cpp source by Jukka Jylänki
https://github.com/juj/RectangleBinPack/
Based on C# port by Sven Magnus
http://unifycommunity.com/wiki/index.php?title=MaxRectanglesBinPack
Ported to ActionScript3 by DUZENGQIANG
http://www.duzengqiang.com/blog/post/971.html
This version is also public domain - do whatever you want with it.
*/
package
{
import flash.geom.Rectangle;
/**
* MaxRectanglesBinPack
* @author DUZENGQIANG
* @date Jun 7, 2012
* @version 1.0
* SinaMicroBlog: http://weibo.com/duzengqiang
* blog: http://www.duzengqiang.com
*/
public class MaxRectsBinPack
{
public var binWidth:int = 0;
public var binHeight:int = 0;
public var allowRotations:Boolean = false;
public var usedRectangles:Vector. = new Vector.();
public var freeRectangles:Vector. = new Vector.();
private var score1:int = 0; // Unused in this function. We don't need to know the score after finding the position.
private var score2:int = 0;
private var bestShortSideFit:int;
private var bestLongSideFit:int;
public function MaxRectsBinPack( width:int, height:int, rotations:Boolean = true) {
init(width, height, rotations);
}
private function init(width:int, height:int, rotations:Boolean = true):void
{
if( count(width) % 1 != 0 ||count(height) % 1 != 0)
throw new Error("Must be 2,4,8,16,32,...512,1024,...");
binWidth = width;
binHeight = height;
allowRotations = rotations;
var n:Rectangle = new Rectangle();
n.x = 0;
n.y = 0;
n.width = width;
n.height = height;
usedRectangles.length = 0;
freeRectangles.length = 0;
freeRectangles.push( n );
}
private function count(n:Number):Number
{
if( n >= 2 )
return count(n / 2);
return n;
}
/**
* Insert a new Rectangle
* @param width
* @param height
* @param method
* @return
*
*/
public function insert(width:int, height:int, method:int):Rectangle {
var newNode:Rectangle = new Rectangle();
score1 = 0;
score2 = 0;
switch(method) {
case FreeRectangleChoiceHeuristic.BestShortSideFit:
newNode = findPositionForNewNodeBestShortSideFit(width, height);
break;
case FreeRectangleChoiceHeuristic.BottomLeftRule:
newNode = findPositionForNewNodeBottomLeft(width, height, score1, score2);
break;
case FreeRectangleChoiceHeuristic.ContactPointRule:
newNode = findPositionForNewNodeContactPoint(width, height, score1);
break;
case FreeRectangleChoiceHeuristic.BestLongSideFit:
newNode = findPositionForNewNodeBestLongSideFit(width, height, score2, score1);
break;
case FreeRectangleChoiceHeuristic.BestAreaFit:
newNode = findPositionForNewNodeBestAreaFit(width, height, score1, score2);
break;
}
if (newNode.height == 0)
return newNode;
placeRectangle(newNode);
trace(newNode);
return newNode;
}
public function insert2( Rectangles:Vector., dst:Vector., method:int):void {
dst.length = 0;
while(Rectangles.length > 0) {
var bestScore1:int = int.MAX_VALUE;
var bestScore2:int = int.MAX_VALUE;
var bestRectangleIndex:int = -1;
var bestNode:Rectangle = new Rectangle();
for(var i:int = 0; i i) {
var score1:int = 0;
var score2:int = 0;
var newNode:Rectangle = scoreRectangle(Rectangles[i].width, Rectangles[i].height, method, score1, score2);
if (score1 bestScore2)) {
bestScore1 = score1;
bestScore2 = score2;
bestNode = newNode;
bestRectangleIndex = i;
}
}
if (bestRectangleIndex == -1)
return;
placeRectangle(bestNode);
Rectangles.splice(bestRectangleIndex,1);
}
}
private function placeRectangle(node:Rectangle):void {
var numRectanglesToProcess:int = freeRectangles.length;
for(var i:int = 0; i ) {
if (splitFreeNode(freeRectangles[i], node)) {
freeRectangles.splice(i,1);
--i;
--numRectanglesToProcess;
}
}
pruneFreeList();
usedRectangles.push(node);
}
private function scoreRectangle( width:int, height:int, method:int,
score1:int, score2:int):Rectangle {
var newNode:Rectangle = new Rectangle();
score1 = int.MAX_VALUE;
score2 = int.MAX_VALUE;
switch(method) {
case FreeRectangleChoiceHeuristic.BestShortSideFit:
newNode = findPositionForNewNodeBestShortSideFit(width, height);
break;
case FreeRectangleChoiceHeuristic.BottomLeftRule:
newNode = findPositionForNewNodeBottomLeft(width, height, score1,score2);
break;
case FreeRectangleChoiceHeuristic.ContactPointRule:
newNode = findPositionForNewNodeContactPoint(width, height, score1);
// todo: reverse
score1 = -score1; // Reverse since we are minimizing, but for contact point score bigger is better.
break;
case FreeRectangleChoiceHeuristic.BestLongSideFit:
newNode = findPositionForNewNodeBestLongSideFit(width, height, score2, score1);
break;
case FreeRectangleChoiceHeuristic.BestAreaFit:
newNode = findPositionForNewNodeBestAreaFit(width, height, score1, score2);
break;
}
// Cannot fit the current Rectangle.
if (newNode.height == 0) {
score1 = int.MAX_VALUE;
score2 = int.MAX_VALUE;
}
return newNode;
}
/// Computes the ratio of used surface area.
private function occupancy():Number {
var usedSurfaceArea:Number = 0;
for(var i:int = 0; i )
usedSurfaceArea += usedRectangles[i].width * usedRectangles[i].height;
return usedSurfaceArea / (binWidth * binHeight);
}
private function findPositionForNewNodeBottomLeft(width:int, height:int,
bestY:int, bestX:int):Rectangle {
var bestNode:Rectangle = new Rectangle();
//memset(bestNode, 0, sizeof(Rectangle));
bestY = int.MAX_VALUE;
var rect:Rectangle;
var topSideY:int;
for(var i:int = 0; i ) {
rect = freeRectangles[i];
// Try to place the Rectangle in upright (non-flipped) orientation.
if (rect.width >= width && rect.height >= height) {
topSideY = rect.y + height;
if (topSideY bestX)) {
bestNode.x = rect.x;
bestNode.y = rect.y;
bestNode.width = width;
bestNode.height = height;
bestY = topSideY;
bestX = rect.x;
}
}
if (allowRotations && rect.width >= height && rect.height >= width) {
topSideY = rect.y + width;
if (topSideY bestX)) {
bestNode.x = rect.x;
bestNode.y = rect.y;
bestNode.width = height;
bestNode.height = width;
bestY = topSideY;
bestX = rect.x;
}
}
}
return bestNode;
}
private function findPositionForNewNodeBestShortSideFit(width:int, height:int):Rectangle {
var bestNode:Rectangle = new Rectangle();
//memset(&bestNode, 0, sizeof(Rectangle));
bestShortSideFit = int.MAX_VALUE;
bestLongSideFit = score2;
var rect:Rectangle;
var leftoverHoriz:int;
var leftoverVert:int;
var shortSideFit:int;
var longSideFit:int;
for(var i:int = 0; i ) {
rect = freeRectangles[i];
// Try to place the Rectangle in upright (non-flipped) orientation.
if (rect.width >= width && rect.height >= height) {
leftoverHoriz = Math.abs(rect.width - width);
leftoverVert = Math.abs(rect.height - height);
shortSideFit = Math.min(leftoverHoriz, leftoverVert);
longSideFit = Math.max(leftoverHoriz, leftoverVert);
if (shortSideFit bestLongSideFit)) {
bestNode.x = rect.x;
bestNode.y = rect.y;
bestNode.width = width;
bestNode.height = height;
bestShortSideFit = shortSideFit;
bestLongSideFit = longSideFit;
}
}
var flippedLeftoverHoriz:Number;
var flippedLeftoverVert:Number;
var flippedShortSideFit:Number;
var flippedLongSideFit:Number;
if (allowRotations && rect.width >= height && rect.height >= width) {
flippedLeftoverHoriz = Math.abs(rect.width - height);
flippedLeftoverVert = Math.abs(rect.height - width);
flippedShortSideFit = Math.min(flippedLeftoverHoriz, flippedLeftoverVert);
flippedLongSideFit = Math.max(flippedLeftoverHoriz, flippedLeftoverVert);
if (flippedShortSideFit bestLongSideFit)) {
bestNode.x = rect.x;
bestNode.y = rect.y;
bestNode.width = height;
bestNode.height = width;
bestShortSideFit = flippedShortSideFit;
bestLongSideFit = flippedLongSideFit;
}
}
}
return bestNode;
}
private function findPositionForNewNodeBestLongSideFit(width:int, height:int, bestShortSideFit:int, bestLongSideFit:int):Rectangle {
var bestNode:Rectangle = new Rectangle();
//memset(&bestNode, 0, sizeof(Rectangle));
bestLOngSideFit= int.MAX_VALUE;
var rect:Rectangle;
var leftoverHoriz:int;
var leftoverVert:int;
var shortSideFit:int;
var longSideFit:int;
for(var i:int = 0; i ) {
rect = freeRectangles[i];
// Try to place the Rectangle in upright (non-flipped) orientation.
if (rect.width >= width && rect.height >= height) {
leftoverHoriz = Math.abs(rect.width - width);
leftoverVert = Math.abs(rect.height - height);
shortSideFit = Math.min(leftoverHoriz, leftoverVert);
longSideFit = Math.max(leftoverHoriz, leftoverVert);
if (longSideFit bestShortSideFit)) {
bestNode.x = rect.x;
bestNode.y = rect.y;
bestNode.width = width;
bestNode.height = height;
bestShortSideFit = shortSideFit;
bestLongSideFit = longSideFit;
}
}
if (allowRotations && rect.width >= height && rect.height >= width) {
leftoverHoriz = Math.abs(rect.width - height);
leftoverVert = Math.abs(rect.height - width);
shortSideFit = Math.min(leftoverHoriz, leftoverVert);
longSideFit = Math.max(leftoverHoriz, leftoverVert);
if (longSideFit bestShortSideFit)) {
bestNode.x = rect.x;
bestNode.y = rect.y;
bestNode.width = height;
bestNode.height = width;
bestShortSideFit = shortSideFit;
bestLongSideFit = longSideFit;
}
}
}
trace(bestNode);
return bestNode;
}
private function findPositionForNewNodeBestAreaFit(width:int, height:int, bestAreaFit:int, bestShortSideFit:int):Rectangle {
var bestNode:Rectangle = new Rectangle();
//memset(&bestNode, 0, sizeof(Rectangle));
bestAreaFit = int.MAX_VALUE;
var rect:Rectangle;
var leftoverHoriz:int;
var leftoverVert:int;
var shortSideFit:int;
var areaFit:int;
for(var i:int = 0; i ) {
rect = freeRectangles[i];
areaFit = rect.width * rect.height - width * height;
// Try to place the Rectangle in upright (non-flipped) orientation.
if (rect.width >= width && rect.height >= height) {
leftoverHoriz = Math.abs(rect.width - width);
leftoverVert = Math.abs(rect.height - height);
shortSideFit = Math.min(leftoverHoriz, leftoverVert);
if (areaFit bestShortSideFit)) {
bestNode.x = rect.x;
bestNode.y = rect.y;
bestNode.width = width;
bestNode.height = height;
bestShortSideFit = shortSideFit;
bestAreaFit = areaFit;
}
}
if (allowRotations && rect.width >= height && rect.height >= width) {
leftoverHoriz = Math.abs(rect.width - height);
leftoverVert = Math.abs(rect.height - width);
shortSideFit = Math.min(leftoverHoriz, leftoverVert);
if (areaFit bestShortSideFit)) {
bestNode.x = rect.x;
bestNode.y = rect.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.
private function commonIntervalLength(i1start:int, i1end:int, i2start:int, i2end:int):int {
if (i1end i1start)
return 0;
return Math.min(i1end, i2end) - Math.max(i1start, i2start);
}
private function contactPointScoreNode(x:int, y:int, width:int, height:int):int {
var score:int = 0;
if (x == 0 || x + width == binWidth)
score += height;
if (y == 0 || y + height == binHeight)
score += width;
var rect:Rectangle;
for(var i:int = 0; i ) {
rect = usedRectangles[i];
if (rect.x == x + width || rect.x + rect.width == x)
score += commonIntervalLength(rect.y, rect.y + rect.height, y, y + height);
if (rect.y == y + height || rect.y + rect.height == y)
score += commonIntervalLength(rect.x, rect.x + rect.width, x, x + width);
}
return score;
}
private function findPositionForNewNodeContactPoint(width:int, height:int, bestContactScore:int):Rectangle {
var bestNode:Rectangle = new Rectangle();
//memset(&bestNode, 0, sizeof(Rectangle));
bestContactScore = -1;
var rect:Rectangle;
var score:int;
for(var i:int = 0; i ) {
rect = freeRectangles[i];
// Try to place the Rectangle in upright (non-flipped) orientation.
if (rect.width >= width && rect.height >= height) {
score = contactPointScoreNode(rect.x, rect.y, width, height);
if (score > bestContactScore) {
bestNode.x = rect.x;
bestNode.y = rect.y;
bestNode.width = width;
bestNode.height = height;
bestContactScore = score;
}
}
if (allowRotations && rect.width >= height && rect.height >= width) {
score = contactPointScoreNode(rect.x, rect.y, height, width);
if (score > bestContactScore) {
bestNode.x = rect.x;
bestNode.y = rect.y;
bestNode.width = height;
bestNode.height = width;
bestContactScore = score;
}
}
}
return bestNode;
}
private function splitFreeNode(freeNode:Rectangle, usedNode:Rectangle):Boolean {
// 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;
var newNode:Rectangle;
if (usedNode.x freeNode.x) {
// New node at the top side of the used node.
if (usedNode.y > freeNode.y && usedNode.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.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) {
// New node at the left side of the used node.
if (usedNode.x > freeNode.x && usedNode.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.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;
}
private function pruneFreeList():void {
for(var i:int = 0; i )
for(var j:int = i+1; j ) {
if (isContainedIn(freeRectangles[i], freeRectangles[j])) {
freeRectangles.splice(i,1);
break;
}
if (isContainedIn(freeRectangles[j], freeRectangles[i])) {
freeRectangles.splice(j,1);
}
}
}
private function isContainedIn(a:Rectangle, b:Rectangle):Boolean {
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;
}
}
}
package
{
public class FreeRectangleChoiceHeuristic {
public static const BestShortSideFit:int = 0; ///<-BSSF: Positions the Rectangle against the short side of a free Rectangle into which it fits the best.
public static const BestLongSideFit:int = 1; ///<-BLSF: Positions the Rectangle against the long side of a free Rectangle into which it fits the best.
public static const BestAreaFit:int = 2; ///<-BAF: Positions the Rectangle into the smallest free Rectangle into which it fits.
public static const BottomLeftRule:int = 3; ///<-BL: Does the Tetris placement.
public static const ContactPointRule:int = 4; ///<-CP: Choosest the placement where the Rectangle touches other Rectangles as much as possible.
}
}
package
{
import flash.display.Bitmap;
import flash.display.BitmapData;
import flash.display.Sprite;
import flash.geom.Point;
import flash.geom.Rectangle;
[SWF(width="800", , frameRate="30")]
public class Demo extends Sprite
{
[Embed(source="assets/1.png")]
private var defence:Class;
public function Demo()
{
var bitmap:Bitmap = Bitmap(new defence());
trace(bitmap.width, bitmap.height);
//Create new MaxRectsBinPack instance
var maxRect:MaxRectsBinPack = new MaxRectsBinPack(bitmap.width,bitmap.height,false);
// insert new rectangle
//maxRect.insert(bitmap.width/2, bitmap.height/2, FreeRectangleChoiceHeuristic.BestLongSideFit);
// insert new rectangle
//maxRect.insert(bitmap.width/2, bitmap.height/2, FreeRectangleChoiceHeuristic.BestLongSideFit);
// insert new rectangle
//maxRect.insert(bitmap.width/2, bitmap.height/2, FreeRectangleChoiceHeuristic.BestLongSideFit);
// insert new rectangle
//maxRect.insert(bitmap.width/2, bitmap.height/2, FreeRectangleChoiceHeuristic.BestLongSideFit);
var rects:Vector. = new Vector.();
rects.push(new Rectangle(0,0,bitmap.width/2, bitmap.height/2));
rects.push(new Rectangle(0,0,bitmap.width/2, bitmap.height/2));
rects.push(new Rectangle(0,0,bitmap.width/2, bitmap.height/2));
rects.push(new Rectangle(0,0,bitmap.width/2, bitmap.height/2));
maxRect.insert2(rects, new Vector.(), FreeRectangleChoiceHeuristic.BestLongSideFit);
for(var i:int = 0; i ) {
var rect:Rectangle = maxRect.usedRectangles[i];
trace(rect);
var bitmapData:BitmapData = new BitmapData(rect.width, rect.height, true, 0);
bitmapData.copyPixels(bitmap.bitmapData, rect, new Point());
var newBitmap:Bitmap = new Bitmap(bitmapData);
newBitmap.x = rect.x;
newBitmap.y = rect.y;
this.addChild(newBitmap);
}
}
}
}
首先，图片要求是2的次幂，如果有的图片，做成影片剪辑时，是3帧，如果能满足 2的次幂的结果是3的倍数呢？这里，我认为有一种方案，可以通过每一帧的偏移量来做，而不是非要3的倍数，不知道这样理解对不对？
public class FreeRectangleChoiceHeuristic {
public static const BestShortSideFit:int = 0; ///<-BSSF: Positions the Rectangle against the short side of a free Rectangle into which it fits the best.
public static const BestLongSideFit:int = 1; ///<-BLSF: Positions the Rectangle against the long side of a free Rectangle into which it fits the best.
public static const BestAreaFit:int = 2; ///<-BAF: Positions the Rectangle into the smallest free Rectangle into which it fits.
public static const BottomLeftRule:int = 3; ///<-BL: Does the Tetris placement.
public static const ContactPointRule:int = 4; ///<-CP: Choosest the placement where the Rectangle touches other Rectangles as much as possible.
}
京公网安备 11010802041100号