2

I have an SQLite database, which does not support trig functions. I would like to sort a set of lat,lng pairs in my table by distance as compared to a second lat,lng pair. I'm familiar with the standard haversine distance formula for sorting lat,lng pairs by distance.

In this case I don't care particularly for precision, my points are separated by large distances, so I don't mind rounding off the distances by treating curves as straight lines.

My question, is there a generally accepted formula for this kind of query? Remember no trig functions!

Ben Holland
  • 2,309
  • 4
  • 34
  • 50
  • Could you get the distances of lat and long separately (absolute values), then apply pythag (no trig there) to get a number representing the length of the distance between the points. Ignore me if this is rubbish - don't know much about geo, but it struck me that you could treat everything as triangles. – Jon Egerton Jul 01 '11 at 14:05

4 Answers4

8

If your points are within reasonable distance of each other (i.e. not across half the world, and not across the date line), you can make a correction for the difference between latitude and longitude (as a longitude degree is shorter, except at the Equator), and then just calculate the distance as if the earth was flat.

As you just want to sort the values, you don't even have to use the square root, you can just add the squares of the differences.

Example, where @lat and @lng is your current position, and 2 is the difference correction:

select *
from Points
order by (lat - @lat) * (lat - @lat) + ((lng - @lng) * 2) * ((lng - @lng) * 2)

You can calculate the difference correction for a specific latitude as 1 / cos(lat).

Cees Timmerman came up with this formula which also works across the date line:

pow(lat-lat2, 2) + pow(2 * min(abs(lon-lon2), 360 - abs(lon-lon2)), 2)
Guffa
  • 687,336
  • 108
  • 737
  • 1,005
  • @downvoter: Why the downvote? If you don't explain what you think is wrong, it can't improve the answer. – Guffa Jul 01 '11 at 17:49
  • I don't understand why there was a downvote on this answer either. Please explain. – Ben Holland Jul 03 '11 at 15:21
  • 1
    `pow(lat - @lat, 2) + pow(2 * (lon - @lon), 2)` is shorter and different from a language var, but what is the final query that corrects for the latitude? Does this have possible Russia-Alaska issues? – Cees Timmerman Mar 29 '12 at 09:17
  • @CeesTimmerman: It's the `2 *` that corrects for the latitude. Alaska for example would have a correction value between 1.6 and 3.2, depending on the latitude. – Guffa Mar 29 '12 at 09:34
  • I see, thanks. The downvote was probably for this algorithm still going the wrong way when traveling between Russia and Alaska: pow(60 - 60, 2) + pow(2 * (150 - -150), 2) = 360000.0 – Cees Timmerman Mar 30 '12 at 09:49
  • 2
    As long as you don't cross the poles, `pow(lat - lat2, 2) + pow(2 * min(abs(lon - lon2), abs((180 - abs(lon)) + (180 - abs(lon2)))), 2)` should do. (14400.0 from Sterling to Russia.) – Cees Timmerman Apr 01 '12 at 07:48
  • @CeesTimmerman: Nice addition. I clarified the limitations of the original algorithm. – Guffa Apr 01 '12 at 07:55
  • Thanks. I improved it a bit: `pow(lat-lat2, 2) + pow(2 * min(abs(lon-lon2), 360 - abs(lon-lon2)), 2)` – Cees Timmerman Apr 01 '12 at 11:05
  • @sajanyamaha, thanks. Most servers need [this complex workaround](http://stackoverflow.com/questions/1947753/getting-the-minimum-of-two-values-in-sql), making it `square(lat-lat2) + square(2 * case when abs(lon-lon2) < 360 - abs(lon-lon2) then abs(lon-lon2) else 360 - abs(lon-lon2) end)`. – Cees Timmerman Jan 25 '13 at 16:57
  • if i may ask, why is the difference correction needed? – Fuseteam Apr 25 '16 at 14:31
  • @Fuseteam: Otherwise an east-west distance would be exaggerated compared to a noth-south distance. – Guffa Apr 26 '16 at 00:03
  • @guffa "compared to" so it's had to do with the fact that the earth is not a perfect sphere? Interesting – Fuseteam Apr 26 '16 at 01:23
  • @Fuseteam: No, it's because the earth is a sphere. The longitude values are closer together when you get closer to the poles. – Guffa Apr 26 '16 at 07:11
  • @guffa oh, I see, thanks for helping me I think I understand now – Fuseteam Apr 26 '16 at 08:24
  • now i think about it wouldn't it be easier to just define an function such that `Limitation(L,L2){if(abs(L-L2) < 360 - abs(L-L2)) abs(L-L2); else 360 - abs(L-L2);}` and then feed longitude, the latitude could be fed to similar function only 90 instead of 180, that way the limitations of this formula could be solved..........i think btw does this formula have possible problems at the equator? – Fuseteam Aug 24 '16 at 17:41
  • @Fuseteam: No, there is no problem at the equator, as the values just goes from positive to negative. There would however be problems if you are very close to a pole, as it would consider the closest distance to be a curve around the pole rather than a line across the pole. (This applies everywhere to a small extent, but anywhere on land (except Antarctica) the difference is small enough.) – Guffa Aug 27 '16 at 13:03
  • But then what causes the problems at the international dateline? – Fuseteam Aug 27 '16 at 17:14
  • @Fuseteam: It's when the longitude jumps between +180 and -180. – Guffa Aug 28 '16 at 01:34
  • so it only when jumps between 180 and -180 but not between positive and negative overall i see and since it anywhere on land the difference is small enough the poles limitation doesn't need solving, i see. – Fuseteam Aug 28 '16 at 03:41
7

If you want proper spatial data in your model then use SpatiaLite, a spatially-enabled version of SQLite:

http://www.gaia-gis.it/spatialite/

Its like PostGIS is for PostgreSQL. All your SQLite functionality will work perfectly and unchanged, and you'll get spatial functions too.

Spacedman
  • 92,590
  • 12
  • 140
  • 224
  • Thanks, this is interesting, but I'm not sure I want to change over my database connectors at this time. Upvote for the cool link though! – Ben Holland Jul 01 '11 at 15:35
  • But this is the proper way to do it. You should bite the bullet now and move on to something really spatial - it will be worth the pain down the road – TheSteve0 Jul 20 '11 at 11:51
1

You could always truncate the Taylor series expansion of sine and use the fact that sin^2(x)+cos^2(x)=1 to get the approximation of cosine. The only tricky part would be using Taylor's theorem to estimate the number of terms that you'd need for a given amount of precision.

0

Change "*" with "/" works for me:

select * from Points order by (lat - @lat) * (lat - @lat) + ((lng - @lng) / 2) * ((lng - @lng) / 2)

Andreoid
  • 11
  • 2