CODEWITHSUNDEEP
javascriptdomgeometry
wireless-g
wireless-g

Reputation: 49

JS randomly distribute child elements in their parent without overlap

I am trying to make something where a bunch of circles (divs with border-radius) can be dynamically generated and laid out in their container without overlapping.

Here is my progress so far - https://jsbin.com/domogivuse/2/edit?html,css,js,output

var sizes = [200, 120, 500, 80, 145];
var max = sizes.reduce(function(a, b) {
    return Math.max(a, b);
});
var min = sizes.reduce(function(a, b) {
    return Math.min(a, b);
});
var percentages = sizes.map(function(x) {
    return ((x - min) * 100) / (max - min);
});
percentages.sort(function(a, b) {
    return b-a;
})
var container = document.getElementById('container');
var width = container.clientWidth;
var height = container.clientHeight;
var area = width * height;
var maxCircleArea = (area / sizes.length);
var pi = Math.PI;
var maxRadius = Math.sqrt(maxCircleArea / pi);
var minRadius = maxRadius * 0.50;
var range = maxRadius - minRadius;
var radii = percentages.map(function(x) {
    return ((x / 100) * range) + minRadius;
});
function getRandomArbitrary(min, max) {
    return Math.random() * (max - min) + min;
}

var coords = [];
radii.forEach(function(e, i) {
    var circle = document.createElement('div');
    var randomTop = getRandomArbitrary(0, height);
    var randomLeft = getRandomArbitrary(0, width);
    var top = randomTop + (e * 2) < height ?
        randomTop :
        randomTop - (e * 2) >= 0 ?
        randomTop - (e * 2) :
        randomTop - e;
    var left = randomLeft + (e * 2) < width ?
        randomLeft :
        randomLeft - (e * 2) >= 0 ?
        randomLeft - (e * 2) :
        randomLeft - e;
    var x = left + e;
    var y = top + e;

    coords.push({x: x, y: y, radius: e});
    circle.className = 'bubble';
    circle.style.width = e * 2 + 'px';
    circle.style.height = e * 2 + 'px';
    circle.style.top = top + 'px';
    circle.style.left = left + 'px';
    circle.innerText = i
    container.appendChild(circle);
});

I have got them being added to the parent container but as you can see they overlap and I don't really know how to solve this. I tried implementing a formula like (x1 - x2)^2 + (y1 - y2)^2 < (radius1 + radius2)^2 but I have no idea about this.

Any help appreciated.

Upvotes: 0

Views: 225

Answers (1)

James K
James K

Reputation: 617

What you're trying to do is called "Packing" and is actually a pretty hard problem. There are a couple potential approaches you can take here.

First, you can randomly distribute them (like you are currently doing), but including a "retry" test, in which if a circle overlaps another, you try a new location. Since it's possible to end up in an impossible situation, you would also want a retry limit at which point it gives up, goes back to the beginning, and tries randomly placing them again. This method is relatively easy, but has the down-side that you can't pack them very densely, because the chances of overlap become very very high. If maybe 1/3 of the total area is covered by circle, this could work.

Second, you can adjust the position of previously placed circles as you add more. This is more equivalent to how this would be accomplished physically -- as you add more you start having to shove the nearby ones out of the way in order to fit the new one. This will require not just finding the things that your current circle hits, but also the ones that would be hit if that one was to move. I would suggest something akin to a "springy" algorithm, where you randomly place all the circles (without thinking about if they fit), and then have a loop where you calculate overlap, and then exert a force on each circle based on that overlap (They push each other apart). This will push the circles away from each other until they stop overlapping. It will also support one circle pushing a second one into a third, and so on. This will be more complex to write, but will support much more dense configurations (since they can end up touching in the end). You still probably need a "this is impossible" check though, to keep it from getting stuck and looping forever.

Upvotes: 2

Related Questions