javascript - 随机放置div而不覆盖

Question

我想将 div 随机放置在窗口上而不覆盖。因此我 创建一些数组，用

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

所以我给了他们一个随机位置，我计算了所有的 Angular 点。 之后，如果一个 div 的 Angular 之一在里面，我会在两个循环内计算 另一个 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 冲突，算法会运行得更快。不是随机调整它们然后检查是否有任何碰撞，而是随机计算每个 DIV 的位置并在添加之前检查该位置是否发生碰撞。如果是，请重新计算新位置并再次检查。我认为这会将大 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
}

我还没有测试它的正确性，只是把它从我的脑海中写下来。希望它能让您知道哪里出错了。