<!DOCTYPE html>
<html>
<head>
<script data-require="jquery@*" data-semver="2.1.4" src="http://code.jquery.com/jquery-2.1.4.min.js"></script>
<link rel="stylesheet" href="style.css" />
</head>
<body>
<div id="content">
<h2>Bin Packing for School Pictures - Demo</h2>
<div class="blocks">
<p>Blocks: W x H [x N] - </p>
<p>
For best results, enter blocks from largest to smallest.
This is taken care of using a sort algorithm or through the UI in production.</p>
<ul class="list-unstyled">
<li>Maximum sheet size is 100x80</li>
<li>8x10 = '100x80'</li>
<li>5x7 = '50x70'</li>
<li>3x5 = '50x35'</li>
<li>wallet = '25x35'</li>
<li>miniwallet = '25x17.5'</li>
</ul>
<textarea id="blocks" rows="12">100x80
50x70
50x35x2
25x35x8
25x17.5x8
</textarea>
</div>
<div id="nofit"></div>
<div id="preview"></div>
</div>
<script src="script.js"></script>
</body>
</html>
GrowingPacker = function(maxW, maxH) {
this.maxW = maxW;
this.maxH = maxH;
};
GrowingPacker.prototype = {
fit: function(blocks) {
var n, node, block, len = blocks.length;
var w = len > 0 ? blocks[0].w : 0;
var h = len > 0 ? blocks[0].h : 0;
this.root = {
x: 0,
y: 0,
w: w,
h: h
};
for (n = 0; n < len ; n++) {
block = blocks[n];
if (node = this.findNode(this.root, block.w, block.h)) {
block.fit = this.splitNode(node, block.w, block.h);
}
else {
block.fit = this.growNode(block.w, block.h);
}
}
},
findNode: function(root, w, h) {
if (root.used) {
return this.findNode(root.right, w, h) || this.findNode(root.down, w, h);
}
else if ((w <= root.w && w <= this.maxW) && (h <= root.h && w <= this.maxW)) {
this.binWidth = this.root.w <= this.maxW ? this.root.w : this.maxW;
this.binHeight = this.root.h <= this.maxH ? this.root.h : this.maxH;
return root;
}
else {
return null;
}
},
splitNode: function(node, w, h) {
node.used = true;
node.down = {
x: node.x,
y: node.y + h,
w: node.w,
h: node.h - h
};
node.right = {
x: node.x + w,
y: node.y,
w: node.w - w,
h: h
};
return node;
},
growNode: function(w, h) {
var canGrowRight = (w <= this.root.w && this.root.w + w <= this.maxW);
var canGrowDown = (h <= this.root.h && this.root.h + h <= this.maxH);
if (canGrowRight) {
return this.growRight(w, h);
}
else if (canGrowDown) {
return this.growDown(w, h);
}
else
return null; // need to ensure sensible root starting size to avoid this happening
},
growRight: function(w, h) {
this.root = {
used: true,
x: 0,
y: 0,
w: this.root.w + w,
h: this.root.h,
down: this.root,
right: {
x: this.root.w,
y: 0,
w: w,
h: this.root.h
}
};
if (node = this.findNode(this.root, w, h))
return this.splitNode(node, w, h);
else
return null;
},
growDown: function(w, h) {
this.root = {
used: true,
x: 0,
y: 0,
w: this.root.w,
h: this.root.h + h,
down: {
x: 0,
y: this.root.h,
w: this.root.w,
h: h
},
right: this.root
};
if (node = this.findNode(this.root, w, h))
return this.splitNode(node, w, h);
else
return null;
}
}
Packagizer = function(sheetWidth, sheetHeight) {
this.sheetWidth = sheetWidth;
this.sheetHeight = sheetHeight;
this.sheets = [];
this.nofit = [];
this.run = function(blocks) {
//remove any blocks that are too big for sheet size and move them to nofit array
for (var i=blocks.length-1; i>=0; i--) {
if (blocks[i].w > sheetWidth || blocks[i].h > sheetHeight) {
this.nofit.unshift(blocks[i]);
blocks.splice(i, 1);
}
}
while(blocks.length) {
var packer = new GrowingPacker(sheetWidth,sheetHeight);
packer.fit(blocks);
var sheet = [];
for (var i=blocks.length-1; i>=0; i--) {
if (blocks[i].fit !== undefined && blocks[i].fit !== null) {
//console.log(blocks[i].fit);
sheet.unshift(blocks[i]);
blocks.splice(i,1);
}
}
sheet.sheetWidth = packer.maxW; //Always printing to 10xH. Use packer.binWidth; for WxH
sheet.sheetHeight = packer.binHeight;
//console.log(sheet);
this.sheets.push(sheet);
}
}
}
function deserialize(val) {
var i, j, block, blocks = val.split("\n"), result = [];
for(i = 0 ; i < blocks.length ; i++) {
block = blocks[i].split("x");
if (block.length >= 2)
result.push({w: parseInt(block[0]), h: parseInt(block[1]), num: (block.length == 2 ? 1 : parseInt(block[2]))});
}
var expanded = [];
for(i = 0 ; i < result.length ; i++) {
for(j = 0 ; j < result[i].num ; j++)
expanded.push({w: result[i].w, h: result[i].h, area: result[i].w * result[i].h});
}
return expanded;
}
function drawSheet(sh, maxW, maxH) {
var canvas = document.createElement('canvas');
canvas.setAttribute('width', maxW);
canvas.setAttribute('height', maxH);
document.getElementById('preview').appendChild(canvas);
var context = canvas.getContext('2d');
for (var k = 0; k < sh.length; k++) {
context.fillStyle = 'cyan';
context.fillRect(sh[k].fit.x, sh[k].fit.y, sh[k].w, sh[k].h);
context.strokeStyle = 'grey';
context.strokeRect(sh[k].fit.x, sh[k].fit.y, sh[k].w, sh[k].h);
console.log("Sheet = " + k + " Width = " + sh[k].w + ", Height = " + sh[k].h + ", X = " + sh[k].fit.x + ", Y = " + sh[k].fit.y);
}
}
function demoRun(blocks) {
$nofit = $('#nofit');
$nofit.html('');
var pack = new Packagizer(100, 80);
pack.run(blocks);
if (pack.nofit.length) {
var o = 'The following wont fit. They exceed the maximum sheet size.</br>';
for (var i=0; i<pack.nofit.length; i++) {
o += "BLOCK - W: " + pack.nofit[i].w + " H: " + pack.nofit[i].h + "</br>";
$nofit.html(o);
}
}
document.getElementById('preview').innerHTML = '';
for (var i=0; i<pack.sheets.length; i++) {
drawSheet(pack.sheets[i], 100, 80);
}
}
$blocks = $('#blocks');
blocks = [];
$blocks.keypress(function(ev) {
if (ev.which == 13) {
blocks = deserialize($blocks.val());
//console.log(JSON.stringify(blocks));//Demo.run(); // run on <enter> while entering block information
demoRun(blocks);
}
});
$(document).ready(
function() {
blocks = deserialize($blocks.val());
demoRun(blocks);
}
);
root {
display: block;
}
body {
width : 90%;
margin : auto;
}
#preview {
width : 100%;
height : 400px;
margin : auto;
overflow : auto;
border : 1px solid black;
clear: both;
}
#preview canvas {
margin : 1px;
float: left;
}
#nofit {
color : red;
float : left;
}