By Jure


2010-09-12 14:44:58 8 Comments

I have data with latitude and longitude stored in my SQLite database, and I want to get the nearest locations to the parameters I put in (ex. My current location - lat/lng, etc.).

I know that this is possible in MySQL, and I've done quite some research that SQLite needs a custom external function for the Haversine formula (calculating distance on a sphere), but I haven't found anything that is written in Java and works.

Also, if I want to add custom functions, I need the org.sqlite .jar (for org.sqlite.Function), and that adds unnecessary size to the app.

The other side of this is, I need the Order by function from SQL, because displaying the distance alone isn't that much of a problem - I already did it in my custom SimpleCursorAdapter, but I can't sort the data, because I don't have the distance column in my database. That would mean updating the database every time the location changes and that's a waste of battery and performance. So if someone has any idea on sorting the cursor with a column that's not in the database, I'd be grateful too!

I know there are tons of Android apps out there that use this function, but can someone please explain the magic.

By the way, I found this alternative: Query to get records based on Radius in SQLite?

It's suggesting to make 4 new columns for cos and sin values of lat and lng, but is there any other, not so redundant way?

7 comments

@Bobs 2012-10-21 12:42:50

1) At first filter your SQLite data with a good approximation and decrease amount of data that you need to evaluate in your java code. Use the following procedure for this purpose:

To have a deterministic threshold and more accurate filter on data, It is better to calculate 4 locations that are in radius meter of the north, west, east and south of your central point in your java code and then check easily by less than and more than SQL operators (>, <) to determine if your points in database are in that rectangle or not.

The method calculateDerivedPosition(...) calculates those points for you (p1, p2, p3, p4 in picture).

enter image description here

/**
* Calculates the end-point from a given source at a given range (meters)
* and bearing (degrees). This methods uses simple geometry equations to
* calculate the end-point.
* 
* @param point
*           Point of origin
* @param range
*           Range in meters
* @param bearing
*           Bearing in degrees
* @return End-point from the source given the desired range and bearing.
*/
public static PointF calculateDerivedPosition(PointF point,
            double range, double bearing)
    {
        double EarthRadius = 6371000; // m

        double latA = Math.toRadians(point.x);
        double lonA = Math.toRadians(point.y);
        double angularDistance = range / EarthRadius;
        double trueCourse = Math.toRadians(bearing);

        double lat = Math.asin(
                Math.sin(latA) * Math.cos(angularDistance) +
                        Math.cos(latA) * Math.sin(angularDistance)
                        * Math.cos(trueCourse));

        double dlon = Math.atan2(
                Math.sin(trueCourse) * Math.sin(angularDistance)
                        * Math.cos(latA),
                Math.cos(angularDistance) - Math.sin(latA) * Math.sin(lat));

        double lon = ((lonA + dlon + Math.PI) % (Math.PI * 2)) - Math.PI;

        lat = Math.toDegrees(lat);
        lon = Math.toDegrees(lon);

        PointF newPoint = new PointF((float) lat, (float) lon);

        return newPoint;

    }

And now create your query:

PointF center = new PointF(x, y);
final double mult = 1; // mult = 1.1; is more reliable
PointF p1 = calculateDerivedPosition(center, mult * radius, 0);
PointF p2 = calculateDerivedPosition(center, mult * radius, 90);
PointF p3 = calculateDerivedPosition(center, mult * radius, 180);
PointF p4 = calculateDerivedPosition(center, mult * radius, 270);

strWhere =  " WHERE "
        + COL_X + " > " + String.valueOf(p3.x) + " AND "
        + COL_X + " < " + String.valueOf(p1.x) + " AND "
        + COL_Y + " < " + String.valueOf(p2.y) + " AND "
        + COL_Y + " > " + String.valueOf(p4.y);

COL_X is the name of the column in the database that stores latitude values and COL_Y is for longitude.

So you have some data that are near your central point with a good approximation.

2) Now you can loop on these filtered data and determine if they are really near your point (in the circle) or not using the following methods:

public static boolean pointIsInCircle(PointF pointForCheck, PointF center,
            double radius) {
        if (getDistanceBetweenTwoPoints(pointForCheck, center) <= radius)
            return true;
        else
            return false;
    }

public static double getDistanceBetweenTwoPoints(PointF p1, PointF p2) {
        double R = 6371000; // m
        double dLat = Math.toRadians(p2.x - p1.x);
        double dLon = Math.toRadians(p2.y - p1.y);
        double lat1 = Math.toRadians(p1.x);
        double lat2 = Math.toRadians(p2.x);

        double a = Math.sin(dLat / 2) * Math.sin(dLat / 2) + Math.sin(dLon / 2)
                * Math.sin(dLon / 2) * Math.cos(lat1) * Math.cos(lat2);
        double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
        double d = R * c;

        return d;
    }

