Generate numbers in side div at random position without overlapping

Question

I want to display random numbers inside a div at random positions without overlapping. I am able to display random number at random position but its going outside the box and overlapping each other.

Here is my code:

JS Fiddle

var width = $('.container').innerWidth();
var height = $('.container').innerHeight();

(function generate() {     // vary size for fun
    for (i = 0; i < 15; i++) {
        var divsize = 12;
        var color = '#' + Math.round(0xffffff * Math.random()).toString(16);
        $newdiv = $('<div/>').css({
            'width': divsize + 'px',
                'height': divsize + 'px'
        });

        // make position sensitive to size and document's width
        var posx = (Math.random() * (width - divsize)).toFixed();
        var posy = (Math.random() * (height - divsize)).toFixed();

        $newdiv.css({
            'position': 'absolute',
                'left': posx + 'px',
                'top': posy + 'px',
                'float': 'left'
        }).appendTo('.container').html(Math.floor(Math.random() * 9));
    }
})();

How can I do this?

Answer 1

You've got most of it figured out. You just need to think of the .container div as a grid to avoid any overlap or outlying items.

Just check out this fiddle.

Here's what the code looks like:

var tilesize = 18, tilecount = 15;
var gRows = Math.floor($(".container").innerWidth()/tilesize);
var gCols = Math.floor($('.container').innerHeight()/tilesize);

var vals = _.shuffle(_.range(tilecount));
var xpos = _.shuffle(_.range(gRows));
var ypos = _.shuffle(_.range(gCols));

_.each(vals, function(d,i){
    var $newdiv = $('<div/>').addClass("tile");
    $newdiv.css({
        'position':'absolute',
        'left':(xpos[i] * tilesize)+'px',
        'top':(ypos[i] * tilesize)+'px'
    }).appendTo( '.container' ).html(d);  
});

PS:I have used underscore in my fiddle to make things easier for me and because I personally hate writing for loops.

Answer 2

If the number of divs you need to create is small enough (i.e. you're not risking that they won't fit) then a simple algorithm is:

• pick a random position (x0, y0)-(x1, y1)
• check if any previously selected rect overlaps
• if none overlaps then add the rect, otherwise loop back and choose another random position

in code

var selected = [];

for (var i=0; i<num_divs; i++) {
    while (true) {
        var x0 = Math.floor(Math.random() * (width - sz));
        var y0 = Math.floor(Math.random() * (height - sz));
        var x1 = x0 + sz;
        var y1 = y0 + sz;
        var i = 0;
        while (i < selected.length &&
               (x0 >= selected[i].x1 ||
                y0 >= selected[i].y1 ||
                x1 <= selected[i].x0 ||
                y1 <= selected[i].y0)) {
            i++;
        }
        if (i == selected.length) {
            // Spot is safe, add it to the selection
            selected.push({x0:x0, y0:y0, x1:x1, y1:y1});
            break;
        }
        // The choice collided with a previously added div
        // just remain in the loop so a new attempt is done
    }
}

In case the elements are many and it's possible to place n-1 of them so that there's no position where to put n-th element then things are a lot more complex.

For the solution of the 1-dimensional version of this problem see this answer.