Efficient way of testing whether a list of divs are overlapping with a particular div

Question

Suppose I have a particular div (target) that I can move around using an input device (in my case, the div moves according to the position of my finger using a Leap Motion), and I want to know when the div overlaps with other divs (obstacles) on the page.

I've written a simple function to test when two divs are overlapping, and if there are only a few obstacle divs on the page, we could probably get away with using the function to test all the obstacle divs on the page vs the target div. However, this can quickly get expensive when there are many items on the page, especially if we are calling the function on every tick (Leap Motion calls the function 60 times a second).

I'm wondering what methods we could use to speed up the process? I'm thinking of a) since the obstacle divs on the page do not move, we could calculate the coordinates of the obstacle divs just once and then cache the results instead of recalculating on each call, b) we could model the obstacle divs as a binary tree sorted by their x-coordinates. This way, we don't need to test all the obstacle divs and only test those that are near the vicinity of the moving div.

Just wanted to ask if there are better ways to do this?

function overlapHelper($obj, $obstacle) {
  var xAxisOverlapping, yAxisOverlapping;

  var $objCoordinates = {
    left: parseInt($obj.css('left'), 10),
    top: parseInt($obj.css('top'), 10),
    right: parseInt($obj.css('left'), 10) + $obj.width(),
    bottom: parseInt($obj.css('top'), 10) + $obj.height()
  };

  var $obstacleCoordinates = {
    left: parseInt($obstacle.css('left'), 10),
    top: parseInt($obstacle.css('top'), 10),
    right: parseInt($obstacle.css('left'), 10) + $obstacle.width(),
    bottom: parseInt($obstacle.css('top'), 10) + $obstacle.height()
  }


  xAxisOverlapping = ($objCoordinates.left >= $obstacleCoordinates.left && $objCoordinates.left <= $obstacleCoordinates.right)
    || ($objCoordinates.right >= $obstacleCoordinates.left && $objCoordinates.right <= $obstacleCoordinates.right);


  yAxisOverlapping = ($objCoordinates.bottom >= $obstacleCoordinates.top && $objCoordinates.bottom <= $obstacleCoordinates.bottom)
    || ($objCoordinates.top >= $obstacleCoordinates.top && $objCoordinates.top <= $obstacleCoordinates.bottom);

  return xAxisOverlapping && yAxisOverlapping;
}

Answer 1

Your needs seem to be similar to this one:

JavaScript Collision Detection

In addition to the information from the link, if the data of your obstacle divs come from somewhere in your script, you can try to cache the values right there and reduce DOM access to a minimum.