CODEWITHSUNDEEP
java
dambros
dambros

Reputation: 4392

How to check if lng/lat bounding box intersects with another?

Assume I have several bounding boxes with 4 coordinates pair (long/lat only) each representing the 4 corners of a square box. How can I check if 2 of those boxes intersects?

I know I could use java.awt.Rectangle to check if 2 rectangles intersects, but the problem is it is calculated using X/Y/Width/Height instead of coordinates.

Can someone please give me some directions on how can I do this calculations?

Thanks.

EDIT

What I am trying to accomplish is the same represented by this library.

Basically it calculates a square bounding box around a given point and check if the (imaginary) squares intersects with each other, like in this image:

enter image description here
(source: google.com)

So far I've been able to calculate the corners for each marker and now I need to somehow check if they intersect with each other. How can I do this intersection calculation?

EDIT 2

This is how I am calculating the corners:

private static double getLatitude(double distance, double lat, double angle) {
    return toDegrees(asin(sin(toRadians(lat)) * cos(distance / RADIUS) + cos(toRadians(lat)) * sin(distance / RADIUS) * cos(toRadians(angle))));
}

private static double getLongitude(double distance, double lat, double lng, double angle) {
    double newLat = getLatitude(distance, lat, angle);
    return toDegrees(toRadians(lng) + atan2(sin(toRadians(angle)) * sin(distance / RADIUS) * cos(toRadians(lat)), cos(distance / RADIUS) - sin(toRadians(lat)) * sin(toRadians(newLat))));
}

Where RADIUS = 6378.1 and angle = 45/135/225/315 (top right, bottom right, bottom left and top left).

Example output

Upvotes: 2

Views: 2490

Answers (1)

DJClayworth
DJClayworth

Reputation: 26886

I'm assuming that in your "lat/long bounding box' each side follows the lines of constant longitude and latitude - in other words that the top side follows the line of constant latitude, and the left side the line of constant longitude.

While this is not actually a rectangle in real life, it can actually be treated as one for our purposes. Mathematically you can think of this as transforming the bounding box into a "lat/long' space, where the shape is in fact a rectangle. If that doesn't make sense you may have to take my word for it. In any case it is possible to show that the curved shapes in real space intersect if and only if the rectangles intersect in curved space.

The short version of this is: if you do a standard test for intersection of rectangles (using the Java Rectangle class code, and using latitude and longitude as the rectangle bounds) you will get the right result.

EXAMPLE

You have two areas, defined as:

  1. The area between 50 and 52 degrees N and 75 and 77 degrees E
  2. The area between 51 and 53 degrees N and 76 and 79 degrees E

You can correctly test for their intersection by doing:

Rectangle r1 = new Rectangle(75,50,2,2);
Rectangle r2 = new Rectangle(76,51,2,3);
boolean intersects = r1.insersects(r2);

It doesn't matter that the rectangles are not rectangular in Euclidean space.

P.S. This will not work if one of your rectangles actually contains either the north or south pole. In that case you will need to split each rectangle into two, one on each side of the pole. You need to normalize everything to +/- 90 latitude and +/- 180 longitude. You will need to do something clever if one or more of the rectangles overlaps the +/-180 longitude line.

Upvotes: 2

Related Questions