Schnellste Weg, um Finden Sie Abstand Zwischen Zwei Lat/Long Punkte

StackOverflow https://stackoverflow.com/questions/1006654

  •  06-07-2019
  •  | 
  •  

Frage

Ich habe derzeit knapp eine million Standorten in einer mysql-Datenbank alle mit Längen-und Breitengrad Informationen.

Ich bin auf der Suche nach den Abstand zwischen einem Punkt und viele andere Punkte, über eine Abfrage.Es ist nicht so schnell, wie ich will, es werden vor allem mit 100+ trifft ein zweiter.

Gibt es eine schnellere Abfrage oder möglicherweise ein schnelleres system andere als mysql für diese?Ich benutze diese Abfrage:

SELECT 
  name, 
   ( 3959 * acos( cos( radians(42.290763) ) * cos( radians( locations.lat ) ) 
   * cos( radians(locations.lng) - radians(-71.35368)) + sin(radians(42.290763)) 
   * sin( radians(locations.lat)))) AS distance 
FROM locations 
WHERE active = 1 
HAVING distance < 10 
ORDER BY distance;

Hinweis:Die bereitgestellten Entfernung wird in Meilen.Wenn Sie brauchen, Kilometer, verwenden Sie 6371 statt 3959.

War es hilfreich?

Lösung

  • Erstellen Sie Ihre Punkte Point Werte von Geometry Datentypen in MyISAM Tabelle. Ab Mysql 5.7.5, InnoDB Tabellen auch jetzt SPATIAL Indizes unterstützen.

  • einen SPATIAL Index auf diesen Punkten erstellen

  • Mit MBRContains() die Werte zu finden: 

    SELECT  *
FROM    table
WHERE   MBRContains(LineFromText(CONCAT(
        '('
        , @lon + 10 / ( 111.1 / cos(RADIANS(@lon)))
        , ' '
        , @lat + 10 / 111.1
        , ','
        , @lon - 10 / ( 111.1 / cos(RADIANS(@lat)))
        , ' '
        , @lat - 10 / 111.1 
        , ')' )
        ,mypoint)

oder in MySQL 5.1 und oben: 

    SELECT  *
    FROM    table
    WHERE   MBRContains
                    (
                    LineString
                            (
                            Point (
                                    @lon + 10 / ( 111.1 / COS(RADIANS(@lat))),
                                    @lat + 10 / 111.1
                                  ),
                            Point (
                                    @lon - 10 / ( 111.1 / COS(RADIANS(@lat))),
                                    @lat - 10 / 111.1
                                  ) 
                            ),
                    mypoint
                    )

Damit werden alle Punkte auswählen etwa im Feld (@lat +/- 10 km, @lon +/- 10km).

Dies ist eigentlich kein Kasten, sondern ein sphärisches Rechteck: Breitengrad und Längengrad-Segment der Kugel gebunden. Dies kann von einem einfachen Rechteck auf der Seite Franz-Joseph-Land unterscheidet , aber ganz in der Nähe, um es auf den meisten bewohnten Orten.

  • Anwenden zusätzliche Filterung alles innerhalb des Kreises (nicht das Quadrat)

    • wählen

  • Möglicherweise gilt zusätzliche Feinfilterung für die große Kreisentfernung zu berücksichtigen (für große Entfernungen)

Andere Tipps

Nicht eine MySql spezifische Antwort, aber es wird die Leistung Ihrer SQL-Anweisung verbessern.

Was sind Sie effektiv tun wird, um den Abstand zu jedem Punkt in der Tabelle berechnet wird, um zu sehen, wenn sie innerhalb von 10 Einheiten eines gegebenen Punktes.

Was Sie tun können, bevor Sie diese SQL ausführen, ist vier Punkte erstellen, die eine Box 20 Einheiten auf einer Seite ziehen, mit dem Punkt in der Mitte heißt .. (x1, y1). . . (X4, y4), wobei (x1, y1) ist (givenlong + 10 Einheiten, 10 Einheiten givenLat +). . . (GivenLong - 10 Einheiten, givenLat -10 Einheiten). Eigentlich brauchen Sie nur zwei Punkte, oben links und unten rechts nennen sie (X1, Y1) und (X2, Y2)

Jetzt ist Ihre SQL-Anweisung, diese Punkte zu verwenden, um Zeilen auszuschließen, die auf jeden Fall mehr als 10u aus dem gegebenen Punkt sind, kann es Indizes für die Breiten und Längen verwenden, so wird um Größenordnungen schneller als das, was Sie im Moment haben.

z. 

select . . . 
where locations.lat between X1 and X2 
and   locations.Long between y1 and y2;

Der Box-Ansatz falsch positive Ergebnisse zurückgeben kann (können Sie Punkte in den Ecken der Box abholen, die> 10u aus dem gegebenen Punkt sind), so dass Sie immer noch die Entfernung von jedem Punkt berechnen müssen. Doch dies wird wieder viel schneller, weil Sie drastisch die Anzahl der Punkte beschränkt sind auf die Punkte innerhalb der Box zu testen.

Ich nenne diese Technik "Denken in der Box":)