Enjoy!

I used and customized this reference and completed it.

@barneymc 2014-09-21 17:20:04

Check out Chris Veness great webpage if you are looking for a Javascript implementation of this concept above. movable-type.co.uk/scripts/latlong.html

@Y.S. 2015-06-04 13:58:18

Please tell me what exactly is COL_X and COL_Y in the WHERE clause. Are those the columns for latitude and longitude ?

@Y.S. 2015-06-05 04:43:43

Never mind, I figured it out myself. Many thanks for this wonderful shortcut ... +1.

@Bobs 2015-06-05 05:50:15

@Y.S. Col_X and Col_Y are the name of latitude and longitude columns in database.

@Menma 2015-09-09 08:39:04

@breceivemail Please tell me what is value x and y from PointF center = new PointF(x, y); and what is radius value? thank you

@Bobs 2015-09-09 09:19:24

@Menma x is latitude and y is longitude. radius: the radius of the circle that is shown in the picture.

@Jas 2015-11-03 07:07:13

@Y.S. how did you solve the issue?

@Y.S. 2015-11-03 08:31:10

the solution given above is correct and works. Try it ... :)

@Jas 2015-11-05 05:31:39

This is not working for me :( @Y.S.

@Y.S. 2015-11-05 05:32:37

Sorry, man. The answer is correct, and it works perfectly fine for me.

@Magnus W 2016-05-26 16:40:22

Works perfectly for me! However, there is also the android.location.Location. distanceBetween() method, which basically does the same as the last function in this answer, so no use reinventing it.

@jublikon 2016-08-29 16:08:47

@breceivemail : why do you use PointF containing float values instead of an object containing double values?

@efkan 2016-09-23 07:25:46

It doesn't work for me. Center is not the center. P1 is too close to the center and P3 is too far. Maybe the problem is the current position. I'm close to Mediterranean sea. If I did correct everything (i did copy-paste) If so the solution doesn't work for every one in the world. Unfortunately.

@user1447316 2016-11-20 15:52:11

This is NOT WORKING! I've put as center point 0,0 and it fives me the following results, with radius set to 30000: 0.269796481776,-8.11266146075 1.65202088404E-17,-8.11266146075 -0.269796481776,-8.11266146075 -4.95606265212E-17,-8.11266146075 I get always the same LONGITUDE! How is this possible! The point 1 and 3 are super correct..the points 2 and 4 are on the same vertical line as the other too!! They should spread!

@user1643723 2018-03-28 09:46:50

This is an approximate solution! It gives you highly approximate results via a fast, index-friendly SQL query. It will give wrong result in some extreme circumstances. Once you have gotten small number of approximate result within area of several kilometers, use slower, more precise methods to filter those results. Do not use it to filter with very large radius or if your app is going to be frequently used at equator!

@Amitabh Sarkar 2018-06-04 10:30:22

Worked for me, Thanks a lot.

@Chris Simpson 2011-08-31 18:25:37

I know this has been answered and accepted but thought I'd add my experiences and solution.

Whilst I was happy to do a haversine function on the device to calculate the accurate distance between the user's current position and any particular target location there was a need to sort and limit the query results in order of distance.

The less than satisfactory solution is to return the lot and sort and filter after the fact but this would result in a second cursor and many unnecessary results being returned and discarded.

My preferred solution was to pass in a sort order of the squared delta values of the long and lats:

((<lat> - LAT_COLUMN) * (<lat> - LAT_COLUMN) +
 (<lng> - LNG_COLUMN) * (<lng> - LNG_COLUMN))

There's no need to do the full haversine just for a sort order and there's no need to square root the results therefore SQLite can handle the calculation.

EDIT:

This answer is still receiving love. It works fine in most cases but if you need a little more accuracy, please check out the answer by @Teasel below which adds a "fudge" factor that fixes inaccuracies that increase as the latitude approaches 90.

@iMatoria 2011-10-16 15:47:51

Great answer. Could you explain how did it work and what is this algorithm called?

@Chris Simpson 2011-10-17 03:51:47

@iMatoria - This is just a cut down version of pythagoras famous theorem. Given two sets of coordinates, the difference between the two X values represents one side of a right angled triangle and the difference between the Y values is the other. To get the hypotenuse (and therefore the distance between the points) you add the squares of these two values together and then square root the result. In our case we don't do the last bit (the square rooting) because we can't. Fortunately this is not necessary for a sort order.

@noisecapella 2012-09-17 00:38:57

In my app BostonBusMap I used this solution to show stops closest to the current location. However you need to scale the longitude distance by cos(latitude) to have the latitude and longitude roughly equal. See en.wikipedia.org/wiki/…

@Sergey Metlov 2015-05-12 11:37:03

In order to increase performance as much as possible I suggest improve @Chris Simpson's idea with the following ORDER BY clause:

ORDER BY (<L> - <A> * LAT_COL - <B> * LON_COL + LAT_LON_SQ_SUM)

In this case you should pass the following values from code:

<L> = center_lat^2 + center_lon^2
<A> = 2 * center_lat
<B> = 2 * center_lon

And you should also store LAT_LON_SQ_SUM = LAT_COL^2 + LON_COL^2 as additional column in database. Populate it inserting your entities into database. This slightly improves performance while extracting large amount of data.

@Scott Helme 2013-06-13 13:03:34

Try something like this:

    //locations to calculate difference with 
    Location me   = new Location(""); 
    Location dest = new Location(""); 

    //set lat and long of comparison obj 
    me.setLatitude(_mLat); 
    me.setLongitude(_mLong); 

    //init to circumference of the Earth 
    float smallest = 40008000.0f; //m 

    //var to hold id of db element we want 
    Integer id = 0; 

    //step through results 
    while(_myCursor.moveToNext()){ 

        //set lat and long of destination obj 
        dest.setLatitude(_myCursor.getFloat(_myCursor.getColumnIndexOrThrow(DataBaseHelper._FIELD_LATITUDE))); 
        dest.setLongitude(_myCursor.getFloat(_myCursor.getColumnIndexOrThrow(DataBaseHelper._FIELD_LONGITUDE))); 

        //grab distance between me and the destination 
        float dist = me.distanceTo(dest); 

        //if this is the smallest dist so far 
        if(dist < smallest){ 
            //store it 
            smallest = dist; 

            //grab it's id 
            id = _myCursor.getInt(_myCursor.getColumnIndexOrThrow(DataBaseHelper._FIELD_ID)); 
        } 
    } 

After this, id contains the item you want from the database so you can fetch it:

    //now we have traversed all the data, fetch the id of the closest event to us 
    _myCursor = _myDBHelper.fetchID(id); 
    _myCursor.moveToFirst(); 

    //get lat and long of nearest location to user, used to push out to map view 
    _mLatNearest  = _myCursor.getFloat(_myCursor.getColumnIndexOrThrow(DataBaseHelper._FIELD_LATITUDE)); 
    _mLongNearest = _myCursor.getFloat(_myCursor.getColumnIndexOrThrow(DataBaseHelper._FIELD_LONGITUDE)); 

Hope that helps!

@NickG 2013-01-16 18:20:06

Have a look at this post:

Distance function for sqlite

It seems to allow you to add a custom Distance() function to SQLite which might allow you to avoid jumping through all the hoops in the other answers.

@Chris.Jenkins 2013-08-21 18:51:40

This is possible, but you need to write an NDK plugin to call to the database. To add the function. looks cool tho.

@Teasel 2011-09-19 14:06:36

Chris's answer is really useful (thanks!), but will only work if you are using rectilinear coordinates (eg UTM or OS grid references). If using degrees for lat/lng (eg WGS84) then the above only works at the equator. At other latitudes, you need to decrease the impact of longitude on the sort order. (Imagine you're close to the north pole... a degree of latitude is still the same as it is anywhere, but a degree of longitude may only be a few feet. This will mean that the sort order is incorrect).

