Finden Sie den nächsten GPS-Punkt zum Benutzer Standort aus einer Liste

Question

was ich versuche zu tun: der Benutzer wählt Start und Ziel auf einer Karte und dann von ihren Koordinaten ich möchte den nächstgelegenen Ort aus einer Liste von Standorten auf der Karte zeigen . Ich habe eine einfache Sqlite-Datenbank, die den Längen-, Breiten- und Namen der möglichen Standorte enthält.

habe ich einige der Forschung, und das ist, was ich gefunden:

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

aber dies ist für die Verwendung mit MySQL und eine Art räumliche Such Verlängerung bedeutete. gibt es eine möglichkeit, dass ich etwas ähnliches mit android api oder externen libs tun kann?

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(); 
} 

ist dies der Code in der PointComparator() Klasse:

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

wo PointWithDistance ein Objekt ist, das enthält: lat, long, Entfernung, name

jedoch diese Lösung nicht der Fall ist biete die richtige return info ... und ich stelle fest, dass es überhaupt nicht skalierbar und sehr langsam ist. Ich brauche eine Lösung, die schnell mit einer Datenbank mit maximal 1000 Zeilen ausgeführt wird.

edit: meine es war ein Fehler in diesem Code in der Sortier jetzt habe ich es geändert (sollte < statt>)

Answer 1

ich vor etwas sehr ähnlich einige Zeit auf der Suche:

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

ich eine MySQL-Lookup auf meinem Server wurde mit MySQL können Sie eine virtuelle Spalte erstellen, führt die Berechnung und sortiert nach Entfernung und dann können Sie die max Ergebnisse zurückgegeben oder die maximale Entfernung eingestellt - es funktioniert sehr gut:

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 

ich die gleiche Operation in meiner app ausführen wollte - ziehen alle Punkte, um Abstand von den Benutzern locati damit ich die nächsten zeigen kann.Ich entschied mich für eine Lösung, die der oben auf dem obigen Link vorgeschlagenen Lösung entsprach, erkannte aber, dass sie wahrscheinlich nicht die optimale Lösung ist, aber für den von mir gewünschten Zweck funktioniert.

Answer 2

i Code nicht versucht haben, laufen, aber es scheint, wie es funktionieren würde Es ist nur, dass es nicht effizient ist. Wie Sie eigentlich nicht sortieren müssen, brauchen Sie den Extrakt das Minimum.

Sie können Ihre Abfrage auf nur das Quadrat der Größe (2 * MAX_SEARCH_DISTANCE)^2 beschränken (mit Ihrem Punkt in der Mitte. Auf diese Weise lokalisieren Sie Ihre Abfrage und das bringt Ihnen weniger Ergebnisse zur Berechnung der Entfernung . (? vielleicht unwahrscheinlich). für natürlich wird dies nicht helfen, wenn alle Standorte in der lokalisierten Platz sind

auch, nehme ich Sie hamiltonsch Entfernung statt euklidischen euklidischen Abstand = sqrt ((LAT0 nutzen könnten. - lat1)^2 + (lon0 - lon1)^2) hamitonischer Abstand = (lat0 - lat1) + (lon0 - lon1)

Answer 3

Thi s Sache ist am effizientesten mit einem R-Tree getan. Die JSI library bietet eine Java-Implementierung, die ich erfolgreich mit einem Index von 80.000 Standorten verwendet habe, die Tausende von Suchvorgängen pro Sekunde verarbeitet. Es kann jedoch nicht auf Android ausgeführt werden.