Advertisement
Guest User

Revised working demo growing bin packing

a guest
May 2nd, 2012
326
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. GrowingPacker = function(maxW, maxH) { this.maxW = maxW; this.maxH = maxH;};
  2.  
  3. GrowingPacker.prototype = {
  4.  
  5.   fit: function(blocks) {
  6.     var n, node, block, len = blocks.length;
  7.     var w = len > 0 ? blocks[0].w : 0;
  8.     var h = len > 0 ? blocks[0].h : 0;
  9.     this.root = { x: 0, y: 0, w: w, h: h };
  10.    
  11.    
  12.    
  13.     for (n = 0; n < len ; n++) {
  14.       block = blocks[n];
  15.       if (node = this.findNode(this.root, block.w, block.h)) {
  16.         block.fit = this.splitNode(node, block.w, block.h);
  17.  
  18.        
  19.       }
  20.    
  21.       else {
  22.         block.fit = this.growNode(block.w, block.h);
  23.       }
  24.     }
  25.   },
  26.  
  27.   findNode: function(root, w, h) {
  28.     if (root.used)
  29.       return this.findNode(root.right, w, h) || this.findNode(root.down, w, h);
  30.     else if ((w <= root.w) && (h <= root.h))
  31.       return root;
  32.     else
  33.       return null;
  34.   },
  35.  
  36.   splitNode: function(node, w, h) {
  37.     node.used = true;
  38.     node.down  = { x: node.x,     y: node.y + h, w: node.w,     h: node.h - h };
  39.     node.right = { x: node.x + w, y: node.y,     w: node.w - w, h: h          };
  40.     return node;
  41.   },
  42.  
  43.   growNode: function(w, h) {
  44.     var canGrowRight  = (w <= this.root.w && this.root.w + w <= this.maxW);
  45.     var canGrowDown = (h <= this.root.h && this.root.h + h <= this.maxH);
  46.  
  47.     if (canGrowRight) {
  48.         return this.growRight(w, h);
  49.     }
  50.     else if (canGrowDown) {
  51.         return this.growDown(w, h);
  52.     }
  53.     else
  54.    
  55.       return null; // need to ensure sensible root starting size to avoid this happening
  56.   },
  57.  
  58.   growRight: function(w, h) {
  59.     this.root = {
  60.       used: true,
  61.       x: 0,
  62.       y: 0,
  63.       w: this.root.w + w,
  64.       h: this.root.h,
  65.       down: this.root,
  66.       right: { x: this.root.w, y: 0, w: w, h: this.root.h }
  67.     };
  68.     if (node = this.findNode(this.root, w, h))
  69.       return this.splitNode(node, w, h);
  70.     else
  71.       return null;
  72.   },
  73.  
  74.   growDown: function(w, h) {
  75.     this.root = {
  76.       used: true,
  77.       x: 0,
  78.       y: 0,
  79.       w: this.root.w,
  80.       h: this.root.h + h,
  81.       down:  { x: 0, y: this.root.h, w: this.root.w, h: h },
  82.       right: this.root
  83.     };
  84.     if (node = this.findNode(this.root, w, h))
  85.       return this.splitNode(node, w, h);
  86.     else
  87.       return null;
  88.   }
  89.  
  90. }
  91.  
  92. /*****************************************************************************************************/
  93.  
  94. var blocks = [
  95.     { w: 500, h: 700 },
  96.     { w: 500, h: 700 },
  97.     { w: 500, h: 350 },
  98.     { w: 500, h: 350 },
  99.     { w: 500, h: 350 },
  100.     { w: 500, h: 350 },
  101.     { w: 500, h: 350 },
  102.     { w: 500, h: 350 },
  103.     { w: 500, h: 350 },
  104.     { w: 500, h: 350 },
  105.     { w: 250, h: 350 },
  106.     { w: 250, h: 350 },
  107.     { w: 250, h: 350 },
  108.     { w: 250, h: 350 },
  109.     { w: 250, h: 350 },
  110.     { w: 250, h: 350 },
  111.     { w: 250, h: 350 },
  112.     { w: 250, h: 350 },
  113.     { w: 250, h: 350 },
  114.     { w: 250, h: 350 },
  115.     { w: 250, h: 350 },
  116.     { w: 250, h: 350 },
  117.     { w: 250, h: 350 }
  118. ];
  119.  
  120. var sheets = [];
  121.  
  122. while(blocks.length) {
  123.     var packer = new GrowingPacker(1000,800);
  124.     packer.fit(blocks);
  125.  
  126.     sheet = [];
  127.     for (var i=blocks.length-1; i>=0; i--) {
  128.         if (blocks[i].fit !== undefined && blocks[i].fit !== null) {
  129.             //console.log(blocks[i].fit);
  130.             sheet.unshift(blocks[i]);
  131.             blocks.splice(i,1);
  132.         }
  133.     }
  134.     //console.log(sheet[sheet.length-1].fit.y + sheet[sheet.length-1].h);
  135.     //console.log(sheet);
  136.     sheets.push(sheet);
  137. }
  138.  
  139.  
  140. for(var i=0; i<sheets.length; i++) {
  141.     var sheet = sheets[i];
  142.     var sheetWidth = sheet[sheet.length-1].w + sheet[sheet.length-1].fit.x;
  143.     var sheetHeight = sheet[sheet.length-1].h + sheet[sheet.length-1].fit.y;
  144.  
  145.     for(var j=0; j<sheet.length; j++) {
  146.  
  147.  
  148.  
  149.     console.log("SHEET #" + i + " - W: " + sheetWidth + " H: " + sheetHeight + " BLOCK #" + j + " - W: " + sheet[j].w + " H: " + sheet[j].h + " X: " + sheet[j].fit.x + " Y: " + sheet[j].fit.y);
  150.     }
  151. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement