Algorithmus zum Finden aller Latitude Longitude-Standorte innerhalb einer bestimmten Entfernung von einem bestimmten Lat Lng-Standort

84

Wie würde ich bei einer Datenbank mit Orten mit Längen- und Breitengraden wie 40.8120390, -73.4889650 alle Orte in einer bestimmten Entfernung von einem bestimmten Ort finden?

Es scheint nicht sehr effizient zu sein, alle Standorte aus der Datenbank auszuwählen und sie dann einzeln durchzugehen, um die Entfernung vom Startort zu ermitteln und festzustellen, ob sie innerhalb der angegebenen Entfernung liegen. Gibt es eine gute Möglichkeit, die ursprünglich ausgewählten Standorte aus der Datenbank einzugrenzen? Wenn ich eine eingegrenzte Anzahl von Orten habe (oder nicht?), Gehe ich sie immer noch einzeln durch, um die Entfernung zu überprüfen, oder gibt es einen besseren Weg?

Die Sprache, in der ich das mache, spielt keine Rolle. Vielen Dank!

Valera
quelle
4
Dies kann sein, was Sie brauchen: en.wikipedia.org/wiki/K-d_tree
biziclop
1
Konnte nicht eine SQL-Abfrage das Problem lösen? SELECT * FROM Orte, an denen (Lat -: Lat) ^ 2 + (Long -: Long) ^ 2 <=: Distance ^ 2 (ofc, eine andere Mathematik ist daran beteiligt, dass die Erde sphärisch ist und alles, dies ist nur ein Beispiel)
Dialecticus
1
@Ashu, nOiAd, Leider musste ich dieses Projekt aufgeben, damit ich keine Lösung fand. Wenn Sie eine der Lösungen in Ihren Projekten verwenden, würden ich und andere Ihre Kommentare hier wirklich begrüßen.
Valera

Antworten:

41

Vergleichen Sie zunächst den Abstand zwischen den Breiten. Jeder Breitengrad ist ungefähr 111 Kilometer voneinander entfernt. Die Reichweite variiert (aufgrund der leicht ellipsoiden Form der Erde) von 110,567 km (68,703 Meilen) am Äquator bis 111,699 km (69,407 Meilen) an den Polen. Der Abstand zwischen zwei Orten ist gleich oder größer als der Abstand zwischen ihren Breiten.

Beachten Sie, dass dies für Längengrade nicht gilt - die Länge jedes Längengrads hängt vom Breitengrad ab. Wenn Ihre Daten jedoch an ein bestimmtes Gebiet gebunden sind (z. B. ein einzelnes Land), können Sie auch für die Längen eine minimale und maximale Grenze berechnen.


Fahren Sie mit einer schnellen Entfernungsberechnung mit geringer Genauigkeit fort, bei der sphärische Erde vorausgesetzt wird:

Der Großkreisabstand d zwischen zwei Punkten mit den Koordinaten {lat1, lon1} und {lat2, lon2} ist gegeben durch:

d = acos(sin(lat1)*sin(lat2)+cos(lat1)*cos(lat2)*cos(lon1-lon2))

Eine mathematisch äquivalente Formel, die für kurze Entfernungen weniger Rundungsfehlern unterliegt, lautet:

d = 2*asin(sqrt((sin((lat1-lat2)/2))^2 +
    cos(lat1)*cos(lat2)*(sin((lon1-lon2)/2))^2))

d ist der Abstand im Bogenmaß

distance_km ≈ radius_km * distance_radians ≈ 6371 * d

(6371 km ist der durchschnittliche Radius der Erde )

Die Berechnungsanforderungen für diese Methode sind minimal. Das Ergebnis ist jedoch für kleine Entfernungen sehr genau.


Wenn es sich dann mehr oder weniger in einer bestimmten Entfernung befindet, verwenden Sie eine genauere Methode.

GeographicLib ist die genaueste Implementierung, die ich kenne, obwohl auch die inverse Vincenty-Formel verwendet werden kann.


Wenn Sie ein RDBMS verwenden, legen Sie den Breitengrad als Primärschlüssel und den Längengrad als Sekundärschlüssel fest. Fragen Sie nach einem Breitengradbereich oder nach einem Breiten- / Längengradbereich ab, wie oben beschrieben, und berechnen Sie dann die genauen Entfernungen für die Ergebnismenge.

