Place divs random without overlaying

i want to place divs on the window randomly without overlay. therfore im creating some arrays, with

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

so im giving all of them a random position and i calculate all of the cornerpoints. after that i calculate within two loops if one of the corners of one div is inside another div, and if this is true, im giving a new random position, as long as it does not overlay with another div.

here is the code:

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++;

                    };
                }
            }
        }

开发者_开发百科

after that im positioning the divs with the created vars. but there are still overlaying divs. is there something wrong with my logic or is it just not written correctly?

thanks for help and sorry for the bad english :)

---

I think the algorithm would run faster if you check for DIV collisions as you are adding them to the window. Instead of pacing them randomly and then checking to see if there are any collisions, randomly calculate the position of each DIV and check to see if that position collides before adding it. If it does, recalculate a new position and check again. I think this reduces the big-O from N^2 to N * log( N ).

Edit - Here's some sample code:

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
}

I have not tested it for correctness, just wrote it off the top of my head. Hopefully it will give you an idea where you went wrong.