EDIT:? Kann diese in einer SQL-Anweisung gesetzt werden

Ich habe keine Ahnung, was mySql oder Php fähig ist, sorry ist. Ich weiß nicht, wo der beste Platz ist, um die vier Punkte zu bauen, oder wie sie auf eine MySQL-Abfrage in Php weitergegeben werden können. Allerdings, wenn Sie die vier Punkte haben, gibt es nichts hindert Sie mit meinen Ihre eigene SQL-Anweisung kombiniert werden. 

select name, 
       ( 3959 * acos( cos( radians(42.290763) ) 
              * cos( radians( locations.lat ) ) 
              * cos( radians( locations.lng ) - radians(-71.35368) ) 
              + sin( radians(42.290763) ) 
              * sin( radians( locations.lat ) ) ) ) AS distance 
from locations 
where active = 1 
and locations.lat between X1 and X2 
and locations.Long between y1 and y2
having distance < 10 ORDER BY distance;

Ich weiß, mit MS SQL kann ich eine SQL-Anweisung erstellen, die vier Schwimmer (X1, Y1, X2, Y2) und berechnet sich vor der „Haupt“ select-Anweisung erklärt, wie ich schon sagte, ich habe keine Ahnung, ob dies kann getan werden, mit MySql. Allerdings würde ich immer noch geneigt werden, um die vier Punkte in C # zu bauen und sie als Parameter an die SQL-Abfrage übergeben.

Leider kann ich nicht mehr helfen, wenn jemand die MySQL & PHP-spezifische Teile dieser Antwort kann, fühlen sich frei, diese Antwort zu bearbeiten, dies zu tun.

Sehen Sie sich diese Präsentation für eine gute Antwort. Im Grunde ist es zeigt die beiden unterschiedlichen Ansätze in den Kommentaren gezeigt, mit einer ausführlichen Erklärung, warum /, wenn Sie einen oder anderen und warum die „in der Box“ Berechnung sehr interessant sein kann verwendet werden soll.

Geo Umkreissuche mit MySQL

auf dieses Blog-Post wurde die folgende MySQL-Funktion geschrieben. Ich habe es nicht viel getestet, aber von dem, was ich von der Post gesammelt, , wenn Ihre Breiten- und Längenfelder indiziert sind, ist dies für Sie arbeitet gut können: 

DELIMITER $$

DROP FUNCTION IF EXISTS `get_distance_in_miles_between_geo_locations` $$
CREATE FUNCTION get_distance_in_miles_between_geo_locations(geo1_latitude decimal(10,6), geo1_longitude decimal(10,6), geo2_latitude decimal(10,6), geo2_longitude decimal(10,6)) 
returns decimal(10,3) DETERMINISTIC
BEGIN
  return ((ACOS(SIN(geo1_latitude * PI() / 180) * SIN(geo2_latitude * PI() / 180) + COS(geo1_latitude * PI() / 180) * COS(geo2_latitude * PI() / 180) * COS((geo1_longitude - geo2_longitude) * PI() / 180)) * 180 / PI()) * 60 * 1.1515);
END $$

DELIMITER ;

Proben Nutzung: Unter der Annahme einer Tabelle namens Orte mit Feldern Breite und Länge:

  

select get_distance_in_miles_between_geo_locations (-34,017330,   22.809500, Breite, Länge) als distance_from_input von Orten;

alle von diesem Post verhakt 