If you are not at the equator, pre-calculate the fudge-factor, based on your current latitude:

<fudge> = Math.pow(Math.cos(Math.toRadians(<lat>)),2);

Then order by:

((<lat> - LAT_COLUMN) * (<lat> - LAT_COLUMN) + (<lng> - LNG_COLUMN) * (<lng> - LNG_COLUMN) * <fudge>)

It's still only an approximation, but much better than the first one, so sort order inaccuracies will be much rarer.

@Chris Simpson 2011-10-17 03:59:14

That's a really interesting point about the longitudal lines converging at the poles and skewing the results the nearer you get. Nice fix.

@max4ever 2012-08-31 11:08:07

this seems to work cursor = db.getReadableDatabase().rawQuery("Select nome, id as _id, " + "( " + latitude + " - lat) * ( " + latitude +"- lat) + ( " + longitude + "- lon) * ( " + longitude + "- lon) * " + fudge + " as distanza " + " from cliente "+ " order by distanza asc", null);

@Bobs 2012-10-21 07:32:09

should ((<lat> - LAT_COLUMN) * (<lat> - LAT_COLUMN) + (<lng> - LNG_COLUMN) * (<lng> - LNG_COLUMN) * <fudge>) be less than distance or distance^2?

@Rangel Reale 2012-12-11 18:46:21

Isn't the fudge factor in radians and the columns in degrees? Shouldn't them be converted to the same unit?

@Teasel 2013-01-16 18:24:54

