Ordering with SQLITE by nearest latitude & longitude coordinates

Question

I must obtain a SQLite SQL Sentence for ordering by nearest latitude and longitude coordinates, given a initial location.

THis is a example sentence for my table in the sqlite database:

SELECT id, name, lat, lng FROM items

EXAMPLE RESULT: 1, Museu, 41375310.0, 2175970.0

I must achieve this with SQLite, and with that table. I can't use another techniques because this is for a existen SQlite database that i can't change.

Exists a way to achieve this with Android and SQlite? I checked a lot of stackoverflow posts and i didn't find the way to achieve that

Thanks

Solution 1

SELECT * AS distance FROM items ORDER BY ABS(location_lat - lat) + ABS(location_lng - lng) ASC

This should roughly sort the items on distance in MySQL, and should work in SQLite.
If you need to sort them preciser, you could try using the Pythagorean theorem (a^2 + b^2 = c^2) to get the exact distance.

Solution 2

The answer from Darkwater is nearly correct. To be correct, you need to use the square of the differences. As the square function is not available on SqLite, you need to multiply the differences by themselves. No need to calculate the square roots.

SELECT * AS distance FROM items ORDER BY ((location_lat-lat)*(location_lat-lat)) + ((location_lng - lng)*(location_lng - lng)) ASC

Solution 3

The solution proposed by Chris:

SELECT * AS distance FROM items ORDER BY ((location_lat-lat)*(location_lat-lat)) + ((location_lng - lng)*(location_lng - lng)) ASC

is correct when we are close to the equator. For it to work correctly in other latitudes, I propose:

SELECT * AS distance FROM items ORDER BY ((location_lat-lat)*(location_lat-lat)) + ((location_lng - lng)*(location_lng - lng)*cos_lat_2) ASC

where we must precompute:

cos_lat_2 = cos(location_lat * PI / 180) ^ 2

THE PROBLEM:

If we are in the equator and we move one degree in longitude (east or west), we do so on a circumference of 40,000 km, representing a distance of 40.000 / 360. If we move one degree in latitude (north or south), we do so on a circle that crosses both poles, which also involves a distance of 40.000 / 360 (considering that the earth is a sphere).

But, if we are in the south of England, with a latitude of 50°, and we move one degree in longitude (east or west) we do it on the 50th parallel, which has a smaller circumference than the equator. The distance is perimeter_parallel_50 / 360. Calculating this perimeter is simple: perimeter_parallel_50 = cos (50) * 2 * PI * EARHT_RADIUS = 0.64 * 40,000 km. This reduction in distance is not seen if we move one degree south or north. The circumference by which we move still has a perimeter of 40,000 Km.

SOLUTION:

Since location_lat is a value known beforehand, we can pre-calculate the value of cos(location_lat) so that it can be used as a scaling factor so the displacements in longitude and latitude are equivalent. Moreover, we pre square it to avoid having to multiply it twice.

NOTE:

This is still an approximation, and it will give wrong results when moving big distances, especially near the poles and when crossing the 180th meridian.

Solution 4

If you know, that 1 degree of latitude is about 111111 meters and 1 degree of longitude is 111111*cos(latitude) meters, then you can easily get all places inside a specific square.

SELECT * FROM items WHERE latitude BETWEEN %f AND %f AND longitude BETWEEN %f AND %f

This query is very fast, even with millions of rows. But don't forget to create an index for latitude and longitude:

CREATE INDEX position ON items (latitude, longitude)

I use this in Objective-C to obtain all places of interest that are within 3km around the current location:

double latDist = 1.0 / 111111.0 * 3.0;
double lonDist = 1.0 / ABS(111111.0*cos(location.coordinate.latitude)) * 3.0;

FMResultSet *results = [database executeQueryWithFormat:@"SELECT * FROM items WHERE latitude BETWEEN %f AND %f AND longitude BETWEEN %f AND %f", location.coordinate.latitude - latDist, location.coordinate.latitude + latDist, location.coordinate.longitude - lonDist, location.coordinate.longitude + lonDist];

You can now calculate the exact distance and sort your results...

Solution 5

If you're able to load the records; convert them to Locations and then use the distanceTo function I'd recommend that but...

You can approximate the distance between two points using plain SQL and the various approaches are laid out clearly here. The further apart the points you are comparing become then your values can become increasingly incorrect if you use a simple calculation

If you're calculating these things yourself and your locations can be anywhere then you might need to be aware of values wrapping around if you're comparing locations around the international date line.

View more solutions

Comments

[NullPointerException]

Thanks but your SQL sentence doesn't works properly, and the pythagorean theorem can't be done with sqlite, no pow and no sqrt functions, and i dont know the way to add these functions on sqlite and android

[NullPointerException]

no, i can't fit this way, i must obtain the SQL sentence that gives me the ordered set of records. Also i can't use your second link way, because SQLITE doesn't have these functions avaiable

[Paul D'Ambra]

which maths functions aren't available in SQLite? Why are your constraints so tight?

[mstenroos]

This is a good quick filter, that seems to work, but your scale of multiplier is off by a factor of 1000. If your 3.0 is in km, then the multiplier should be 111.1.

[DanielFo]

yeah you are right, i forgot to mention that i am storing all my coordinates as integers and first multiplied them by 1000

[Entea]

nice answer from a person who studied math :) This should be the accepted answer

[Aleksey Kontsevich]

Simplest!!! Thanks!!! Getting exact distance is better however I think. Or there is no math functions in sqlite?

[Boris Verkhovskiy]

Don't you need to also have some logic to wrap around if you're close to the antimeridian?

[Boris Verkhovskiy]

I think you should add the logic to handle crossing the 180th meridian instead of making the reader do it :)

[user3403733]

Thank you this worked perfectly for me. Odd question but could you explain the Math behind it?