图片墙和 Bin Packing

_.js

var BinPacker = require('./binpacker')

var blocks = []

blocks.push(
  // 宽的
  {w: 300,h: 390}, 
  {w: 300,h: 390}, 
  // 窄的
  {w: 150,h: 195}, 
  {w: 150,h: 195}, 
  {w: 150,h: 195}, 
  {w: 150,h: 195}, 
  {w: 150,h: 195}, 
  {w: 150,h: 195}, 
  {w: 150,h: 195}, 
  {w: 150,h: 195}, 
  {w: 150,h: 195}, 
  {w: 150,h: 195}
)

var sorter = {
  random : function() {
    return Math.random() - .5
  }
}

// 容器宽900，高585
var packer = new BinPacker(900,585)

blocks.sort(sorter.random)

/*var fits = */
packer.fit(blocks)

var drawBlock = function(blk) {
  console.log(blk.fit);
}

blocks.forEach(drawBlock)

binpacker.js

(function(host) {

/**
 * Bin Packing
 * ref : http://www.blackpawn.com/texts/lightmaps/
 * ref : https://github.com/jakesgordon/bin-packing/blob/master/js/packer.js
 */

function BinPacker(width,height) {
  this.root = rect( 0, 0, width, height )
}

function rect(left,top,width,height) {
  return { x:left, y:top, w:width, h:height }
}

BinPacker.prototype = {
  fit : function(blocks) {
    return (Array.isArray(blocks) ? blocks : [blocks]).map(function(blk) {
      return blk.fit = this.find( this.root, blk )
    },this)
  },
  find : function(node,blk) {
    if ( node.left )
      return this.find( node.left, blk ) || this.find( node.right, blk )

    if ( node.used || blk.w > node.w || blk.h > node.h )
      return null

    if ( blk.w === node.w && blk.h === node.h ) {
      node.used = true
      return node
    }

    this.split(node,blk)

    return this.find( node.left, blk )
  },
  split : function(node,blk) {
    var dw = node.w - blk.w, dh = node.h - blk.h

    if ( dw > dh ) {
      // 横向分区
      node.left = rect( node.x, node.y, blk.w, node.h )
      node.right = rect( node.x+blk.w, node.y, node.w-blk.w, node.h )
    } else {
      // 纵向分区
      node.left = rect( node.x, node.y, node.w, blk.h )
      node.right = rect( node.x, node.y+blk.h, node.w, node.h-blk.h )
    }
  }
}

if( typeof module !== 'undefined' ){
  module.exports = BinPacker
}else{
  host.BinPacker = BinPacker
}

})(this)

dump.md

{ x: 0, y: 0, w: 150, h: 195, used: true }
{ x: 0, y: 195, w: 150, h: 195, used: true }
{ x: 0, y: 390, w: 150, h: 195, used: true }
{ x: 150, y: 0, w: 300, h: 390, used: true }
{ x: 150, y: 390, w: 150, h: 195, used: true }
{ x: 300, y: 390, w: 150, h: 195, used: true }
{ x: 450, y: 0, w: 150, h: 195, used: true }
{ x: 600, y: 0, w: 150, h: 195, used: true }
{ x: 750, y: 0, w: 150, h: 195, used: true }
{ x: 450, y: 195, w: 150, h: 195, used: true }
{ x: 450, y: 390, w: 150, h: 195, used: true }
{ x: 600, y: 195, w: 300, h: 390, used: true }

分区的不同

simple-packer
目标恰好排除到节点分区之外
目标方块区域不计入 node。这里，只插入一个块时，分区只进行一次，packer上存在三个节点。

growing-packer
把首个插入的方块当做根节点，然后往它的下方或右方自适应增长。
它不适用于随机生成顺序的情况，大方块在后面的的话，排列时直接被丢弃了。

bin-packer
直到给目标划分了节点
上面参照 blackpawn 的实现，每一个插入的方块必然被一个节点包含；每一次分区就进行预判，决定横向还是纵向分区。
因此当第一个方块插入时就已经存在五个节点了。

对这个特定示例测试时，由于三种模式策略完全不同，它们排列时达到完美效果的概率也不同，尝试10万次运行统计如下：

Mode            耗时     完美次数/尝试次数
bin-packer      947ms    93598/100000
growing-packer  993ms    29349/100000
simple-packer   753ms    25672/100000

关于

Bin packing problem

梦幻般的图片墙展示

我看到原文是 lightmap 拼接，还有 CSS Sprite 自动化处理，有了这些印象之后，我想图片展示也是用途之一。

用 CSS3、SVG、Jscex 做了一个练习

http://ambar.no.de/demos/binpacking/index.html

• Modernizr 用于检测 CSS 3 变换模块支持，不支持的情况回退 jQuery 动画
• Raphaël 用于 SVG 图形，带交互和动画，语法类似于 jQuery
• Jscex 用于高亮块，异步动画
• ES 5 Shim 让低版本 IE JavaScript 写起来爽快一点
• Aristo 主题 UI，按钮样式

hi，demo貌似无法访问了。请问有没有新的访问路径？或者能否发一份完整代码

, 3q