SQlite Ermitteln der nächstgelegenen Standorte (mit Längen- und Breitengrad)

86

Ich habe Daten mit Längen- und Breitengrad in meiner SQLite-Datenbank gespeichert und möchte die nächstgelegenen Speicherorte zu den von mir eingegebenen Parametern ermitteln (z. B. meinen aktuellen Standort - lat / lng usw.).

Ich weiß, dass dies in MySQL möglich ist, und ich habe einige Untersuchungen durchgeführt, wonach SQLite eine benutzerdefinierte externe Funktion für die Haversine-Formel (Berechnung der Entfernung auf einer Kugel) benötigt, aber ich habe nichts gefunden, was in Java geschrieben ist und funktioniert .

Wenn ich benutzerdefinierte Funktionen hinzufügen möchte, benötige ich außerdem die org.sqlite.jar (für org.sqlite.Function), wodurch die App unnötig vergrößert wird.

Die andere Seite davon ist, dass ich die Funktion "Sortieren nach" aus SQL benötige, da das Anzeigen der Entfernung allein kein so großes Problem darstellt - ich habe es bereits in meinem benutzerdefinierten SimpleCursorAdapter getan, aber ich kann die Daten nicht sortieren, weil ich Ich habe die Entfernungsspalte nicht in meiner Datenbank. Das würde bedeuten, die Datenbank jedes Mal zu aktualisieren, wenn sich der Standort ändert, und das ist eine Verschwendung von Batterie und Leistung. Wenn also jemand eine Idee hat, den Cursor nach einer Spalte zu sortieren, die nicht in der Datenbank enthalten ist, wäre ich auch dankbar!

Ich weiß, dass es Unmengen von Android-Apps gibt, die diese Funktion verwenden, aber kann jemand bitte die Magie erklären.

Übrigens habe ich diese Alternative gefunden: Abfrage zum Abrufen von Datensätzen basierend auf Radius in SQLite?

Es wird vorgeschlagen, 4 neue Spalten für die cos- und sin-Werte von lat und lng zu erstellen. Gibt es jedoch einen anderen, nicht so redundanten Weg?

Jure
quelle
Haben Sie überprüft, ob org.sqlite.Function für Sie funktioniert (auch wenn die Formel nicht korrekt ist)?
Thomas Mueller
Nein, ich habe eine (redundante) Alternative (bearbeiteter Beitrag) gefunden, die besser klingt als das Hinzufügen einer 2,6-MB-JAR-Datei in der App. Aber ich suche immer noch nach einer besseren Lösung. Vielen Dank!
Jure
Was ist der Typ der Rücklaufentfernungseinheit?
Hier finden Sie eine vollständige Implementierung zum Erstellen einer SQlite-Abfrage unter Android basierend auf der Entfernung zwischen Ihrem Standort und dem Standort des Objekts.
EricLarch

Antworten:

110

1) Filtern Sie zuerst Ihre SQLite-Daten mit einer guten Annäherung und verringern Sie die Datenmenge, die Sie in Ihrem Java-Code auswerten müssen. Verwenden Sie zu diesem Zweck das folgende Verfahren:

Um einen deterministischen Schwellenwert und einen genaueren Filter für Daten zu erhalten, ist es besser, 4 Positionen in radiusMetern des Nordens, Westens, Ostens und Südens Ihres Mittelpunkts in Ihrem Java-Code zu berechnen und dann einfach um weniger als und mehr als zu überprüfen SQL-Operatoren (>, <), um festzustellen, ob sich Ihre Punkte in der Datenbank in diesem Rechteck befinden oder nicht.

Die Methode calculateDerivedPosition(...)berechnet diese Punkte für Sie (p1, p2, p3, p4 im Bild).

Geben Sie hier die Bildbeschreibung ein

