Determining if two bounding boxes overlap

Often when displaying polygons you only need or want to show the polygons that are in the viewable area of the map. By doing this an increase in performance should occur with the map control as there will be less data that will need to be handled by the control. One method to go about this is to store the bounding coordinates of your polygon compare then to the bounding box of the viewable map. This leaves you with the task of determining if two bounding boxes overlap which should be much easier than determining if a polygon with any number of sides is in the map view. What this blog is meant to do is to present a mathematical solution to this problem.

For this solution we need to break a bounding box into some key components. A bounding box has a center point and two important radii’s. A radius from the center point to and edge in the x direction, and a radius in from the center point to and edge in the y direction. The following diagram illustrates this:

 bbox

By looking at this diagram we can derive two key logical statements about how to determine if two bounding boxes overlap. The first statement is that if the radius from the center of bounding box A to bounding box B clip_image002[9] is less than or equal to the sum of the radius of A in the x direction clip_image002[11]and the radius of B in the x direction clip_image002[13]; then bounding boxes A and B are aligned such that they share common coordinates in the x plane. We can write this like so: clip_image002[17]. Using this same train of thought we can make a similar statement for the y plane; clip_image002[15]. If both of these statements are true then bound bounding boxes must overlap or share a common edge.

We can calculate the x coordinate of the center point by adding the top left x value to the radius on the bounding box in the x direction. We can then determine the distance between centers by taking the absolute value of the different between the x coordinates of the center points of bounding box A and B. This gives use the distance clip_image002[9] which can be represented as follows:

clip_image002

The radius clip_image002[11] can be calculated by taking the difference between the top left x coordinate and the bottom right x coordinate and dividing it by 2. By applying this to the above formula we get the following:

clip_image002[6]

this can then be further reduced to the following:

clip_image002[8]

Similarly we can can derive a formula like this for clip_image002[10]:

clip_image002[12]

Now we can look at the other side of the equation where we add the radii’s of bounding box A and B. Doing this we get the following for the x direction:

clip_image002[14]

this can then be reduced to the following:

clip_image002[16]

Doing the same for the y direction we get the following:

clip_image002[18]

this can then be reduced to the following:

clip_image002[20]

We can now take the formula clip_image002[17] and put it all together:

clip_image002[32]

this can then be reduced to the following:

clip_image002[34]

Lets call this condition 1.

Doing the same for the y direction we get the following:

clip_image002[36]

Lets call this condition 2.

Now if both condition 1 and condition 2 are true then the bounding boxes A and B must overlap.

We can now create a simple function that takes in two VELatLongRectangle objects and returns boolean depending on if the two bounding boxes overlap.

function DoBoundingBoxesIntersect(bb1, bb2) {

                //First bounding box, top left corner, bottom right corner
                var ATLx = bb1.TopLeftLatLong.Longitude;
                var ATLy = bb1.TopLeftLatLong.Latitude;
                var ABRx = bb1.BottomRightLatLong.Longitude;
                var ABRy = bb1.BottomRightLatLong.Latitude;

                //Second bounding box, top left corner, bottom right corner
                var BTLx = bb2.TopLeftLatLong.Longitude;
                var BTLy = bb2.TopLeftLatLong.Latitude;
                var BBRx = bb2.BottomRightLatLong.Longitude;
                var BBRy = bb2.BottomRightLatLong.Latitude;

                var rabx = Math.abs(ATLx + ABRx – BTLx – BBRx);
                var raby = Math.abs(ATLy + ABRy – BTLy – BBRy);

                //rAx + rBx
                var raxPrbx = ABRx – ATLx + BBRx – BTLx;

                //rAy + rBy
                var rayPrby = ATLy – ABRy + BTLy – BBRy;

                if(rabx <= raxPrbx && raby <= rayPrby)
                {
                                return true;
                }
                return false;
}

Advertisements

9 thoughts on “Determining if two bounding boxes overlap

  1. A simpler method, cost of 4 comparisons and 3 boolean ORs.
    Instead of 2 function calls, 4 adds, 4 or 12 assignments, and 8 subtractions, 1 boolean AND and 2 comparisons.

    Using a highly optimized form of the separating axis theorem (I guess)…

    where a and b are {x1,y1,x2,y2}

    if(a[0] > b[2] || b[0] > a[2] || a[1] > b[3] || b[1] > a[3])
    return false;
    return true;

    alternatively
    if(ax1 > bx2 || bx1 > ax2 || ay1 > by2 || by1 > ay2)
    return false;
    return true;

    Basically there are 2 tests for each box that if true the boxes cannot possibly intersect/overlap. The tests are the same for each axis. If foos minimal value is greater then bars largest value along that axis, then foo and bar cannot ever possibly intersect.
    Do this for both axis on each box, 4 tests, no intersection.

    • I actually started out with that formula but found that it failed often when using this in GIS situations. Bounding boxes on the surface of the earth are not truely symetrical like bounding boxes on a flat 2D plane. The solution I have proposed tends be more accurate in when the bounding boxes are on a curved surface.

  2. Pingback: Les index spatiaux dans SQL Server 2012 / SQL Azure | Codelicious

    • This is an old code sample from a map control that only supported a single map and no wrap around the international date line. As such there was no need for it to support the international date line. Also, this blog post was written for Bing Maps v6.3, avoid doing any new development on that legacy API as it’s very old and likely to be retired in the near future.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s