SELECT * FROM (SELECT *,(((acos(sin((43.6980168*pi()/180)) * 
sin((latitude*pi()/180))+cos((43.6980168*pi()/180)) * 
cos((latitude*pi()/180)) * cos(((7.266903899999988- longitude)* 
pi()/180))))*180/pi())*60*1.1515 ) as distance 
FROM wp_users WHERE 1 GROUP BY ID limit 0,10) as X 
ORDER BY ID DESC

Dies ist die Abstandsberechnung Abfrage zwischen zwei Punkten in MySQL, ich kann es in einer langen Datenbank verwendet habe, sie daran zu arbeiten perfekt! Hinweis:. Tun, um die Änderungen (Datenbankname, Tabellenname, Spalte usw.) nach Ihren Wünschen 

set @latitude=53.754842;
set @longitude=-2.708077;
set @radius=20;

set @lng_min = @longitude - @radius/abs(cos(radians(@latitude))*69);
set @lng_max = @longitude + @radius/abs(cos(radians(@latitude))*69);
set @lat_min = @latitude - (@radius/69);
set @lat_max = @latitude + (@radius/69);

SELECT * FROM postcode
WHERE (longitude BETWEEN @lng_min AND @lng_max)
AND (latitude BETWEEN @lat_min and @lat_max);

Quelle

Wenn Sie MySQL 5.7 verwenden. *, Dann können Sie st_distance_sphere (Punkt, Punkt) . 

Select st_distance_sphere(POINT(-2.997065, 53.404146 ), POINT(58.615349, 23.56676 ))/1000  as distcance

   select
   (((acos(sin(('$latitude'*pi()/180)) * sin((`lat`*pi()/180))+cos(('$latitude'*pi()/180)) 
    * cos((`lat`*pi()/180)) * cos((('$longitude'- `lng`)*pi()/180))))*180/pi())*60*1.1515) 
    AS distance
    from table having distance<22;

Der vollständige Code mit Details darüber, wie zu installieren, wie MySQL-Plugin sind hier: https://github.com/lucasepe / lib_mysqludf_haversine

ich gepostet im vergangenen Jahr als Kommentar. Da freundlich als Antwort zu schreiben @TylerCollier mir vorgeschlagen, hier ist es.

Eine andere Möglichkeit ist es, eine benutzerdefinierte UDF-Funktion zu schreiben, die die Haversine Abstand von zwei Punkten zurück. Diese Funktion kann in Eingabe nehmen: 

lat1 (real), lng1 (real), lat2 (real), lng2 (real), type (string - optinal - 'km', 'ft', 'mi')

So wir so etwas schreiben kann: 

SELECT id, name FROM MY_PLACES WHERE haversine_distance(lat1, lng1, lat2, lng2) < 40;

Alle Datensätze mit einem Abstand holen weniger als 40 Kilometer. Oder: 

SELECT id, name FROM MY_PLACES WHERE haversine_distance(lat1, lng1, lat2, lng2, 'ft') < 25;

Alle Datensätze mit einem Abstand holen weniger als 25 Fuß.

Die Kernfunktion ist: 

double
haversine_distance( UDF_INIT* initid, UDF_ARGS* args, char* is_null, char *error ) {
    double result = *(double*) initid->ptr;
    /*Earth Radius in Kilometers.*/ 
    double R = 6372.797560856;
    double DEG_TO_RAD = M_PI/180.0;
    double RAD_TO_DEG = 180.0/M_PI;
    double lat1 = *(double*) args->args[0];
    double lon1 = *(double*) args->args[1];
    double lat2 = *(double*) args->args[2];
    double lon2 = *(double*) args->args[3];
    double dlon = (lon2 - lon1) * DEG_TO_RAD;
    double dlat = (lat2 - lat1) * DEG_TO_RAD;
    double a = pow(sin(dlat * 0.5),2) + 
        cos(lat1*DEG_TO_RAD) * cos(lat2*DEG_TO_RAD) * pow(sin(dlon * 0.5),2);
    double c = 2.0 * atan2(sqrt(a), sqrt(1-a));
    result = ( R * c );
    /*
     * If we have a 5th distance type argument...
     */
    if (args->arg_count == 5) {
        str_to_lowercase(args->args[4]);
        if (strcmp(args->args[4], "ft") == 0) result *= 3280.8399;
        if (strcmp(args->args[4], "mi") == 0) result *= 0.621371192;
    }

    return result;
}

