Query to get records based on Radius in SQLite?

Question

I have this query which does work fine in MySQL

SELECT ((ACOS(SIN(12.345 * PI() / 180) * SIN(lat * PI() / 180) +
         COS(12.345 * PI() / 180) * COS(lat * PI() / 180) * COS((67.89 - lon) * 
         PI() / 180)) * 180 / PI()) * 60 * 1.1515 * 1.609344) AS distance, poi.* 
FROM poi
WHERE lang='eng' 
HAVING distance<='30'

distance is in Kilometers, the input is lat=12.345 and lon=67.89

The SQLite is 3, and I can't run custom functions with it as it's on Android. I also don't have acos() etc... as that is not part of the standard SQLite.

How would be the above query in SQLite?

You have two choices, calculate outside the database or project your coordinates on an ellipsoid that will get you meters and allow you to use the regular distance formula as an approximation. — Vinko Vrsalovic, Jun 27 '10 at 08:42
I am open to this solution, can you please detail it in an answer. — Pentium10, Jun 27 '10 at 08:47
For beginners like me, the whole formula is called `Spherical Law of Cosines` and is described here: http://www.movable-type.co.uk/scripts/latlong.html — Afriza N. Arief, Jan 06 '11 at 15:17
look at this answer http://stackoverflow.com/a/12997900/779408 — Bob, Oct 22 '12 at 12:16

score 31 · Answer 1 · answered Mar 02 '12 at 16:35

Here is an implementation in Java for building a location based query on an Android device. The idea comes from KennyTM (see accepted response) and implies the addition of 4 columns in your table to store values of sinus and cosinus of latitude and longitudes.

Here is the code preparing the data for a "Shop" table at insert time:

public static void injectLocationValues(ContentValues values, double latitude, double longitude) {
    values.put(LocationColumns.LATITUDE, latitude);
    values.put(LocationColumns.LONGITUDE, longitude);
    values.put(LocationColumns.COSLAT, Math.cos(MathUtil.deg2rad(latitude)));
    values.put(LocationColumns.SINLAT, Math.sin(MathUtil.deg2rad(latitude)));
    values.put(LocationColumns.COSLNG, Math.cos(MathUtil.deg2rad(longitude)));
    values.put(LocationColumns.SINLNG, Math.sin(MathUtil.deg2rad(longitude)));
}

public static double deg2rad(double deg) {
    return (deg * Math.PI / 180.0);
}

You can then build your projection using the following function:

/**
 * Build query based on distance using spherical law of cosinus
 * 
 * d = acos(sin(lat1).sin(lat2)+cos(lat1).cos(lat2).cos(long2−long1)).R
 * where R=6371 and latitudes and longitudes expressed in radians
 * 
 * In Sqlite we do not have access to acos() sin() and lat() functions.
 * Knowing that cos(A-B) = cos(A).cos(B) + sin(A).sin(B)
 * We can determine a distance stub as:
 * d = sin(lat1).sin(lat2)+cos(lat1).cos(lat2).(cos(long2).cos(long1)+sin(long2).sin(long1))
 * 
 * First comparison point being fixed, sin(lat1) cos(lat1) sin(long1) and cos(long1)
 * can be replaced by constants.
 * 
 * Location aware table must therefore have the following columns to build the equation:
 * sinlat => sin(radians(lat))
 * coslat => cos(radians(lat))
 * coslng => cos(radians(lng))
 * sinlng => sin(radians(lng))
 *  
 * Function will return a real between -1 and 1 which can be used to order the query.
 * Distance in km is after expressed from R.acos(result) 
 *  
 * @param latitude, latitude of search
 * @param longitude, longitude of search
 * @return selection query to compute the distance
 */
