Trying to create x number of random rectangles by iterating through loop - but no overlapping

Question

This one has be me stumped. This is more of a Math/logic issue then a specific JS issue, but it's JS that I am working in and and some point I will need to convert the resulting logic to code....

I am trying to create X number of Non-overlapping rectangles and/or squares of random sizes on the canvas to achieve something like this example image:

(the number of boxes I would want to create could range anywhere from 10 to 100, give or take. Obviously the more boxes needed, the smaller they would all have to be)

I have a JS Fiddle where I have been trying different ideas, but the logic of this issue just keeps getting away from me...

What I DONT want is the classic Fibonacci spiral box pattern. I was hoping randomness would take care of that to some degree, but I also had the idea I could search the array of stored lines each time to find the longest line and start from a random point on that line.

I am on the current path of attempting to cut the canvas in half at a random point then add that line to an array. Then draw another lines based on the coordinates of the first line and then store that line also, and so on and so on... I'm storing the coordinates in an array of objects like this:

function storeLine(startX, startY, endX, endY, array) {
        array.push({
                start : {
                         x: startX,
                         y: startY
                        },
                end : {
                         x: endX,
                         y: endY
                        }
                });
}

But I soon hit issues with the fact that the very first line I draw across the whole x axis will ALWAYS be the longest line and I just ended up with lots of thin boxes.

In a perfect world my end result would take in variables like, Total number of boxes and Min x/y ratio so I could (somehow>) have an option to lean towards more portrait or more landscape boxes, so that I could adjust and keep regenerating till I had a result that I liked.

Anyway, I'm stuck about how to proceed, or even if I'm on the right path. If anyone has an idea about to continue down my current path or a better way to go about this, I would be forever in your debt!

Note: after checking my question, I had the thought that the Fibonacci box pattern would be OK as a starting point, but I would somehow still need to make the larger initial boxes also be divided up so that I dont just keep getting smaller and smaller boxes when I want a larger total number of boxes... anyway, just a random thought, if it gives someone else a spark of an idea.

Additional thought: A Voronoi pattern would be amazing too, but my math skills are just not up to even knowing where to start

Answer 1

This is a cool idea!

You can think about it terms of boxes in boxes (also like a tree). These boxes have their own coordinates and sizes. Boxes can be inside boxes so to do this you pick a dimension to split on (horizontally or vertically) then divide up for however many boxes. Then in each of those boxes you can add more boxes, etc. Finally to draw the lines you just equip boxes with the ability to draw themselves (and tell their boxes to draw themselves).

Below is some JS that does this. You can play with how much nesting you want to do pretty easily. The thing that is a little tricky and might need some adjusting is determining how to split the space into roughly even boxes (randomly different by a little bit). What's I've done to split the space into n boxes is to start with the size being 1/n of the available space, then randomly nudging it a little. If you just go with remaining*Math.random() most of the time you'll end up with very narrow boxes.

// probably play around with this to get better splitting
// maybe split near a mouse click
let splitDimension = (l, n) => {
    let splits = [];
    let remaining = l;
    let x = 0;
    for (let i=0; i<n-1; i++) {
        let r = Math.random();
        let seg = remaining * (1/n);
        let s = seg + 0.75*(0.5-r)*seg
        splits.push([x, s]);
        x += s;
        remaining -= s;
    }
    // add the last bit
    splits.push([x, remaining])
    return splits;
};
// the main idea
class Box {
    constructor(x, y, w, h) {
        this.x = x;
        this.y = y;
        this.w = w;
        this.h = h;
        this.boxes = [];
        
    }

    draw(ctx) {
        ctx.beginPath();
        ctx.rect(this.x, this.y, this.w, this.h);
        ctx.stroke();
        this.boxes.forEach(box => {
            box.draw(ctx)
        });
    }

    addBoxes(n, dim) {
        let splits;
        if (dim == "x") {
            // split on width
            splits = splitDimension(this.w, n)
            // turn the splits into new boxes
            this.boxes = splits.map(([x,w]) => {
                return new Box(this.x+x, this.y, w, this.h)
            });
        } else {
            // split over height
            splits = splitDimension(this.h, n);
            this.boxes = splits.map(([y,h]) => {
                return new Box(this.x, this.y+y, this.w, h);
            })
        }
    }
}
let canvas = document.querySelector("canvas");
let ctx = canvas.getContext("2d");
// let's make some boxes!
let bigBox = new Box(0,0,canvas.width,canvas.height);
bigBox.addBoxes(2, "y");
// now add boxes on boxes on boxes
bigBox.boxes.forEach(box => {
    box.addBoxes(3, "x");
    // also more boxes
    box.boxes.forEach(boxBox => {
        boxBox.addBoxes(2, "y");
    });
});
// now draw the boxes!
bigBox.draw(ctx);

Answer 2

The answer from @g23 is the basis of this, but I wanted to post the end result I came up with in case anyone wants a complete working system for this dilema.

