Najszybszy sposób na znalezienie odległości między dwoma punktami Lat / Long

Obecnie mam prawie milion lokalizacji w bazie danych mysql, wszystkie z informacjami o długości i szerokości geograficznej.

Próbuję znaleźć odległość między jednym punktem a wieloma innymi punktami za pomocą zapytania. To nie jest tak szybkie, jak chcę, szczególnie przy ponad 100 trafieniach na sekundę.

Czy istnieje szybsze zapytanie lub być może szybszy system inny niż mysql? Korzystam z tego zapytania:

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;

Uwaga: podana odległość jest w milach . Jeśli potrzebujesz Kilometrów , użyj 6371zamiast 3959.

• Utwórz punkty, używając Pointwartości Geometrytypów danych w MyISAMtabeli. Od wersji Mysql 5.7.5 InnoDBtabele obsługują teraz także SPATIALindeksy.

• Utwórz SPATIALindeks tych punktów

• Użyj, MBRContains()aby znaleźć wartości:

  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)

lub, w MySQL 5.1i powyżej:

    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
                    )

Spowoduje to zaznaczenie wszystkich punktów w przybliżeniu w ramce (@lat +/- 10 km, @lon +/- 10km).

W rzeczywistości nie jest to pudełko, lecz sferyczny prostokąt: segment kuli związany z szerokością i długością geograficzną. To może różnić się od prostokąta na Ziemi Franciszka Józefa , ale dość blisko w większości zamieszkałych miejsc.

• Zastosuj dodatkowe filtrowanie, aby zaznaczyć wszystko wewnątrz okręgu (nie kwadrat)

• Ewentualnie zastosuj dodatkowe dokładne filtrowanie w celu uwzględnienia odległości dużego koła (dla dużych odległości)

Nie jest to odpowiedź specyficzna dla MySql, ale poprawi wydajność twojej instrukcji SQL.

To, co skutecznie robisz, to obliczanie odległości do każdego punktu w tabeli, aby sprawdzić, czy jest w odległości 10 jednostek od danego punktu.

Co możesz zrobić przed uruchomieniem tej sql, to utworzyć cztery punkty, które narysują pudełko 20 jednostek na boku, z punktem w środku, tj. (x1, y1). . . (x4, y4), gdzie (x1, y1) to (dane długie + 10 jednostek, dane Lat + 10 jednostek). . . (danyLong - 10 jednostek, danyLat -10 jednostek). Właściwie potrzebujesz tylko dwóch punktów, nazwij je lewym górnym i prawym dolnym (X1, Y1) i (X2, Y2)

Teraz twoja instrukcja SQL używa tych punktów, aby wykluczyć wiersze, które zdecydowanie przekraczają 10u od twojego punktu, może używać indeksów szerokości i długości geograficznej, więc będzie o rząd wielkości szybszy niż to, co obecnie masz.

na przykład

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

Podejście pudełkowe może zwrócić fałszywie dodatnie (możesz zbierać punkty w rogach pudełka, które są> 10u od danego punktu), więc nadal musisz obliczyć odległość każdego punktu. Jednak to znowu będzie znacznie szybsze, ponieważ drastycznie ograniczyłeś liczbę punktów do przetestowania do punktów w ramce.

Nazywam tę technikę „Myśleniem w pudełku” :)

EDYCJA: Czy można to umieścić w jednej instrukcji SQL?

Przepraszam, nie mam pojęcia, do czego zdolny jest mój SQL lub Php. Nie wiem, gdzie najlepiej jest zbudować cztery punkty, ani jak można je przekazać do zapytania mySql w Php. Jednak gdy zdobędziesz cztery punkty, nic nie stoi na przeszkodzie, aby połączyć własną instrukcję SQL z moją.

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;

Wiem, że dzięki MS SQL mogę zbudować instrukcję SQL, która deklaruje cztery zmiennoprzecinkowe (X1, Y1, X2, Y2) i oblicza je przed „główną” instrukcją select, tak jak powiedziałem, nie mam pojęcia, czy można to zrobić za pomocą MySql. Jednak nadal będę skłonny zbudować cztery punkty w języku C # i przekazać je jako parametry do zapytania SQL.

Przykro mi, że nie mogę pomóc, jeśli ktoś może odpowiedzieć na części MySQL i Php tego, edytuj tę odpowiedź, aby to zrobić.

Poniższa funkcja MySQL została opublikowana na tym blogu . Nie testowałem tego zbyt wiele, ale z tego, co zebrałem z postu, jeśli twoje pola szerokości i długości geograficznej są indeksowane , może to działać dobrze:

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 ;

Przykładowe użycie:

Zakładając, że tabela jest wywoływana placesz polami latitudei longitude:

SELECT get_distance_in_miles_between_geo_locations(-34.017330, 22.809500,
latitude, longitude) AS distance_from_input FROM places;

Musiałem rozwiązać podobny problem (filtrowanie wierszy według odległości od pojedynczego punktu) i łącząc oryginalne pytanie z odpowiedziami i komentarzami, opracowałem rozwiązanie, które doskonale działa dla mnie zarówno w MySQL 5.6, jak i 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