Eine schnelle, einfache und genaue (für kleinere Distanzen) Näherung kann mit einer sphärischer Projektion erfolgen . Zumindest in meinem Routing-Algorithmus erhalte ich einen 20% Schub im Vergleich zur korrekten Berechnung. In Java-Code sieht es so aus: 

public double approxDistKm(double fromLat, double fromLon, double toLat, double toLon) {
    double dLat = Math.toRadians(toLat - fromLat);
    double dLon = Math.toRadians(toLon - fromLon);
    double tmp = Math.cos(Math.toRadians((fromLat + toLat) / 2)) * dLon;
    double d = dLat * dLat + tmp * tmp;
    return R * Math.sqrt(d);
}

Nicht sicher MySQL (sorry!).

Seien Sie sicher, dass Sie über die Begrenzung kennen (die dritte param von assertEquals bedeutet die Genauigkeit in km): 

    float lat = 24.235f;
    float lon = 47.234f;
    CalcDistance dist = new CalcDistance();
    double res = 15.051;
    assertEquals(res, dist.calcDistKm(lat, lon, lat - 0.1, lon + 0.1), 1e-3);
    assertEquals(res, dist.approxDistKm(lat, lon, lat - 0.1, lon + 0.1), 1e-3);

    res = 150.748;
    assertEquals(res, dist.calcDistKm(lat, lon, lat - 1, lon + 1), 1e-3);
    assertEquals(res, dist.approxDistKm(lat, lon, lat - 1, lon + 1), 1e-2);

    res = 1527.919;
    assertEquals(res, dist.calcDistKm(lat, lon, lat - 10, lon + 10), 1e-3);
    assertEquals(res, dist.approxDistKm(lat, lon, lat - 10, lon + 10), 10);

Hier ist eine sehr detaillierte Beschreibung von Geo Entfernung Suche mit MySQL eine Lösung basiert auf der Umsetzung von Haversine Formel mysql. Die komplette Lösungsbeschreibung mit der Theorie, Umsetzung und weiterer Performance-Optimierung. Obwohl der Teil räumliche Optimierung hat in meinem Fall nicht korrekt funktionieren. http://www.scribd.com/doc/2569355/Geo -Entfernung-Search-mit-MySQL

Haben Sie einen Lese von Geo Umkreissuche mit MySQL eine Lösung basierend auf der Umsetzung Haversine Formel MySQL. Dies ist eine komplette Lösung Beschreibung mit Theorie, Umsetzung und weitere Performance-Optimierung. Obwohl die räumliche Optimierung Teil nicht funktioniert richtig in meinem Fall.

Ich habe bemerkt, zwei Fehler in dieser:

  1. die Verwendung von abs in der select-Anweisung auf p8. Ich abs nur weggelassen und es hat funktioniert.

  2. die räumliche Suche Distanzfunktion auf p27 konvertiert nicht in Radianten oder mehrfach Länge von cos(latitude), es sei denn, seine räumlichen Daten mit diesem in Betracht geladen wird (kann nicht aus dem Kontext des Artikels sagen), aber sein Beispiel auf p26 zeigt an, dass seine räumlichen Daten POINT mit Radianten oder Grad nicht geladen.

A MySQL Funktion, die die Anzahl von m zwischen den beiden Koordinaten zurückgibt: 

CREATE FUNCTION DISTANCE_BETWEEN (lat1 DOUBLE, lon1 DOUBLE, lat2 DOUBLE, lon2 DOUBLE)
RETURNS DOUBLE DETERMINISTIC
RETURN ACOS( SIN(lat1*PI()/180)*SIN(lat2*PI()/180) + COS(lat1*PI()/180)*COS(lat2*PI()/180)*COS(lon2*PI()/180-lon1*PI()/180) ) * 6371000

den Wert in einem anderen Format zurückzukehren, die 6371000 in der Funktion mit dem Radius der Erde in der Wahl der Einheit ersetzen. Zum Beispiel würde gefahrene Kilometer 6371 und Meilen würden 3959 werden.

