来自：http://www.duzengqiang.com/blog/post/971.html 转载请标明出处。
What's MaxRectsBinPack
MaxRects算法是一个二维图像排列算法,在FlashCS6的Sprite导出功能和TexturePacker中均有使用. 
Reference
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
This version is also public domain - do whatever you want with it.
Source Code
/*
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.display.*;
import flash.events.*;
import flash.geom.Rectangle;
import flash.net.*;
/**
* MaxRectanglesBinPack
* @author DUZENGQIANG
* @date Jun 7, 2012
* @version 1.0
* <p>SinaMicroBlog: http://weibo.com/duzengqiang</p>
* <p>blog: http://www.duzengqiang.com</p>
*/
public class MaxRectsBinPack
{
public var binWidth:int = 0;
public var binHeight:int = 0;
public var allowRotations:Boolean = false;
public var usedRectangles:Vector.<Rectangle> = new Vector.<Rectangle>();
public var freeRectangles:Vector.<Rectangle> = new Vector.<Rectangle>();
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;
}
private function insert2( Rectangles:Vector.<Rectangle>, dst:Vector.<Rectangle>, 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 < Rectangles.length; ++i) {
var score1:int = 0;
var score2:int = 0;
var newNode:Rectangle = scoreRectangle(Rectangles[i].width, Rectangles[i].height, method, score1, score2);
if (score1 < bestScore1 || (score1 == bestScore1 && score2 < 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 < numRectanglesToProcess; 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 < usedRectangles.length; i++)
usedSurfaceArea += usedRectangles[i].width * usedRectangles[i].height;
return usedSurfaceArea / (binWidth * binHeight);
}
private function findPositionForNewNodeBottomLeft(width:int, height:int,
bestY:int, bestX:int) {
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 < freeRectangles.length; 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 < bestY || (topSideY == bestY && rect.x < 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 < bestY || (topSideY == bestY && rect.x < 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 < freeRectangles.length; 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 < bestShortSideFit || (shortSideFit == bestShortSideFit && longSideFit < bestLongSideFit)) {
bestNode.x = rect.x;
bestNode.y = rect.y;
bestNode.width = width;
bestNode.height = height;
bestShortSideFit = shortSideFit;
bestLongSideFit = longSideFit;
}
}
var flippedLeftoverHoriz:int;
var flippedLeftoverVert:int;
var flippedShortSideFit:int;
var flippedLongSideFit:int;
if (allowRotations && rect.width >= height && rect.height >= width) {
var flippedLeftoverHoriz = Math.abs(rect.width - height);
var flippedLeftoverVert = Math.abs(rect.height - width);
var flippedShortSideFit = Math.min(flippedLeftoverHoriz, flippedLeftoverVert);
var flippedLongSideFit = Math.max(flippedLeftoverHoriz, flippedLeftoverVert);
if (flippedShortSideFit < bestShortSideFit || (flippedShortSideFit == bestShortSideFit && flippedLongSideFit < 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 < freeRectangles.length; 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 < bestLongSideFit || (longSideFit == bestLongSideFit && shortSideFit < 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 < bestLongSideFit || (longSideFit == bestLongSideFit && shortSideFit < 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 < freeRectangles.length; 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 < bestAreaFit || (areaFit == bestAreaFit && shortSideFit < 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 < bestAreaFit || (areaFit == bestAreaFit && shortSideFit < 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 < i2start || i2end < 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 < usedRectangles.length; 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 < freeRectangles.length; 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 + 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;
}
private function pruneFreeList():void {
for(var i:int = 0; i < freeRectangles.length; i++)
for(var j:int = i+1; j < freeRectangles.length; 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;
}
}
}
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.
}
Download
How to use
//Create new MaxRectsBinPack instance
var maxRect:MaxRectsBinPack = new MaxRectsBinPack(1024,1024,false);
// insert new rectangle
maxRect.insert(300,200,0);
//There are 5 insert method in FreeRectangleChoiceHeuristic class.
// 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.
//}
usedRectangles: storage of all used rectangles
freeRectangles: storage of all free rectangles
The insert method will return a rectangle. when its width an height are both 0. That means it can not be inserted anymore.
For more information, see a series of blog posts at
http://clb.demon.fi/projects/rectangle-bin-packing
http://clb.demon.fi/projects/more-rectangle-bin-packing
http://clb.demon.fi/projects/even-more-rectangle-bin-packing
使用方法：http://www.cnblogs.com/yourihua/archive/2012/06/19/2554687.html
相关推荐
基于区域合并的纹理图像分割—MSRM算法的MATLAB实现 本文档主要讨论了基于区域合并的纹理图像分割—MSRM算法的MATLAB实现。图像分割是图像分析及计算机视觉系统中的重要环节，是图像处理研究中的一个基本难题。图像...
### 一种改进的纹理分析算法 #### 概述 本文主要介绍了一种改进的纹理分析算法，该算法通过计算图像的归一化共生矩阵来提取纹理特征，具体涉及的纹理特征包括二阶矩（能量）、熵、对比度以及同质性。通过分析这些...
### 3D纹理算法类似OpenGL的一个实现 #### 知识点概述 在计算机图形学领域，3D纹理映射是一项关键技术，它能够显著提升场景的真实感。本文将围绕一个类似于OpenGL实现的3D纹理算法进行深入探讨。通过分析提供的...
这种方法能够在无需人工干预的情况下实现纹理的有效合并，并保证合并结果接近全局最优。 ##### 贪心算法 **步骤一：使用贪心算法自动合并小纹理** - **目的**：通过贪心算法快速完成初步的纹理合并，为后续优化提供...
本文将深入探讨两种纹理合成算法的实现，分别是基于像素的Li-Yi Wei算法和基于块的Freeman算法。 首先，让我们关注基于像素的Li-Yi Wei算法。此算法的核心思想是通过在原始纹理中寻找相似的像素邻域，并将它们映射...
3. **复制与旋转**：将这个相似区域复制并随机旋转后粘贴到新纹理的位置，确保新纹理的连续性和多样性。 4. **迭代过程**：重复以上步骤，每次选择不同的种子像素，直到新纹理达到所需的大小。 5. **自适应调整**：...
3. **纹理坐标映射**：将纹理坐标与模型的几何坐标关联起来，这通常通过纹理坐标顶点数组实现。 4. **启用纹理映射**：在OpenGL中设置必要的状态，如开启纹理映射，选择合适的纹理环境参数。 5. **绘制几何体**：...
文中不仅对比了球面纹理映射的不同算法的优点和缺陷，并且介绍了适用于不规则曲面投影映射的具体实现步骤及其实验结果，表明后者在维持纹理形状完整性方面更具优势。这几种方法对于提升计算机视觉效果，增强虚拟现实...
总之，OpenGL的纹理映射算法为3D图形带来了生动的视觉效果，而实现这一功能需要理解纹理坐标系统、纹理对象、纹理参数和渲染流程等多个方面。通过VC++6.0和OpenGL，我们可以创建出具有高质量纹理的3D应用程序。
### 一种适用于球面局部区域的纹理映射算法解析 #### 概述 在三维图形渲染和虚拟现实领域，纹理映射技术是一项至关重要的技术，它能够赋予模型表面丰富的细节和真实感。其中，球面纹理映射因其简单性和通用性而被...
3. **纹理块选择和放置**：编写算法逻辑，根据统计信息选取合适的纹理块，并在大纹理上进行放置。 4. **边界混合**：实现边界混合算法，消除相邻纹理块的界限。 5. **迭代优化**：设置循环结构，进行多次迭代以...
压缩包中的“LBP算法实现图像的纹理分类”文件可能包含了完整的MATLAB代码示例，涵盖了上述所有步骤。通过阅读和理解代码，你可以学习到如何在实际项目中应用LBP算法进行图像纹理分类。同时，这个程序也可以作为...
3. `mincut.m` 和 `ssd.m`：这两个文件可能是实现图像分割过程中使用的辅助函数，如最小割（Minimum Cut）算法或均方差（Sum of Squared Differences）计算。 4. `Y.mat`：可能存储了图像处理过程中的中间结果或参数...
### 基于纹理的匹配算法：改进与实现 #### 引言 在图像处理领域，基于纹理的模板匹配算法是一种高效且灵活的方法，用于识别和定位特定模式或对象。这种算法尤其适用于处理复杂场景，如监控视频分析、工业检测、...
对于有一定基础或热衷于研究的人来说，可以在这些基础代码上进行修改和扩展，实现其他功能。 【沟通交流】：有任何使用上的问题，欢迎随时与博主沟通，博主会及时解答。鼓励下载和使用，并欢迎大家互相学习，共同...
图像纹理聚类分割算法是一种在图像处理领域广泛应用的技术，它主要关注如何通过对图像中的纹理信息进行分析和组织，来实现图像区域的有效分割。这个过程通常包括纹理特征的提取、聚类算法的选择以及最终的图像分割。...