find nearest Gps point to the user location form a list

Question

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

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 2

I was looking for something very similar some time ago:

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.