/**
* 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;

    }

Und jetzt erstellen Sie Ihre Abfrage:

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_Xist der Name der Spalte in der Datenbank, in der Breitengradwerte und COL_YLängengrade gespeichert sind .

Sie haben also einige Daten, die sich mit einer guten Annäherung in der Nähe Ihres Mittelpunkts befinden.

2) Jetzt können Sie diese gefilterten Daten in einer Schleife bearbeiten und mithilfe der folgenden Methoden feststellen, ob sie sich wirklich in der Nähe Ihres Punkts (im Kreis) befinden oder nicht:

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

Genießen!

Ich habe diese Referenz verwendet, angepasst und vervollständigt.

Bobs
quelle
Schauen Sie sich die großartige Webseite von Chris Veness an, wenn Sie nach einer Javascript-Implementierung dieses Konzepts suchen. movable-type.co.uk/scripts/latlong.html
barneymc
@Menma x ist Breitengrad und y ist Längengrad. Radius: Der Radius des Kreises, der im Bild angezeigt wird.
Bobs
Die oben angegebene Lösung ist korrekt und funktioniert. Probieren Sie es aus ... :)
YS
1
Dies ist eine ungefähre Lösung! Über eine schnelle , indexfreundliche SQL-Abfrage erhalten Sie sehr ungefähre Ergebnisse . Unter extremen Umständen führt dies zu einem falschen Ergebnis. Wenn Sie innerhalb eines Bereichs von mehreren Kilometern eine geringe Anzahl von ungefähren Ergebnissen erhalten haben, verwenden Sie langsamere und präzisere Methoden, um diese Ergebnisse zu filtern . Verwenden Sie es nicht zum Filtern mit sehr großem Radius oder wenn Ihre App am Äquator häufig verwendet wird!
user1643723
1
Aber ich verstehe es nicht. CalculateDerivedPosition wandelt die lat, lng-Koordinate in eine kartesische um, und dann vergleichen Sie in der SQL-Abfrage diese kartesischen Werte mit den lat, long-Werten. Zwei verschiedene geometrische Koordinaten? Wie funktioniert das? Vielen Dank.
Fehlentwicklung
70

Chris 'Antwort ist wirklich nützlich (danke!), Funktioniert aber nur, wenn Sie geradlinige Koordinaten verwenden (z. B. UTM- oder OS-Gitterreferenzen). Wenn Sie Grad für lat / lng verwenden (z. B. WGS84), funktioniert das Obige nur am Äquator. In anderen Breiten müssen Sie den Einfluss der Länge auf die Sortierreihenfolge verringern. (Stellen Sie sich vor, Sie befinden sich in der Nähe des Nordpols ... ein Breitengrad ist immer noch derselbe wie überall, aber ein Längengrad kann nur wenige Fuß betragen. Dies bedeutet, dass die Sortierreihenfolge falsch ist.)

Wenn Sie nicht am Äquator sind, berechnen Sie den Fudge-Faktor anhand Ihres aktuellen Breitengrads vor:

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

Dann bestellen Sie bei:

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

Es ist immer noch nur eine Annäherung, aber viel besser als die erste, so dass Ungenauigkeiten in der Sortierreihenfolge viel seltener sind.

Karde
quelle
3
Das ist ein wirklich interessanter Punkt, wenn die Längslinien an den Polen zusammenlaufen und die Ergebnisse verzerren, je näher Sie kommen. Schöne Lösung.
Chris Simpson
1
Dies scheint zu funktionieren. cursor = db.getReadableDatabase (). rawQuery ("Nome, ID als _id auswählen" + "(" + Breitengrad + "- Lat) * (" + Breitengrad + "- Lat) + (" + Längengrad + "- lon) * (" + longitude + "- lon) *" + fudge + "als distanza" + "from cliente" + "order by distanza asc", null);
Max4ever
sollte ((<lat> - LAT_COLUMN) * (<lat> - LAT_COLUMN) + (<lng> - LNG_COLUMN) * (<lng> - LNG_COLUMN) * <fudge>)kleiner sein als distanceoder distance^2?
Bobs
Ist der Fudge-Faktor nicht im Bogenmaß und die Spalten in Grad? Sollten sie nicht in dieselbe Einheit umgewandelt werden?
Rangel Reale
1
Nein, der Fudge-Faktor ist ein Skalierungsfaktor, der an den Polen 0 und am Äquator 1 beträgt. Es ist weder in Grad noch im Bogenmaß, es ist nur eine Zahl ohne Einheit. Die Java Math.cos-Funktion erfordert ein Argument im Bogenmaß, und ich nahm an, dass <lat> in Grad angegeben ist, daher die Math.toRadians-Funktion. Der resultierende Kosinus hat jedoch keine Einheiten.
Karde
68

Ich weiß, dass dies beantwortet und akzeptiert wurde, dachte aber, ich würde meine Erfahrungen und Lösungen hinzufügen.

Während ich gerne eine Haversine-Funktion auf dem Gerät ausführte, um die genaue Entfernung zwischen der aktuellen Position des Benutzers und einem bestimmten Zielort zu berechnen, musste die Abfrageergebnisse in der Reihenfolge der Entfernung sortiert und begrenzt werden.

Die weniger als zufriedenstellende Lösung besteht darin, das Los zurückzugeben und nachträglich zu sortieren und zu filtern. Dies würde jedoch dazu führen, dass ein zweiter Cursor und viele unnötige Ergebnisse zurückgegeben und verworfen werden.

Meine bevorzugte Lösung bestand darin, in einer Sortierreihenfolge der quadratischen Deltawerte von Long und Lats zu übergeben:

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

Es ist nicht erforderlich, den vollständigen Haversine nur für eine Sortierreihenfolge auszuführen, und es ist nicht erforderlich, die Ergebnisse zu quadrieren, sodass SQLite die Berechnung durchführen kann.

BEARBEITEN:

Diese Antwort empfängt immer noch Liebe. In den meisten Fällen funktioniert es einwandfrei. Wenn Sie jedoch etwas mehr Genauigkeit benötigen, lesen Sie bitte die Antwort von @Teasel unten, in der ein "Fudge" -Faktor hinzugefügt wird, der Ungenauigkeiten behebt, die zunehmen, wenn sich der Breitengrad 90 nähert.

Chris Simpson
quelle
Gute Antwort. Können Sie erklären, wie es funktioniert hat und wie dieser Algorithmus heißt?
iMatoria
3
@iMatoria - Dies ist nur eine abgespeckte Version des berühmten Satzes von Pythonagoras. Bei zwei Koordinatensätzen repräsentiert die Differenz zwischen den beiden X-Werten eine Seite eines rechtwinkligen Dreiecks und die Differenz zwischen den Y-Werten die andere. Um die Hypotenuse (und damit den Abstand zwischen den Punkten) zu erhalten, addieren Sie die Quadrate dieser beiden Werte und wurzeln dann das Ergebnis. In unserem Fall machen wir nicht das letzte Stück (das Quadratwurzeln), weil wir es nicht können. Glücklicherweise ist dies für eine Sortierreihenfolge nicht erforderlich.
Chris Simpson
6
In meiner App BostonBusMap habe ich diese Lösung verwendet, um Haltestellen anzuzeigen, die dem aktuellen Standort am nächsten liegen. Sie müssen jedoch den Längengradabstand so skalieren cos(latitude), dass Breiten- und Längengrad ungefähr gleich sind. Siehe en.wikipedia.org/wiki/…
Noisecapella
0

Um die Leistung so weit wie möglich zu steigern, schlage ich vor, die Idee von @Chris Simpson mit der folgenden ORDER BYKlausel zu verbessern :

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

In diesem Fall sollten Sie die folgenden Werte aus dem Code übergeben:

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

Und Sie sollten auch LAT_LON_SQ_SUM = LAT_COL^2 + LON_COL^2als zusätzliche Spalte in der Datenbank speichern. Füllen Sie es aus und fügen Sie Ihre Entitäten in die Datenbank ein. Dies verbessert die Leistung geringfügig, während große Datenmengen extrahiert werden.

Sergey Metlov
quelle
-3

Versuchen Sie so etwas:

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

Danach enthält id das gewünschte Element aus der Datenbank, damit Sie es abrufen können:

    //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)); 

Hoffentlich hilft das!

Scott Helme
quelle