图片墙和 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 }

, 3q