Bin Packing Js implementation using box rotation for best fit

Question

I have used the bin packing js implementation here https://github.com/jakesgordon/bin-packing

When I specify the frame size as 800x600

and Blocks size as 150x700,150x700 it would say that, it cant accommodate However, there is ample space. The same when 700x150, 700x150 is made, it would fit it.

How Do I adapt the code, so that it can dynamically rotate the block size and fits in to the frame.

The js packer used here is,

    Packer = function(w, h) {
  this.init(w, h);
};

Packer.prototype = {

  init: function(w, h) {
    this.root = { x: 0, y: 0, w: w, h: h };
  },

  fit: function(blocks) {
    var n, node, block;
    for (n = 0; n < blocks.length; n++) {
      block = blocks[n];
      if (node = this.findNode(this.root, block.w, block.h))
        block.fit = this.splitNode(node, 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) && (h <= root.h))
      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;
  }

}

Answer 1

I think the code below might do the trick...?! (Ie, I did limited testing, but for what I tested, it appears to work.)

I essentially added another option in the findnode routine to rotate the block (ie, switch the width and height dimensions) as an option if it doesn't fit in it's predefined orientation. This involved adding another property to block dubbed rotate as an indicator that the dimensions were swapped. (And the introduction of swapping and the rotate property necessitated, of course, passing block to findnode rather than w and h as in the previous code.)

Packer = function(w, h) {
  this.init(w, h);
};

Packer.prototype = {

  init: function(w, h) {
    this.root = { x: 0, y: 0, w: w, h: h };
  },

  fit: function(blocks) {
    var n, node, block;
    for (n = 0; n < blocks.length; n++) {
      block = blocks[n];
      block.rotate = false;
      if (node = this.findNode(this.root, block))
        block.fit = this.splitNode(node, block);
    }  
  },

  findNode: function(root, block) {
    if (root.used) {
      return this.findNode(root.right, block) || this.findNode(root.down, block);
    } else if ((block.w <= root.w) && (block.h <= root.h)) {
      return root;
    } else if ((block.h <= root.w) && (block.w <= root.h)) {
        let temp = block.w;
        block.w = block.h;
        block.h = temp;
        block.rotate = !block.rotate;
        return root;
    } else
      return null;
  },

  splitNode: function(node, block) {
    node.used = true;
    node.down  = { x: node.x,           y: node.y + block.h, w: node.w,           h: node.h - block.h };
    node.right = { x: node.x + block.w, y: node.y,           w: node.w - block.w, h: block.h          };
    return node;
  }
}

Hopefully this does the trick for you.