coordinatesjest polem typu POINTi ma SPATIALindeks
6371służy do obliczania odległości w kilometrach
56.946285szerokość geograficzna dla punktu centralnego
24.105078długość geograficzna dla punktu centralnego
15to maksymalna odległość w kilometrach

W moich testach MySQL używa indeksu SPATIAL na coordinatespolu, aby szybko wybrać wszystkie wiersze znajdujące się w prostokącie, a następnie oblicza rzeczywistą odległość dla wszystkich filtrowanych miejsc, aby wykluczyć miejsca z narożników prostokątów i pozostawić tylko miejsca wewnątrz okręgu.

Oto wizualizacja mojego wyniku:

Szare gwiazdy wizualizują wszystkie punkty na mapie, żółte gwiazdy zwracają zapytanie MySQL. Szare gwiazdy w rogach prostokąta (ale poza okręgiem) zostały wybrane przez, MBRContains()a następnie cofnięte przez HAVINGklauzulę.

jeśli używasz MySQL 5.7. *, możesz użyć st_distance_sphere (POINT, POINT) .

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

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

Jest to zapytanie o obliczenie odległości między punktami w MySQL, użyłem go w długiej bazie danych, działa idealnie! Uwaga: wykonaj zmiany (nazwa bazy danych, nazwa tabeli, kolumna itp.) Zgodnie z własnymi wymaganiami.

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

źródło

   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;

Funkcja MySQL, która zwraca liczbę metrów między dwiema współrzędnymi:

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

Aby zwrócić wartość w innym formacie, zamień funkcję 6371000in na promień Ziemi w wybranej jednostce. Na przykład byłyby kilometry 6371i mile 3959.

Aby użyć tej funkcji, po prostu wywołaj ją tak, jak każdą inną funkcję w MySQL. Na przykład, jeśli masz stolik city, możesz znaleźć odległość między każdym miastem do każdego innego miasta:

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`

Pełny kod ze szczegółowymi informacjami na temat instalacji jako wtyczki MySQL znajduje się tutaj: https://github.com/lucasepe/lib_mysqludf_haversine

Zamieściłem ten komentarz w zeszłym roku. Ponieważ uprzejmie @TylerCollier zaproponował mi opublikowanie jako odpowiedzi, oto jest.

Innym sposobem jest napisanie niestandardowej funkcji UDF, która zwraca odległość w poziomie od dwóch punktów. Ta funkcja może pobierać dane wejściowe:

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

Możemy więc napisać coś takiego:

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

aby pobrać wszystkie rekordy z odległości mniejszej niż 40 kilometrów. Lub:

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

aby pobrać wszystkie rekordy z odległości mniejszej niż 25 stóp.

Podstawową funkcją jest:

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

Szybkiej, prostej i dokładnej (dla mniejszych odległości) aproksymacji można dokonać za pomocą projekcji sferycznej . Przynajmniej w moim algorytmie routingu otrzymuję wzrost o 20% w porównaniu do prawidłowego obliczenia. W kodzie Java wygląda to tak:

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

Nie jestem pewien co do MySQL (przepraszam!).

Upewnij się, że wiesz o ograniczeniu (trzeci parametr assertEquals oznacza dokładność w kilometrach):

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

Oto bardzo szczegółowy opis Geo Distance Search z MySQL, rozwiązaniem opartym na implementacji Haversine Formula na mysql. Pełny opis rozwiązania z teorią, implementacją i dalszą optymalizacją wydajności. Chociaż część optymalizacji przestrzennej nie działała poprawnie w moim przypadku. http://www.scribd.com/doc/2569355/Geo-Distance-Search-w--MySQL

Zapoznaj się z Geo Distance Search z MySQL , rozwiązaniem opartym na implementacji Haversine Formula na MySQL. Jest to pełny opis rozwiązania z teorią, implementacją i dalszą optymalizacją wydajności. Chociaż część optymalizacji przestrzennej nie działała poprawnie w moim przypadku.

Zauważyłem w tym dwa błędy:

1. użycie absw instrukcji select na p8. Właśnie pominąłem absi zadziałało.

2. funkcja odległości poszukiwania przestrzennego na p27 nie przekształca się w radiany ani nie mnoży długości geograficznej cos(latitude), chyba że jego dane przestrzenne zostaną w tym uwzględnione (nie można tego stwierdzić z kontekstu artykułu), ale jego przykład na p26 wskazuje, że jego dane przestrzenne POINTnie są załadowane radiany lub stopnie.

$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";

Korzystanie z 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;

Widzieć: https://andrew.hedges.name/experiments/haversine/

Widzieć: https://stackoverflow.com/a/24372831/5155484

Widzieć: http://www.plumislandmedia.net/mysql/haversine-mysql-nearest-loc/

UWAGA: LEASTsłuży do unikania wartości zerowych jako komentarza sugerowanego na https://stackoverflow.com/a/24372831/5155484