How to distribute words in a fixed size area?

Question

I have a list of words and I need to distribute them in an area of fixed dimensions so that it looks like they were randomly arranged in that space. However, I need to make sure that the words do not fit, and that there are no large blank "holes" in the area. The result should be visually harmonious.

With a CSS simple, I get a result stuck too much to the grid:

While what I’m looking for is something like this:

Is there a classic algorithm that allows me to distribute the words in space, with absolute positioning, getting a result close to what I’m looking for?

Answer 1

The first thing to do is to find out the height and width on the screen of each word. That answer in the SOEN shows a possible path (create a div with the word and measure their clientWidth and clientHeight).

var palavras = [];
var larguraTotal = 0;
var alturaMaxima = 0;
$('li').each(function() {
    palavras.push({
        elemento:this,
        largura:this.clientWidth,
        altura:this.clientHeight
    });
    larguraTotal += this.clientWidth;
    alturaMaxima = Math.max(alturaMaxima, this.clientHeight);
});

Once this is done, you need to figure out the most "harmonious" way to distribute your words on the screen (i.e. don’t leave them "tight" horizontally and "loose" vertically, or vice versa). One way - not necessarily the best way - would be:

var linhas = 0;
do {
    linhas++;
    var horizontal = larguraTotal / linhas / larguraConteiner;
    var vertical = linhas * alturaMaxima / alturaConteiner;
} while ( vertical < horizontal*0.8 ); // Esse 0.8 é uma "folga"

Now it’s backpack problem! Good, almost... You need to choose, for each line, a set of words that approaches the desired width (larguraConteiner * horizontal). I suggest we start with the bigger ones, because it’s easier to fit the smaller ones later.

var distribuicao = [];
for ( var i = 0 ; i < linhas ; i++ )
    distribuicao.push({ palavras:[], larguraTotal:0 });
function minima() {
    var min = 0;
    for ( var i = 1 ; i < distribuicao.length ; i++ )
        if ( distribuicao[i].larguraTotal < distribuicao[min].larguraTotal )
            min = i;
    return distribuicao[min];
}

palavras.sort(function(a,b) { return b.largura - a.largura; });
for ( var i = 0 ; i < palavras.length ; i++ ) {
    var min = minima();
    min.palavras.push(palavras[i]);
    min.larguraTotal += palavras[i].largura;
}

Finally, we will distribute the words across the screen. I will do this using absolute positioning, but you can think of another way too.

var alturaSobrando = alturaConteiner - linhas*alturaMaxima;
var alturaAntes = alturaSobrando / linhas / 2;
for ( var i = 0 ; i < distribuicao.length ; i++ ) {
    var larguraSobrando = larguraConteiner - distribuicao[i].larguraTotal;
    var larguraAntes = larguraSobrando / distribuicao[i].palavras.length / 2;

    var top = alturaAntes + i*(2*alturaAntes + alturaMaxima);
    var left = larguraAntes;
    for ( var t = 0 ; t < distribuicao[i].palavras.length ; t++ ) {
        var palavra = distribuicao[i].palavras[t];
        $(palavra.elemento).css({
            position: "absolute",
            top: top,
            left: left
        });
        left += 2*larguraAntes + palavra.largura;
    }
}

Quite homogeneous, no? Now, we have a margin of manoeuvre to randomize each word. There is a space of larguraAntes before and after each word. Iofc alturaAntes. I will use half of this space (here you evaluate what is interesting, aesthetically speaking, in my opinion using the whole space has left the appearance kind bizarre).

        top: top + Math.floor(Math.random()*alturaAntes - alturaAntes/2),
        left: left + Math.floor(Math.random()*larguraAntes - larguraAntes/2)

Final result. Each of these steps can be improved, if desired, I did not spend much time with each of them not. In addition, some boundary conditions I think may be bugged (for example, when testing using the whole space, some words came out of the container) - but in the example above I believe this does not occur.

Answer 2

A simple solution is to apply a random offset smaller than the margin:

function getRandomInt(min, max) {
  return Math.floor(Math.random() * (max - min + 1) + min);
}
function rand() {
    return getRandomInt(-20, 20);
}

$('li').each(function() {
    $(this).css({
        'position': 'relative',
        'left': rand() + 'px',
        'top': rand() + 'px',
    });
});

Fiddle