The end result works by creating a box on the canvas where the user clicks then making 4 boxes around it. Those 4 boxes then use @g23 's original answer to divide it randomly into smaller boxes. The Box in the middle is the solution to having the very 1st divide line cut through the whole image and therefor make it look like two randomly divided boxes that just been stuck side by side. With this new system there will never be a line that cuts all the way across the canvas. I also added a Save button to download the result as well as sliders to control all of the settings and dimensions:

Working Fiddle here

var ImageWidth = 960
var ImageHeight = 540

var direction1 = "x";
var direction2 = "y";
var vert = true;

var LargeVerticalBoxes = parseInt(document.getElementById("lvb").value);
var inner = parseInt(document.getElementById("inner").value);
var smallest = parseInt(document.getElementById("smallest").value);
var totalboxes = "";

var clickBoxWidth = 200;
var clickBoxHeight = 100;
var lineWidth = 5;

var clickBox_xStart = 0;
var clickBox_yStart = 0;

var minSize = 0.1
var maxSize = 0.9

var canvas = document.getElementById('myCanvas');
var ctx = canvas.getContext('2d');


ctx.canvas.width = ImageWidth;
ctx.canvas.height = ImageHeight;

updateSettings();
canvas.addEventListener('click', function(evt) {
  var mousePos = getMousePos(canvas, evt);
  //console.log(mousePos.x + ',' + mousePos.y);

  clearCanvas();
  ctx.beginPath();
  calcclickBox(mousePos.x, mousePos.y)
  ctx.rect(clickBox_xStart, clickBox_yStart, clickBoxWidth, clickBoxHeight);
  ctx.lineWidth = lineWidth;
  ctx.strokeStyle = 'black';
  ctx.stroke();

  ctx.closePath();
  reDraw();
}, false);


download_img = function(el) {
  var image = canvas.toDataURL("image/png");
  el.href = image;
};


function updateSettings() {
  lineWidth = parseInt(document.getElementById("linewidth").value,10);
  clickBoxWidth = parseInt(document.getElementById("boxWidth").value,10);
  clickBoxHeight = parseInt(document.getElementById("boxHeight").value,10);
  canvas.width = parseInt(document.getElementById("canWidth").value,10);
  canvas.height = parseInt(document.getElementById("canHeight").value,10);
  document.getElementById("dispW").innerText = "Width: " + canvas.width;
  document.getElementById("dispH").innerText = "Height: " + canvas.height;
  document.getElementById("canW").innerText = "Width: " + clickBoxWidth;
  document.getElementById("canH").innerText = "Height: " + clickBoxHeight;
}


function clearCanvas() {
  ctx.clearRect(0, 0, canvas.width, canvas.height);
}


function calcclickBox(x, y) {
  clickBox_xStart = x - clickBoxWidth / 2;
  clickBox_yStart = y - clickBoxHeight / 2;
  clickBoxWidth = clickBoxWidth;
  clickBoxHeight = clickBoxHeight;
}



function getMousePos(canvas, evt) {
  var rect = canvas.getBoundingClientRect();
  return {
    x: evt.clientX - rect.left,
    y: evt.clientY - rect.top
  };
}

function toggle() {
  vert = !vert;
  if (vert) {
    direction1 = "x";
    direction2 = "y";
  } else {
    direction1 = "y";
    direction2 = "x";
  }
}

function getTotal() {
  LargeVerticalBoxes = parseInt(document.getElementById("lvb").value);
  inner = parseInt(document.getElementById("inner").value);
  smallest = parseInt(document.getElementById("smallest").value);
  totalboxes = LargeVerticalBoxes * inner * smallest * 4 + 1
  document.getElementById("total").innerText = totalboxes
}


function getRandomArbitrary(min, max) {
  return Math.random() * (max - min) + min;
}


