Great circle and distances

I reckon that techies sometimes go overboard in accuracy!
Many sites use so-called Great-Circle calculations to find places within a certain distance of a specified location. The resulting queries tend to do full table scans with relatively few actual matches, then order by distance and page or limit that.

If, instead, you use a bounding rectangle and also pretend that earth is flat, life becomes much easier. The resulting queries then will use range scans on indexes. So much faster you wouldn’t believe it.

What’s the difference? Well, accuracy.
For short distances, the earth’s curvature is not significant.
Apart from that, the maximum deviation from the radius is (SQRT(POWER(r,2) * 2) – r) where r is the radius, simply applying Pythagoras’ Theorem.
It comes down to a deviation of about 20 kilometers when looking in a 50 km radius in the extreme corners.

So, if you’re looking for a hotel in the area, or a date (or both ;-), does this extra distance matter? Probably not.
Yes, the effective maximum distance can be 70 instead of 50, but that’s “as the crow flies” anyway.
Imagine if there’s a river between your central location and a hotel, with a few bridges in town – how much further would you need to drive to get to the hotel? Sites don’t take that into account either… absolute proximity is a very relative matter.

Naturally, you shouldn’t use this shortcut on its own for larger distances.
What you can do though is use this trick to efficiently do the initial search, then perform the more accurate great-circle calculation on those results. That’s an extra step, but believe me, it’ll still be much faster.
It can also still be done within a single query.

Please do feel free to post comments about your particular encounter of this problem in your application; and if you have timing information from how you solved the issue in your case, that’d be great.

By the way, I know you could optimise this in some RDBMS with 3D GIS queries, however it should still be more efficient (quicker) to use the shortcut. Popular GIS platforms (such as MAPINFO) use bounding rectangles for pretty much everything under the hood, too…

2 thoughts on “Great circle and distances

  1. Could you give an example of the end query you are describing, using bounding box for the initial search and factoring in the curvature for the narrowed down results, all in one query ? Using for example lat1 long1, lat2 long2 ?

  2. Nah – I firmly believe in people doing their own homework. The information is there, and if you work the rest out yourself, that’s a good exercise that improves your SQL skills.
    If *I* do it all for you, why would *you* get paid for it? ;-)
    I’m happy to write complete query constructs based on your needs, as a short consulting gig. See http://openquery.com.au/
    Good luck!

Comments are closed.