How to make sure randomly generated Divs don't overlap

Question

I am currently working on a website, that works with randomly generated div-placement. I worked out some JavaScript code to place the divs according to the user's screen size. I have also implemented various method's to check wether two divsoverlay each other. The objective is two have every div not-overlaying any other ⇒ if 'getOverlap' returns true, the coordinates need to be generated again.

I am not quite sure how to generate new coordinates as long as there are overlaying divs. The for-loop in the driver code checks every element against every other element while ignoring duplictates (#a == #b and #b == #a for example).

Problematic is the part of the code that should "come up" with unique coordinates: I can't get a version to work that actually does not overlap in the end. I've tried to do it recursively, with no success.

Note: this is the first larger-scale JS project I am approaching. If you have any suggestions on how to improve the general code, please let me know :)

JSFiddle: https://jsfiddle.net/timlwsk/7bokp6wr/2/

MWE:


    
        Div1
        Div2
        Div3

user_16584778 · Answer

Interestingly you have all of the code that you need to achieve this already. That is two things:

A function to check if rectangles overlap. That's already in the code: getOverlap
A way to check if a new rectangle placement would overlap with an existing one. That's essentially the same as the final loop.

So all I've done is add some code into the div placement loop, which makes it look at every previous div, to see if they would overlap. If they would overlap, it just generates a new position. This continues until a free location is found.

If no location is found after 50 attempts, the rectangle will be randomly placed anywhere, even if it overlaps. This ensures that we don't end up in an infinite loop, which would occur if the window was tiny and there wasn't enough room to place all rectangles in a non-overlapping way.

I've also increased the amount of rectangles to five, which increases the chance for a collision.

That's here:

(I've made the divs smaller in this version, because the snippet window is very small.)

 // Returns largest div's width and height
 function getMaxDimension(arr) {
   var maxWidth = 0;
   for (var i = 0; i < div_selection.length; i++) {
     if (div_selection[i].offsetWidth > maxWidth) {
       maxWidth = div_selection[i].offsetWidth;
     }
   }
   var maxHeight = 0;
   for (var i = 0; i < div_selection.length; i++) {
     if (div_selection[i].offsetHeight > maxHeight) {
       maxHeight = div_selection[i].offsetHeight;
     }
   }
   var values = {
     maxWidth: maxWidth,
     maxHeight: maxHeight
   };
   return values;
 }

 // Retruns a random number x; min < x < max
 function getRandomNumber(min, max) {
   return Math.random() * (max - min) + min;
 }

 // returns the position in xy-space of every corner of a rectangular div
 function getOffset(element) {
   var position_x = element.offsetLeft;
   var position_y = element.offsetTop;
   var height_x = element.offsetWidth;
   var height_y = element.offsetHeight;
   var tolerance = 0; // will get doubled
   return {
     A: {
       y: position_y - tolerance,
       x: position_x - tolerance
     },
     B: {
       y: position_y + height_x + tolerance,
       x: position_x - tolerance
     },
     C: {
       y: position_y + height_x + tolerance,
       x: position_x + height_y + tolerance
     },
     D: {
       y: position_y - tolerance,
       x: position_x + height_y + tolerance
     }
   };
 }


 // Returns true if any corner is inside the coordinates of the other div
 function getOverlap(div1, div2) {
   coor_1 = getOffset(document.getElementById(div1));
   coor_2 = getOffset(document.getElementById(div2));
   return (
     (coor_1.A.x <= coor_2.A.x && coor_2.A.x <= coor_1.D.x) && (coor_1.A.y <= coor_2.A.y && coor_2.A.y <= coor_1.B.y) ||
     (coor_1.A.x <= coor_2.B.x && coor_2.B.x <= coor_1.D.x) && (coor_1.A.y <= coor_2.B.y && coor_2.B.y <= coor_1.B.y) ||
     (coor_1.A.x <= coor_2.C.x && coor_2.C.x <= coor_1.D.x) && (coor_1.A.y <= coor_2.C.y && coor_2.C.y <= coor_1.B.y) ||
     (coor_1.A.x <= coor_2.D.x && coor_2.D.x <= coor_1.D.x) && (coor_1.A.y <= coor_2.D.y && coor_2.D.y <= coor_1.B.y)
   );
 }

 // Number to Letter
 function getChar(n) {
   var ordA = 'a'.charCodeAt(0);
   var ordZ = 'z'.charCodeAt(0);
   var len = ordZ - ordA + 1;

   var s = "";
   while (n >= 0) {
     s = String.fromCharCode(n % len + ordA) + s;
     n = Math.floor(n / len) - 1;
   }
   return s;
 }

 var div_selection = document.getElementsByClassName("random");

 maxDimensions = getMaxDimension(div_selection);
 var widthBoundary = maxDimensions.maxWidth;
 var heightBoundary = maxDimensions.maxHeight;

 for (var i = 0; i < div_selection.length; i++) {
   var isOverlapping = false;
   var attemptCount = 0;
   do {
     randomLeft = getRandomNumber(0, window.innerWidth - widthBoundary);
     randomTop = getRandomNumber(0, window.innerHeight - heightBoundary);
     div_selection[i].style.left = randomLeft + "px";
     div_selection[i].style.top = randomTop + "px";     
     isOverlapping = false;
     for (var j = 0; j < i; j++) {
        if (getOverlap(getChar(i), getChar(j))) {
        isOverlapping = true;
        break;
      }
     }
   } while (++attemptCount < 50 && isOverlapping);
 }

 // check every element
 for (var i = 0; i < div_selection.length; i++) {
   for (var j = i + 1; j < div_selection.length; j++) {
     console.log(i, j)
     console.log(getChar(i), getChar(j))
     console.log(getOverlap(getChar(i), getChar(j)))
   }
 }

div {
  width: 60px;
  height: 60px;
  position: absolute;
}

#a {
  background-color: pink;
}

#b {
  background-color: lightblue;
}

#c {
  background-color: lightgreen;
}

#d {
  background-color: silver;
}

#e {
  background-color: yellow;
}



  
    Div1
    Div2
    Div3
    Div4
    Div5

How to make sure randomly generated Divs don't overlap

1 Answers