A more complete solution is to calculate and sum the width of the elements, distributing them in lines according to the average of the widths. Then, in each row, the elements are distributed as if they were an independent table of the other lines.

I don’t know if I can explain the algorithm well, so I’m going to post the code:

function getRandomInt(min, max) {
  return Math.floor(Math.random() * (max - min + 1) + min);
}
function rand(n) {
    return getRandomInt(-n, n);
}

//calcula tamanhos dos itens para distribuição
var itens = [];
var larguraTotal = 0;
$('li').each(function(i) {
    var $this = $(this);
    larguraTotal += $this.width();
    itens.push({
        item: $this,
        width: $this.width(),
        height: $this.height()
    });
});

//define a quantidade de linhas
var linhas = Math.ceil(Math.sqrt(itens.length));
var larguraMedia = larguraTotal / linhas;

//faz a distribuição dos elementos nas linhas de uma grid imaginária
var grid = [ [] ];
grid[0].largura = 0;
for (var i = 0, larguraConsumida = 0, linha = 0, coluna = 0, proximaQuebra = larguraMedia; i < itens.length; i++) {
    var item = itens[i];

    //quebra a linha, caso mais da metade do elemento ultrapasse a média
    if (larguraConsumida + item.width / 2 > proximaQuebra) {
        linha++;
        grid[linha] = [];
        grid[linha].largura = 0;
        coluna = 0;
        larguraLinha = 0;
        proximaQuebra = larguraMedia * (linha + 1);
    } else {
        coluna++;
    }
    //armazena a largura 
    grid[linha].largura += item.width;
    larguraConsumida += item.width;
    grid[linha].push(item);

}

//coloca os elementos na posição final (uma célula do container)
var container = $('ul');
//a largura da célula (local onde o item deve ser inserido)
var larguraCelula = container.height() / grid.length;
for (var i = 0; i < grid.length; i++) {

    var linha = grid[i];
    //altura da célula (local onde o item deve ser inserido)
    var alturaCelula = container.width() / linha.length;
    //calcula o espaço horizontal que tem para randomizar, isto é, o espaço em branco até onde não enconsta no próximo elemento
    //deve dividir por 2 pela possibilidade do outro elemento também poder se aproximar, mas multiplicando por 0.4 garante que não vão encostar um no outro
    var espacoLivreEntreElementos = (container.width() - linha.largura) / linha.length * 0.4;
    //itera sobre os itens da linha    
    for (var j = 0; j < linha.length; j++) {

        var item = linha[j];
        //calcula o espaço vertical em branco para randomizar, usando o mesmo princípio anterior
        var espacoLivreVertical = (larguraCelula - item.height) * 0.4;
        item.item.css({
            position: 'absolute',
            //posiciona o item horizontalmente no meia da célula e randomiza no espaço que sobra
            left: (j + 0.5) * alturaCelula
                - item.width / 2 
                + rand(espacoLivreEntreElementos) + 'px',
            //posiciona o item verticalmente no meia da célula e randomiza no espaço que sobra
            top: (i + 0.5) * larguraCelula
                - item.height / 2 
                + rand(espacoLivreVertical) + 'px'
        });
    }
}

Fiddle

---

Random result 1

---

Random result 2

Answer 3

Based on your fiddle, I decided to try to get the words to move from their original points, randomly at any angle, at a fixed distance of 25px, and the result until it was good:

jsfiddle

Code:

CSS:

li {
    position: relative;
}

Javascript:

var randomCoordsInACircle = function(cx, cy, radius) {
  var r2 = radius*Math.sqrt(Math.random());
  var angle = 2*Math.PI*Math.random();

  return {
    angle: angle,
    x: (r2 * Math.cos(angle) + cx),
    y: (r2 * Math.sin(angle) + cy)
  }
};

$(function () {
    $('li').each(function () {
        var rnd = randomCoordsInACircle(0,0,25);
        $(this).css({
            left: rnd.x.toFixed(0)+'px',
            top: rnd.y.toFixed(0)+'px'
        });
    });
})

Reference:

Random point Within a Circle, Even Distribution, no problem, in javascript.

Answer 4

I think the simplest solution is to put all words in a paragraph instead of a list, and put the text-align attribute into Justified. I used this solution precisely to show a cloud tag with most searched topics about Javascript.

<div style="text-align: justified; width: 20em">C C++ Java PHP JavaScript Lisp Scheme Haskell Lua Python Ruby Delphi Cobol</div>