Beachten Sie, dass moderne Versionen aller wichtigen RDBMS geografische Datentypen und Abfragen nativ unterstützen.

Lior Kogan
quelle
Nur einen Kopf hoch, der erste Link ist kaputt.
k richtet
@kunruh: Danke. Der Link zeigte auf Ed Williams 'Aviation Formulary, das jetzt offline zu sein scheint. Ich habe den Link durch eine Formel ersetzt.
Lior Kogan
Dieser Link erklärte fast alle im Zusammenhang mit diesem Thema movable-type.co.uk/scripts/…
madeinQuant
14

Basierend auf dem Breiten- und Längengrad des aktuellen Benutzers und der Entfernung, die Sie suchen möchten, wird die SQL-Abfrage unten angegeben.

SELECT * FROM(
    SELECT *,(((acos(sin((@latitude*pi()/180)) * sin((Latitude*pi()/180))+cos((@latitude*pi()/180)) * cos((Latitude*pi()/180)) * cos(((@longitude - Longitude)*pi()/180))))*180/pi())*60*1.1515*1.609344) as distance FROM Distances) t
WHERE distance <= @distance

@latitude und @longitude sind der Breiten- und Längengrad des Punktes. Breite und Länge sind die Spalten der Entfernungstabelle. Der Wert von pi ist 22/7

Yogihosting
quelle
2
Ist der Parameter @distance in KMs oder Miles?
Garfbradaz
Ich gehe davon aus, dass die Entfernung in km angegeben ist oder mein Skript falsch ist. Bitte beantworten Sie die obige Frage.
Omar Abbas
7

PostgreSQL GIS-Erweiterungen können hilfreich sein - da sie möglicherweise bereits einen Großteil der Funktionen implementieren, die Sie implementieren möchten.

Gian
quelle
5

Tank´s Yogihosting

Ich habe eine Gruppe von Tabellen aus Open Streep Maps in meiner Datenbank und habe sie erfolgreich getestet.

Entfernung funktioniert gut in Metern.

SET @orig_lat=-8.116137;
SET @orig_lon=-34.897488;
SET @dist=1000;

SELECT *,(((acos(sin((@orig_lat*pi()/180)) * sin((dest.latitude*pi()/180))+cos((@orig_lat*pi()/180))*cos((dest.latitude*pi()/180))*cos(((@orig_lon-dest.longitude)*pi()/180))))*180/pi())*60*1.1515*1609.344) as distance FROM nodes AS dest HAVING distance < @dist ORDER BY distance ASC LIMIT 100;
Helmut Kemper
quelle
Die Welt ist keine Kugel!
Toby Speight
Was ist dein Vorschlag?
Helmut Kemper
2

Wie von biziclop erwähnt, ist wahrscheinlich eine Art metrischer Raumbaum die beste Option. Ich habe Erfahrung mit kd-Bäumen und Quad-Bäumen, um diese Art von Bereichsabfragen durchzuführen, und sie sind erstaunlich schnell. Sie sind auch nicht so schwer zu schreiben. Ich würde vorschlagen, eine dieser Strukturen zu untersuchen, da Sie damit auch andere interessante Fragen beantworten können, z. B. "Was ist der nächstgelegene Punkt in meinem Datensatz zu diesem anderen Punkt?".

templatetypedef
quelle
Während dies ein wertvoller Hinweis zur Lösung des Problems sein kann, muss eine Antwort wirklich die Lösung demonstrieren. Bitte bearbeiten Sie , um einen Beispielcode bereitzustellen, der zeigt, was Sie meinen. Alternativ können Sie dies stattdessen als Kommentar schreiben.
Toby Speight
1
Ich denke tatsächlich, dass Code hier ablenken würde - er wäre zu spezifisch für die Bibliothek, die die Baumstruktur und die bestimmte ausgewählte Sprache enthält (beachten Sie, dass diese Frage nicht mit einer Sprache versehen ist.)
templatetypedef
0