, um die Funktion nutzen zu können, rufen Sie einfach es wie jede andere Funktion in MySQL. Zum Beispiel, wenn Sie eine Tabelle city haben, kann man den Abstand zwischen jeder Stadt zu jeder anderen Stadt finden: 

SELECT
    `city1`.`name`,
    `city2`.`name`,
    ROUND(DISTANCE_BETWEEN(`city1`.`latitude`, `city1`.`longitude`, `city2`.`latitude`, `city2`.`longitude`)) AS `distance`
FROM
    `city` AS `city1`
JOIN
    `city` AS `city2`

Ich brauchte, um zu lösen ähnliches problem (filtern von Zeilen nach der Entfernung von single-point) und durch die Kombination von original-Frage mit Antworten und Kommentare, ich kam mit einer Lösung, die perfekt funktioniert für mich auf MySQL 5.6 und 5.7. 

SELECT 
    *,
    (6371 * ACOS(COS(RADIANS(56.946285)) * COS(RADIANS(Y(coordinates))) 
    * COS(RADIANS(X(coordinates)) - RADIANS(24.105078)) + SIN(RADIANS(56.946285))
    * SIN(RADIANS(Y(coordinates))))) AS distance
FROM places
WHERE MBRContains
    (
    LineString
        (
        Point (
            24.105078 + 15 / (111.320 * COS(RADIANS(56.946285))),
            56.946285 + 15 / 111.133
        ),
        Point (
            24.105078 - 15 / (111.320 * COS(RADIANS(56.946285))),
            56.946285 - 15 / 111.133
        )
    ),
    coordinates
    )
HAVING distance < 15
ORDER By distance

coordinates ist das Feld mit Typ POINT und hat SPATIAL index
6371 für die Berechnung der Entfernung in Kilometer
56.946285 ist Spielraum für zentrale Punkt
24.105078 ist Längengrad für zentrale Punkt
10 ist die maximale Entfernung in Kilometer

In meinen tests verwendet MySQL RÄUMLICHEN index auf coordinates - Feld, um schnell wählen Sie alle Zeilen, die innerhalb von Rechteck und berechnet dann die tatsächliche Entfernung für alle gefilterten Orte ausschließen Orte, von Rechtecke Ecken und lassen Sie nur Plätze im Kreis.

Dies ist eine Visualisierung von mein Ergebnis:

map

Gray stars visualisieren alle Punkte auf der Karte, gelbe Sterne sind diejenigen zurückgegeben, die vom MySQL-Abfrage.Graue Sterne im inneren Ecken des Rechtecks (aber außerhalb Kreis) ausgewählt wurden, die von MBRContains() und dann deaktiviert, indem HAVING Klausel.

mysql 

SET @orig_lon = 1.027125;
SET @dest_lon = 1.027125;

SET @orig_lat = 2.398441;
SET @dest_lat = 2.398441;

SET @kmormiles = 6371;-- for distance in miles set to : 3956

SELECT @kmormiles * ACOS(LEAST(COS(RADIANS(@orig_lat)) * 
 COS(RADIANS(@dest_lat)) * COS(RADIANS(@orig_lon - @dest_lon)) + 
 SIN(RADIANS(@orig_lat)) * SIN(RADIANS(@dest_lat)),1.0)) as distance;

Siehe auch: https://andrew.hedges.name/experiments/haversine/

Siehe auch: https://stackoverflow.com/a/24372831/5155484

Siehe auch: http://www.plumislandmedia.net/mysql/ Haversine-mysql-nearest-loc /

Hinweis: LEAST wird verwendet, Nullwert zu vermeiden, wie ein Kommentar vorgeschlagen auf https://stackoverflow.com/a/24372831/5155484 

$objectQuery = "SELECT table_master.*, ((acos(sin((" . $latitude . "*pi()/180)) * sin((`latitude`*pi()/180))+cos((" . $latitude . "*pi()/180)) * cos((`latitude`*pi()/180)) * cos(((" . $longitude . "- `longtude`)* pi()/180))))*180/pi())*60*1.1515  as distance FROM `table_post_broadcasts` JOIN table_master ON table_post_broadcasts.master_id = table_master.id WHERE table_master.type_of_post ='type' HAVING distance <='" . $Radius . "' ORDER BY distance asc";
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top