No, the fudge factor is a scaling factor which is 0 at the poles and 1 at the equator. It's neither in degrees, nor radians, it's just a unitless number. The Java Math.cos function requires an argument in radians, and I assumed <lat> was in degrees, hence the Math.toRadians function. But the resulting cosine has no units.

@Gavin 2015-04-05 07:36:30

Cool, this should be the accepted answer

@AdamMc331 2016-02-24 22:03:38

What unit of distance does this return?

@Teasel 2016-02-25 12:07:39

This is just an 'order by' clause for the SQL... it makes sure that the closest records are at the top, but doesn't calculate distances. So, once you've got the result set, you should then calculate the distances in your code, using the Haversine formula. Eg you could use breceivemail's getDistanceBetweenTwoPoints function, posted above. That function hardcodes an Earth radius of 6371000, so the distances it returns will be in m. If you want your results in different units, simply change that number (eg use 31670 for distances in furlongs).

@jublikon 2016-08-26 14:26:51

I have added that piece of code to my order by clause and I get a SQL syntax error. The SQL statement is working without the order clause. Where do I have made a mistake? SELECT * FROM locations WHERE latitude > 51.193966 AND latitude < 51.194324 AND longitude < 6.4470406 AND longitude > 6.4464664 ORDER BY ((51.19414666666667 - latitude) * (51.19414666666667 - latitude + (6.446753333333334 - longitude) * (6.446753333333334 - longitude) * 0.39273211543715586)

@Moulesh 2017-10-11 11:57:07

great answer :-)

@Carlos Alberto Martínez Gadea 2018-08-08 15:29:59

Simply brilliant, and definitely thanks to @ChrisSimpson answer for it's original answer.

@Morrison Chang 2010-09-12 18:40:11

Have you considered a Geohash tag/index for your entries to reduce the size of your result set and then apply the appropriate function.

Another stackoverflow question in a similar area: finding-the-closest-point-to-a-given-point

@Jure 2010-09-13 10:30:11

Thanks, your post led me to this: code.google.com/p/javageomodel/source/browse/trunk/geocell/t‌​est/… But i can't quite figure out how i can query it in the sqlite database. As I said, I need a quite accurate distance from the given location to the locations in the database and the nearest locations ordered by distance. I can calculate the distance with Locations distanceTo() method, but that's outside of the DB and therefore slower.

@Morrison Chang 2010-09-13 16:43:34

You never mentioned how many data points you are working with, or the use case for that matter. If you really need a list of all of n points in accurate distance order you may want to consider a server side option or if possible just hold your data in memory and apply distance calc for each. For mobile you are on a 'limited' resource machine where a typical use case is search for nearby things, i.e. use a geohash to reduce the result set, and then sort out the stuff in the result set to display to the user. For the geocell/geohash use the hexstring as your index for each POI.

@Jure 2010-09-13 20:14:31

I have about 400 data points. Server side querying isn't really an option, because I want the app to be usable even if it's not online (Mobile network internet isn't free and I don't think users would be glad to have to be online everytime they would want to use the app). As I mentioned, I'm using a content provider to access the DB and it would be redundant to have another "provider" that's different from the DB content provider.

@Morrison Chang 2010-09-13 21:42:56

Most smartphone users will have data connection, but I get the concern. 400 points isn't that large unless you need to get the distance from the current position for each. Back to your original question, I think the 'magic' is that most apps don't need all 400 points so they use a geohash/geocell to get only the closest points (say 1 km) and then sort and display the results. If you need all 400 points in order, I think you'll need to either create a custom cursor for your content provider which returns POI in order or have other code sort it once the cursor is available.

@Morrison Chang 2010-09-13 21:43:37

I had also mentioned putting all POI in a cache (a service maybe?) as another option to avoid the db overhead or to get the performance you require.

@Jure 2010-09-14 07:29:27

Thanks, as you suggested I will probably use geocell to get the closest points in the user defined filter (1km, 5km, ...) and then only calculate the distances to those points (maybe 20 or 30 POI). I'll probably need a custom cursor anyway for the sorting after I get data from the DB.

Related Questions

Sponsored Content

21 Answered Questions

[SOLVED] How do I get the current GPS location programmatically in Android?

17 Answered Questions

9 Answered Questions

[SOLVED] Improve INSERT-per-second performance of SQLite?

25 Answered Questions

1 Answered Questions

1 Answered Questions

Get latitude and longitude of user in PHP or JavaScript for use in PHP

4 Answered Questions

[SOLVED] How to get 10 nearest locations from the current location

  • 2010-10-11 12:44:19
  • praveenb
  • 2776 View
  • 1 Score
  • 4 Answer
  • Tags:   android

4 Answered Questions

[SOLVED] Android sqlite sort on calculated column (co-ordinates distance)

2 Answered Questions

[SOLVED] IPhone - SQLite distance by Latitude and Longitude

Sponsored Content