Find the nearest GPS point to the user's location from the list

Question

what I'm trying to do: the user selects the beginning and destination on the map, and then from my coordinates I want to show the nearest point location from the list of locations on the map. I have a simple Sqlite database containing the longitude, latitude, and name of possible locations.

I did some research, and here is what I found:

http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL

but it is intended to be used with mySql and some kind of spatial search extension. is there any way i can do something similar using android api or external libs?

public Point dialogFindClosestLocationToPoint(geometry.Point aStartPoint){ List<PointWithDistance> helperList=new ArrayList<PointWithDistance>(); try { openDataBase(); Cursor c=getCursorQueryWithAllTheData(); if(c.moveToFirst()) do{ PointWithDistance helper=new PointWithDistance(c.getDouble(1),c.getDouble(2),c.getString(3)); int distance=returnDistanceBetween2Points(aStartPoint, helper); if(distance<MAX_SEARCH_DISTANCE){ helper.setDistance(distance); Log.i("values", helper.name); helperList.add(helper); } }while (c.moveToNext()); Collections.sort(helperList,new PointComparator()); if(helperList!=null) return helperList.get(0); else return null; }catch(SQLException sqle){ throw sqle; } finally{ close(); } 

this is the code in the PointComparator () class:

  public int compare(PointWithDistance o1, PointWithDistance o2) { return (o1.getDistance()<o2.getDistance() ? -1 : (o1.getDistance()==o2.getDistance() ? 0 : 1)); } 

where PointWithDistance is an object that contains: lat, long, distance, name

however, this solution does not provide the correct information about the return ... and I understand that it does not scale at all and is very slow. I need a solution that will execute quickly with a database with a maximum of 1000 rows.

edit: I had an error in this code in the sort, now I changed it (should be <instead of>)

Answer 1

I was looking for something very similar a while back:

Android sqlite sort by computed column (distance between coordinates)

I used MySQL search on my server, MySQL allows you to create a virtual column, perform calculations and sort by distance, and then you can set maximum results or maximum distance - it works very well: / p>

 Select Lat, Lon, acos(sin($lat)*sin(radians(Lat)) + cos($lat)*cos(radians(Lat))cos(radians(Lon)-$lon))$R As dist From MyTable ORDER BY dist DESC 

I wanted to perform the same operation in my application - to pull out all the points in order to distance myself from the users location, which allowed me to show the closest ones. I ended up going with the solution along the lines suggested by the link above, but I understand that this is probably not the optimal solution, but it works for the purpose I wanted.

Answer 2

This kind of thing is done most efficiently using R-Tree . The JSI library provides a Java implementation that I have successfully used with an index of 80,000 places, processing thousands of requests per second. However, it may not work on Android.

Answer 3

I have not tried using your code, but it looks like it will work, it just is not efficient. for example, you do not need to sort, you need a cutout minimum.

you can limit your query to only a square of size (2 * MAX_SEARCH_DISTANCE) ^ 2 (with your point in the middle. This way you localize your query and it will give you fewer results for calculating the distance. Of course, this will not help if all your locations located on a localized area (perhaps unlikely?).

Also, I suppose you could use the Hamiltonian distance instead of the Euclidean. Euclidean distance = sqrt ((lat0 - lat1) ^ 2 + (lon0 - lon1) ^ 2) hamitonian distance = (lat0 - lat1) + (lon0 - lon1)