Sie können Längen- und Breitengrade in das UTM-Format konvertieren. Hierbei handelt es sich um ein metrisches Format, mit dessen Hilfe Sie Entfernungen berechnen können. Dann können Sie leicht entscheiden, ob der Punkt an einer bestimmten Stelle liegt.

Hamdi
quelle
1
Während dies ein wertvoller Hinweis zur Lösung des Problems sein kann, muss eine Antwort wirklich die Lösung demonstrieren. Bitte bearbeiten Sie , um einen Beispielcode bereitzustellen, der zeigt, was Sie meinen. Alternativ können Sie dies stattdessen als Kommentar schreiben.
Toby Speight
0

Da Sie sagen, dass jede Sprache akzeptabel ist, ist PostGIS die natürliche Wahl:

SELECT * FROM places
WHERE ST_DistanceSpheroid(geom, $location, $spheroid) < $max_metres;

Wenn Sie WGS Datum verwenden möchten, sollten Sie setzen $spheroidauf'SPHEROID["WGS 84",6378137,298.257223563]'

Angenommen, Sie haben placesnach der geomSpalte indiziert , sollte dies einigermaßen effizient sein.

Toby Speight
quelle
0

Dank der von @yogihosting bereitgestellten Lösung konnte ich ähnliche Ergebnisse aus schemenlosen Spalten von MySQL mit den unten gezeigten Codes erzielen:

// @params - will be bound to named query parameters
$criteria = [];
$criteria['latitude'] = '9.0285183';
$criteria['longitude'] = '7.4869546';
$criteria['distance'] = 500;
$criteria['skill'] = 'software developer';

// Get doctrine connection 
$conn = $this->getEntityManager()->getConnection();

        $sql = '
               SELECT DISTINCT m.uuid AS phone, (((acos(sin((:latitude*pi()/180)) * sin((JSON_EXTRACT(m.location, "$.latitude")*pi()/180))+cos((:latitude*pi()/180)) * 
              cos((JSON_EXTRACT(m.location, "$.latitude")*pi()/180)) * 
              cos(((:longitude - JSON_EXTRACT(m.location, "$.longitude"))*pi()/180))))*180/pi())*60*1.1515*1.609344) AS distance FROM member_profile AS m 
               INNER JOIN member_card_subscription mcs ON mcs.primary_identity = m.uuid
               WHERE mcs.end > now() AND JSON_SEARCH(m.skill_logic, "one", :skill) IS NOT NULL  AND (((acos(sin((:latitude*pi()/180)) * sin((JSON_EXTRACT(m.location, "$.latitude")*pi()/180))+cos((:latitude*pi()/180)) * 
              cos((JSON_EXTRACT(m.location, "$.latitude")*pi()/180)) * 
              cos(((:longitude - JSON_EXTRACT(m.location, "$.longitude"))*pi()/180))))*180/pi())*60*1.1515*1.609344) <= :distance ORDER BY distance
               ';
        $stmt = $conn->prepare($sql);
        $stmt->execute(['latitude'=>$criteria['latitude'], 'longitude'=>$criteria['longitude'], 'skill'=>$criteria['skill'], 'distance'=>$criteria['distance']]);
        var_dump($stmt->fetchAll());

Bitte beachten Sie, dass das obige Code-Snippet die Doctrine DB-Verbindung und PHP verwendet

Frederick Eze
quelle
-2

Sie können diese Gleichung überprüfen, ich denke, es wird helfen

SELECT id, ( 3959 * acos( cos( radians(37) ) * cos( radians( lat ) ) * cos( radians( lng ) - radians(-122) ) + sin( radians(37) ) * sin( radians( lat ) ) ) ) AS distance FROM markers HAVING distance < 25 ORDER BY distance LIMIT 0 , 20;
Emad Elmogy
quelle
Obwohl dieser Code zur Lösung des Problems beitragen kann, erklärt er nicht, warum und / oder wie er die Frage beantwortet. Die Bereitstellung dieses zusätzlichen Kontextes würde den langfristigen Bildungswert erheblich verbessern. Bitte bearbeiten Sie Ihre Antwort, um eine Erklärung hinzuzufügen, einschließlich der Einschränkungen und Annahmen. Woher kommen insbesondere die magischen Werte 3959 und 37?
Toby Speight