Поместите div в случайном порядке без наложения

Question

Я хочу разместить элементы div в окне случайным образом без наложения. поэтому я создавая несколько массивов, с

widthArray, heightArray, xP = xPosition, yP = yPosition, xPRT = rightCornerX (xPos + width), yPRT = rightCornerY и т. д.

так что я даю им всем случайное положение, и я вычисляю все угловые точки. после этого я рассчитываю в течение двух циклов, если один из углов одного div внутри другой div, и если это правда, я даю новую случайную позицию, пока это делает не накладывается на другой div.

вот код:

for(var i = 0; i<xP.length; i++) {  
            for(var k = 0; k<xP.length; k++) {

                if(i == k) {
                    //alert(Math.random());
                } else {

                    while((xP[i]>xP[k] && yP[i]>yP[k] && xP[i]<xPRB[k] && yP[i]<yPRB[k]) || (xPRT[i]<xPRT[k] && yPRT[i]>yPRT[k] && xPRT[i]>xP[k] && yPRT[i]<yPRB[k]) || (xPRB[i]<xPRB[k] && yPRB[i]<yPRB[k] && xPRB[i]>xP[k] && yPRB[i]>yP[i]) || (xPLB[i]>xPLB[k] && yPLB[i]<yPLB[k] && xPLB[i]<xPRB[k] && yPLB[i]>yP[k])) {
                        //alert("i: "+i+" k: "+k+" xP: "+xP[i]+" > xP2: "+xP[k]+" & yP: "+yP[i]+"  > yP2: "+yP[k]);
                        xP[i] = GetRandom(0, window.innerWidth - widthArray[i]-2);
                        yP[i] = GetRandom(0, window.innerHeight - heightArray[i]-2);

                        xPRT[i] = xP[i] + widthArray[i];
                        yPRT[i] = yP[i];

                        xPRB[i] = xP[i]+ widthArray[i];
                        yPRB[i] = yP[i]+ heightArray[i];

                        xPLB[i] = xP[i];
                        yPLB[i] = yP[i] + heightArray[i];
                        count++;

                    };
                }
            }
        }

после этого я размещаю div с созданными переменными. но все еще есть наложения div. что-то не так с моей логикой или это просто неправильно написано?

спасибо за помощь и извините за плохой английский:)

Answer 1

Я думаю, что алгоритм будет работать быстрее, если вы будете проверять наличие коллизий DIV при добавлении их в окно. Вместо того, чтобы расставлять их в произвольном порядке, а затем проверять, нет ли столкновений, случайным образом рассчитать положение каждого DIV и проверить, сталкивается ли эта позиция, прежде чем добавлять его. Если это произойдет, пересчитайте новую позицию и проверьте снова. Я думаю, что это уменьшает big-O с N ^ 2 до N * log (N).

Редактировать - вот пример кода:

function Rect( x, y, w, h )
{
  this.x = x;
  this.y = y;
  this.w = w;
  this.h = h;

  this.hitTest = function( x, y )
  {
    return( x >= this.x && x <= this.x + this.width &&
            y >= this.y && y <= this.t + this.height );
  }
}

var numDivs = 10;
var divList = new Array();

for( var i = 0 ; i < numDivs ; i++ )
{
  var doesOverlap = false;
  do
  {
    divList[i] = new Rect( Math.random() * ( window.innerWidth - 50 ), Math.random() * ( window.innherHeight - 50 ), 50, 50 );
    for( var y = 0 ; y < i && !doesOverlap ; y++ )
    {
      doesOverlap |= divList[y].hitTest( divList[i].x, divList[i].y );
      doesOverlap |= divList[y].hitTest( divList[i].x + divList[i].width, divList[i].y );
      doesOverlap |= divList[y].hitTest( divList[i].x, divList[i].y + divList[i].height );
      doesOverlap |= divList[y].hitTest( divList[i].x + divList[i].width, divList[i].y + divList[i].height );
    }
  }
  while( doesOverlap );

  // No colision, add div
}

Я не проверял это на правильность, просто списал это с моей головы. Надеюсь, это даст вам представление о том, где вы ошиблись.