/////// big long function that does most of the work //////////
function reDraw() {

  getTotal();

  // probably play around with this to get better splitting
  // maybe split near a mouse click
  let splitDimension = (l, n) => {
    let splits = [];
    let remaining = l;
    let x = 0;
    for (let i = 0; i < n - 1; i++) {
      let r = Math.random();
      let seg = remaining * (1 / n);
      let s = seg + 0.75 * (0.5 - r) * seg
      splits.push([x, s]);
      x += s;
      remaining -= s;
    }
    // add the last bit
    splits.push([x, remaining])
    return splits;
  };
  // the main idea
  class Box {
    constructor(x, y, w, h) {
      this.x = x;
      this.y = y;
      this.w = w;
      this.h = h;
      this.boxes = [];

    }



    draw(ctx) {
      ctx.beginPath();
      ctx.rect(this.x, this.y, this.w, this.h);
      ctx.stroke();
      this.boxes.forEach(box => {
        box.draw(ctx)
      });
    }

    addBoxes(n, dim) {
      let splits;
      if (dim == "x") {
        // split on width
        splits = splitDimension(this.w, n)
        // turn the splits into new boxes
        this.boxes = splits.map(([x, w]) => {
          return new Box(this.x + x, this.y, w, this.h)
        });
      } else {
        // split over height
        splits = splitDimension(this.h, n);
        // turn the splits into new boxes
        this.boxes = splits.map(([y, h]) => {
          return new Box(this.x, this.y + y, this.w, h);
        })
      }
    }
  }


  // let's make some boxes!
  let TopRightBox = new Box(clickBox_xStart,
    clickBox_yStart,
    canvas.width - clickBox_xStart,
    -clickBox_yStart);

  let BottomRight = new Box(clickBox_xStart + clickBoxWidth,
    clickBox_yStart,
    canvas.width - clickBox_xStart - clickBoxWidth,
    canvas.height - clickBox_yStart);

  let BottomLeft = new Box(clickBox_xStart + clickBoxWidth,
    clickBox_yStart + clickBoxHeight,
    -clickBox_xStart - clickBoxWidth,
    canvas.height - clickBox_yStart - clickBoxHeight);

  let TopLeft = new Box(0, 0, clickBox_xStart, clickBox_yStart + clickBoxHeight);
  TopRightBox.addBoxes(LargeVerticalBoxes, direction1);
  BottomRight.addBoxes(LargeVerticalBoxes, direction1);
  BottomLeft.addBoxes(LargeVerticalBoxes, direction1);
  TopLeft.addBoxes(LargeVerticalBoxes, direction1);

  // now add boxes on boxes on boxes
  TopRightBox.boxes.forEach(box => {
    box.addBoxes(inner, direction2);

    // also more boxes
    box.boxes.forEach(boxBox => {
      boxBox.addBoxes(smallest, direction1);
    });
  });
  BottomRight.boxes.forEach(box => {
    box.addBoxes(inner, direction2);

    // also more boxes
    box.boxes.forEach(boxBox => {
      boxBox.addBoxes(smallest, direction1);
    });
  });

  BottomLeft.boxes.forEach(box => {
    box.addBoxes(inner, direction2);

    // also more boxes
    box.boxes.forEach(boxBox => {
      boxBox.addBoxes(smallest, direction1);
    });
  });
  TopLeft.boxes.forEach(box => {
    box.addBoxes(inner, direction2);

    // also more boxes
    box.boxes.forEach(boxBox => {
      boxBox.addBoxes(smallest, direction1);
    });
  });


  // now draw the boxes!
  TopRightBox.draw(ctx);
  BottomRight.draw(ctx);
  BottomLeft.draw(ctx);
  TopLeft.draw(ctx);
  document.getElementById("total").innerText = totalboxes
}

<html>
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/4.5.2/css/bootstrap.min.css">
<style>
canvas {
}
</style>
<body>
<div class="fluid-container px-3 border">
     <strong>click</strong> on the canvas to create start box and draw new layout


<div class="row">
    <div class="col">
        <div class="row">
        
            <div class="col-12">
            Canvas:
        </div>
            
        </div>
        
        <div class="row">
        
            <div class="col">
                    <span id="dispW">Width: </span>  <input class="form-control" type="range" min="16" max="1920" value=480 id="canWidth" onchange="updateSettings()" />
            </div>
        
            <div class="col">
                <span id="dispH">Height: </span><input class="form-control" type="range" min="9" max="1080" value=270 id="canHeight" onchange="updateSettings()" /> 
            </div> 
            
            
    </div>
    
    <div class="row">
        <div class="col-12">
                Start Box:
        </div>
    </div>
    <div class="row">
        <div class="col">
        <span id="canW">Width: </span> <input class="form-control" type="range" min="1" max="200" value=50 id="boxWidth" onchange="updateSettings()"> 
        </div>
        <div class="col">
            <span id="canH">Height: </span> <input class="form-control" type="range" min="1" max="200" value=100 id="boxHeight" onchange="updateSettings()">
            </div>
</div>
    <div class="row">
        <div class="col-12">
            Line Width:    (changing these settings breaks stuff)
        <input class="form-control" type="range" min="1" max="20" value="5" id="linewidth" onchange="updateSettings()"> </div>
        </div>
        
        <div class="row">
        <div class="col-6">
    <p>Large Vertical Boxes: 
  <input type="range" min="1" max="10" value="1" id="lvb" onchange="getTotal()"></p>
      <p>Medium inner Boxes: 
  <input type="range" min="1" max="10" value="1" id="inner" onchange="getTotal()"></p>
    <p>Smallest inner Boxes: 
  <input type="range" min="1" max="10" value="1" id="smallest" onchange="getTotal()">
    </p>
    </div>
        <div class="col-6">
     toggle horizontal/vertical
<label class="switch">
  <input type="checkbox" id="toggle" onchange="toggle()">
  <span class="slider round"></span>
</label>
    <p>Total number of boxes: <span id="total"> </span></p>
    
    <a  id="download" download="GridLayout.png" href="" onclick="download_img(this);"><button>
    Save Layout
    </button></a>
    </div>
</div>
<br>
<div class="row">
    <div class="col">
        <canvas id="myCanvas" width="578" height="200" style="border:1px solid #000000;" ></canvas>
    </div>
 </div>
</div>
</div>
</div>
<br><br><br><br><br>
</body>
</html>