public static String buildDistanceQuery(double latitude, double longitude) {
    final double coslat = Math.cos(MathUtil.deg2rad(latitude));
    final double sinlat = Math.sin(MathUtil.deg2rad(latitude));
    final double coslng = Math.cos(MathUtil.deg2rad(longitude));
    final double sinlng = Math.sin(MathUtil.deg2rad(longitude));
    //@formatter:off
    return "(" + coslat + "*" + LocationColumns.COSLAT
            + "*(" + LocationColumns.COSLNG + "*" + coslng
            + "+" + LocationColumns.SINLNG + "*" + sinlng
            + ")+" + sinlat + "*" + LocationColumns.SINLAT 
            + ")";
    //@formatter:on
}

It will inject a response column with the distance on which you need to apply the following formula to convert in kilometers:

public static double convertPartialDistanceToKm(double result) {
    return Math.acos(result) * 6371;
}

If you want to order your query using the partial distance, you need to order DESC and not ASC.

Note, that this approach reads all locations from disk and does the calculation for each (even if you limit the radius!). It is also incompatible with indexes (always performs full table scan). A query can be greatly accelerated by limiting the bounds, using method, decribed in [this question](http://stackoverflow.com/q/3695224/1643723) first and filtering/ordering results with subquery, using the method above. And you can use index with that first query unlike this one! — user1643723, Nov 30 '15 at 09:59

sclaeys · Answer 2 · 2014-11-16T20:40:02.423

Had the same issue while working on sqlite3 for ios, after playing a little with the formula here is a way to do it without using function from the sql side (pseudo-code):

Pre-calculate these value for each item you store in the database (and store them):

cos_lat = cos(lat * PI / 180)
sin_lat = sin(lat * PI / 180)
cos_lng = cos(lng * PI / 180)
sin_lng = sin(lng * PI / 180)

Pre-calculate these value at the search time (for a given position cur_lat,cur_lng)

CUR_cos_lat = cos(cur_lat * PI / 180)
CUR_sin_lat = sin(cur_lat * PI / 180)
CUR_cos_lng = cos(cur_lng * PI / 180)
CUR_sin_lng = sin(cur_lng * PI / 180)
cos_allowed_distance = cos(2.0 / 6371) # This is 2km

Your SQL query will look like this (replace CUR_* by the values you just calculated)

SELECT * FROM position WHERE CUR_sin_lat * sin_lat + CUR_cos_lat * cos_lat * (cos_lng* CUR_cos_lng + sin_lng * CUR_sin_lng) > cos_allowed_distance;

I like this approach but is the equation correct? Most of equations I've seen have acos(). Yours doesn't. Am I missing something? — Sam, Jun 16 '15 at 07:18
I guess, that instead of ``acos(left part) compare to 2`` they use ``left part compare to cos(2)`` which should be equivalent. — Slawa, Jan 10 '16 at 10:53

score 15 · Accepted Answer · edited May 23 '17 at 12:09

15

You can create 4 new columns, being sin and cos of lat and lon. Since cos(a+b) = cos a cos b - sin a sin b, and other appearances of sin and cos like SIN(12.345 * PI() / 180) can be calculated in the program before running the query, the big "distance" expression reduces to something of the form P * SIN_LAT + Q * COS_LAT + ... that can be handled by SQLite3.

BTW, see also Sqlite on Android: How to create a sqlite dist db function - to be used in the app for distance calculation using lat, long.

edited May 23 '17 at 12:09

Community

1
1

answered Jun 27 '10 at 09:02

kennytm

510,854
105
1,084
1,005

Actually, I'm rather skeptical on the approach outlined in the content provider answer you link to. `org.sqlite` is not in Android, and it is unclear if there exists an `org.sqlite` implementation that will work in concert with Android's SQLite environment. – Pentium10 Jun 27 '10 at 09:13
Your method to have some columns added sounds doable. – Pentium10 Jun 27 '10 at 09:13
So how do you handle `ACOS()`? creating custom SQL function using `sqlite3_create_function()`? How do you do it in Android? – Afriza N. Arief Jan 06 '11 at 15:20
You need to maintain a hardcoded set of values on insert. You would insert along with the values in a new column the acos() value computed in Java. – Pentium10 Jan 07 '11 at 07:08

Query to get records based on Radius in SQLite?

3 Answers3

Linked

Related