CODEWITHSUNDEEP
algorithmgoogle-mapsgeometrybounding-box
Bryce Thomas
Bryce Thomas

Reputation: 10799

Calculating radius of smallest circle encompassing a North-East/Sout-West based bounding rectangle on Earth

I have a webpage that I am using a Google Map on. When the user drags the map and lets go, I need to query a server for all data points that fall within the bounds of the visible region of the map. I can quite easily get the North-East and South-West coordinate of the visible region of the map through the javascript API, essentially providing a bounding rectangle. However on the server, I am relying on a database whose geographic query API only supports queries in the form of a center point and a radius. So basically what I would like to do is figure out the minimum radius circle I would need to at least encompass the North-East and South-West points.

The simplest algorithm I thought of involved finding the center point between the NE and SW coordinate and then measuring the radius as the distance from the center point to either the NE or SW coordinate. In a simple euclidean space I'd be comfortable doing this, but I think I'd probably get something wrong with the Earth's non-flat coordinate system. I haven't even been able to convince myself that if I knew that centerpoint that the distance would be the same between the center and NE and the center and SW.

I've come across algorithms for smallest circles on a flat 2D surface and also algorithms describing the opposite i.e. bounding box from circle center and radius. I haven't come across a concise algorithm for this particular problem though.

Upvotes: 2

Views: 1201

Answers (1)

M Oehm
M Oehm

Reputation: 29126

I assume what you call the east-west and north-south coordinates are the longitude and latitude. You can convert them to Cartesian points and find the midpoint between the edge points of your region. This will yield a point C' below Earth's surface with the same latitude and longitude as your centre point C. (This will only work if the difference of your longitudes is smaller than 180°, however; otherwise you'll get a point on the opposite side of the earth, but with the same latitude.) If you need Cartesian coordinates for your centre point, you can project C' onto the surface by adjusting the radius to find your new centre point.

The distance bewteen the two points on the surface of Earth can be calculated with the great-circle disnatce formula.

Transformation is easy if you assume that Earth is a perfect sphere with radius R = 6373 km:

x = R * cos(lat) * cos(lon)
y = R * cos(lat) * sin(lon)
z = R * sin(lat)

and back:

lon = atan2(y, x)
lat = atan2(z, r) with r = sqrt(x*x + y*y)

(But Earth does not have a constant radius, so you might want to use a better coordinate system, maybe ECEF as explained in this answer if you need more precision.)

My first thought was to find your midpoint in terms of longitude and latitude, which should be okay if you take care of wrapping for the latitude. Then you calculate your distance accpording to the great-circle formula. But averaging the longitudes and latitudes does not seem to be sensible if your map region includes a pole.

Upvotes: 1

Related Questions