Radius of multiple latitude/longitude points

Question

I have a program that takes as input an array of lat/long points. I need to perform a check on that array to ensure that all of the points are within a certain radius. So, for example, the maximum radius I will allow is 100 miles. Given an array of lat/long (coming from a MySQL database, could be 10 points could be 10000) I need to figure out if they will all fit in a circle with radius of 100 miles.

Kinda stumped on how to approach this. Any help would be greatly appreciated.

Answer 1

Find the smallest circle containing all points, and compare its radius to 100.

Answer 2

Check out the answers to this question. It gives a way to measure the distance between any two (lat,long) points. Then use a smallest enclosing circle algorithm.

I suspect that finding a smallest enclosing circle may be difficult enough on a plane, so to eliminate the subtleties of working with latitude and longitude and spherical geometry, you should probably consider mapping your points to the XY plane. That will introduce some amount of distortion, but if your intended scale is 100 miles you can probably live with that. Once you have a circle and its center on the XY plane, you can always map back to the terrestial sphere and re-check your distances.

Answer 3

It's easiest way for me to solve this is by converting the coordinates to (X,Y,Z), then finding the distance along a sphere.

Assuming Earth is a sphere (totally untrue) with radius R...

X = R * cos(long) * cos(lat)

Y = R * sin(long) * cos(lat)

Z = R * sin(lat)

At this point, you can approximate the distance between the points using the extension of the pythagorean theorem for threespace:

dist = sqrt((x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2)

But to find the actual distance along the surface, you're going to need to know the angle subtended by the two points from the origin (center of the Earth).

Representing your locations as vectors V1 = (X1, Y1, Z1) and V2 = (X2, Y2, Z2), the angle is:

angle = arcsin((V1 x V2) / (|V1||V2|)), where x is the cross-product.

The distance is then:

dist = (Earth's circumference) * angle / (2 * pi)

Of course, this doesn't take into account changes in elevation or the fact that the Earth is wider at the equator.

Apologies for not writing my math in LaTeX.