find nearest Gps point to the user location form a list

Question

hello to all.

what i am trying to do: the user selects start and destination on a map and then from their coordinates i want to show the closest point location from a list of locations on map. i have a simple Sqlite database containing the longitude,latitude and name of the possible locations.

i did some research and this is what i found:

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

but this is meant for using it with mySql and some kind of spatial search extension. is there a possibility 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 a object that contains: lat, long , distance, name

however this solution doesn't provide the right return info... and i realize that is it not scalable at all and very slow. i need a solution that will execute fast with a database with max of 1000 rows.

edit: my there was a mistake in this code in the sorting now i have it changed( should be < instead of >)

Answer 1

i haven't tried running your code, but it seems like it would work, it's just that it's not efficient. like you don't actually need to sort, you need the extract the minimum.

you can restrict your query to just the square that is of size (2*MAX_SEARCH_DISTANCE)^2 (with your point in the middle. This way you are localizing your query and that will return you less results to compute distance for. Of course this will not help if all your locations are in the localized square (maybe unlikely?).

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

Answer 2

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

Answer 3

I was looking for something very similar some time ago:

http://stackoverflow.com/questions/2034348/android-sqlite-sort-on-calculated-column-co-ordinates-distance

I was using a MySQL lookup on my server, MySQL allows you to create a virtual column, performs the calculation and sorts by distance, and then you can set the max results returned or the max distance - it works very well:

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 app - pull all the points in order to distance from the users location allowing me to show the closest ones. I ended up going with the a solution along the lines of the one suggested on the link above but realise its probably not the optimal solution but works for the purpose I wanted.