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:

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 is less than or equal to the sum of the radius of A in the x direction and the radius of B in the x direction ; then bounding boxes A and B are aligned such that they share common coordinates in the x plane. We can write this like so: . Using this same train of thought we can make a similar statement for the y plane; . 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 which can be represented as follows:

The radius 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:

this can then be further reduced to the following:

Similarly we can can derive a formula like this for :

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:

this can then be reduced to the following:

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

this can then be reduced to the following:

We can now take the formula and put it all together:

this can then be reduced to the following:

Lets call this condition 1.

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

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 //Second bounding box, top left corner, bottom right corner var rabx = Math.abs(ATLx + ABRx – BTLx – BBRx); //rAx + rBx //rAy + rBy if(rabx <= raxPrbx && raby <= rayPrby) |

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.

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

I think this fails for fully contained polygons at lat/lng in the mid-US.

This is for bounding boxes and not polygons. If you want to do a check if polygons overlap then take a look at the point in polygon algorithm I wrote about in this documentation: http://msdn.microsoft.com/en-us/library/cc451895.aspxhttp://msdn.microsoft.com/en-us/library/cc451895.aspx

Hi, Can we find area of a bounding box using its coordinates?

Yes, but it requires a lot more math. Basically you will want to calculate the area of triangles on a sphere (earth). you can find the math for this here: http://www.robertobigoni.eu/Matematica/Spherical/spherical.html

How does this work when the boxes overlap poles or international date line?

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.