Algorytm znajdujący wszystkie lokalizacje szerokości i długości geograficznej w określonej odległości od danej lokalizacji szerokości geograficznej

85

Biorąc pod uwagę bazę danych miejsc z lokalizacjami Latitude + Longitude, na przykład 40.8120390, -73.4889650, jak znaleźć wszystkie lokalizacje w określonej odległości od określonej lokalizacji?

Nie wydaje się zbyt wydajne wybieranie wszystkich lokalizacji z bazy danych, a następnie przechodzenie przez nie jedna po drugiej, sprawdzając odległość od lokalizacji początkowej, aby sprawdzić, czy znajdują się w określonej odległości. Czy istnieje dobry sposób na zawężenie początkowo wybranych lokalizacji z bazy danych? Kiedy już mam (lub nie) zawężony zestaw lokalizacji, czy nadal przechodzę przez nie pojedynczo, aby sprawdzić odległość, czy jest lepszy sposób?

Język, w którym to robię, nie ma znaczenia. Dzięki!

Valera
źródło
4
To może być to, czego potrzebujesz: en.wikipedia.org/wiki/K-d_tree
biziclop
1
Czy jedno zapytanie SQL nie mogłoby go rozwiązać? SELECT * FROM Places WHERE (Lat -: Lat) ^ 2 + (Long -: Long) ^ 2 <=: Distance ^ 2 (ofc, inna matematyka związana jest z kulistością Ziemi i tak dalej, to tylko przykład)
Dialecticus
1
@Ashu, nOiAd, Niestety musiałem porzucić ten projekt, więc nie wybrałem rozwiązania. Jeśli korzystacie z jednego z rozwiązań w swoich projektach, ja i inni bylibyśmy wdzięczni za komentarze na ten temat.
Valera

Odpowiedzi:

41

Zacznij od porównania odległości między szerokościami geograficznymi. Każdy stopień szerokości geograficznej jest oddalony od siebie o około 111 kilometrów. Zasięg waha się (ze względu na lekko elipsoidalny kształt Ziemi) od 68,703 mil (110,567 km) na równiku do 69,407 (111,699 km) na biegunach. Odległość między dwoma lokalizacjami będzie równa lub większa niż odległość między ich szerokościami geograficznymi.

Zauważ, że nie dotyczy to długości geograficznych - długość każdego stopnia zależy od szerokości geograficznej. Jeśli jednak twoje dane są ograniczone do jakiegoś obszaru (na przykład pojedynczego kraju) - możesz obliczyć minimalne i maksymalne granice również dla długości geograficznych.


Kontynuacja będzie szybkim obliczeniem odległości o niskiej dokładności, które zakłada kulistą ziemię:

Odległość po ortodromie d między dwoma punktami o współrzędnych {lat1, lon1} i {lat2, lon2} jest wyrażona wzorem:

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

Matematycznie równoważny wzór, który jest mniej podatny na błąd zaokrąglania dla krótkich odległości, to:

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

d to odległość w radianach

distance_km ≈ radius_km * distance_radians ≈ 6371 * d

(6371 km to średni promień Ziemi )

Wymagania obliczeniowe tej metody są minimalne. Jednak wynik jest bardzo dokładny dla małych odległości.


Następnie, jeśli jest w określonej odległości, mniej więcej, zastosuj dokładniejszą metodę.

GeographicLib to najdokładniejsza implementacja, jaką znam, chociaż można również użyć odwrotnego wzoru Vincenty'ego .


Jeśli korzystasz z systemu RDBMS, ustaw szerokość geograficzną jako klucz podstawowy, a długość geograficzną jako klucz dodatkowy. Zapytanie o zakres szerokości geograficznych lub o zakres szerokości / długości geograficznej, jak opisano powyżej, a następnie obliczyć dokładne odległości dla zestawu wyników.

Należy zauważyć, że nowoczesne wersje wszystkich głównych systemów RDBMS natywnie obsługują geograficzne typy danych i zapytania.

Lior Kogan
źródło
Tylko jedno ostrzeżenie, pierwsze łącze jest zepsute.
kunruh
@kunruh: Dziękuję. Link wskazywał na Aviation Formulary Eda Williamsa, który wydaje się być teraz offline. Zamieniłem łącze na formułę.
Lior Kogan
Ten link wyjaśniał prawie wszystkie związane z tym tematem movable-type.co.uk/scripts/ ...
madeinQuant
14

W oparciu o szerokość i długość geograficzną bieżącego użytkownika oraz odległość, którą chcesz znaleźć, zapytanie sql podano poniżej.

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 i @longitude to szerokość i długość geograficzna punktu. Szerokość i długość geograficzna to kolumny tabeli odległości. Wartość pi wynosi 22/7

yogihosting
źródło
2
Czy parametr @distance jest wyrażony w km czy milach?
garfbradaz
Zakładam, że odległość jest w kilometrach lub mój skrypt będzie błędny. Niech ktoś odpowie na powyższe pytanie.
Omar Abbas
5

Tank´s Yogihosting

Mam w swojej bazie danych jedną grupę tabel z Open Streep Maps i pomyślnie przetestowałem.

Odległość działa dobrze w metrach.

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
źródło
Świat nie jest kulą!
Toby Speight
Co sugerujesz?
Helmut Kemper
2

Jak wspomniał biziclop, prawdopodobnie najlepszym rozwiązaniem będzie jakieś drzewo z przestrzenią metryczną. Mam doświadczenie w używaniu kd-trees i quad trees do wykonywania tego rodzaju zapytań o zakres i są one zadziwiająco szybkie; nie są też takie trudne do napisania. Proponuję przyjrzeć się jednej z tych struktur, ponieważ pozwalają one również odpowiedzieć na inne interesujące pytania, takie jak „Jaki jest najbliższy punkt w moim zbiorze danych do tego innego punktu?”.

templatetypedef
źródło
Chociaż może to być cenna wskazówka do rozwiązania problemu, odpowiedź naprawdę musi zademonstrować rozwiązanie. Proszę edit dostarczyć przykładowy kod, aby pokazać to, co masz na myśli. Alternatywnie, zamiast tego rozważ napisanie tego jako komentarza.
Toby Speight
1
Właściwie myślę, że tutaj kod byłby rozpraszający - byłby zbyt specyficzny dla biblioteki zawierającej strukturę drzewa i konkretny wybrany język (zwróć uwagę, że to pytanie nie jest tagowane językiem).
templatetypedef
1

Potrzebujesz wyszukiwania przestrzennego. Możesz skorzystać z wyszukiwania Solr Spatial . Ma również wbudowany typ danych lat / long, sprawdź tutaj .

Zimbabao
źródło
Chociaż może to teoretycznie odpowiedzieć na pytanie, lepiej byłoby zawrzeć tutaj zasadnicze części odpowiedzi i podać link do odniesienia.
Toby Speight
0

Możesz przekonwertować długość i szerokość geograficzną na format UTM, który jest formatem metrycznym, który może pomóc w obliczaniu odległości. Wtedy możesz łatwo zdecydować, czy punkt przypada w określonej lokalizacji.

Hamdi
źródło
1
Chociaż może to być cenna wskazówka do rozwiązania problemu, odpowiedź naprawdę musi zademonstrować rozwiązanie. Proszę edit dostarczyć przykładowy kod, aby pokazać to, co masz na myśli. Alternatywnie, zamiast tego rozważ napisanie tego jako komentarza.
Toby Speight
0

Ponieważ mówisz, że każdy język jest akceptowalny, naturalnym wyborem jest PostGIS:

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

Jeśli chcesz używać odniesienia WGS, powinieneś ustawić $spheroidna'SPHEROID["WGS 84",6378137,298.257223563]'

Zakładając, że zindeksowano placeswedług geomkolumny, powinno to być dość wydajne.

Toby Speight
źródło
0

Dzięki rozwiązaniu dostarczonemu przez @yogihosting udało mi się osiągnąć podobny wynik z bezschematycznych kolumn mysql z kodami pokazanymi poniżej:

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

Proszę zauważyć, że powyższy fragment kodu korzysta z połączenia bazy danych doctrine i PHP

Frederick Eze
źródło
-2

możesz sprawdzić to równanie, myślę, że to pomoże

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
źródło
Chociaż ten kod może pomóc w rozwiązaniu problemu, nie wyjaśnia, dlaczego i / lub jak odpowiada na pytanie. Zapewnienie tego dodatkowego kontekstu znacznie poprawiłoby jego długoterminową wartość edukacyjną. Proszę edytować swoje odpowiedzi, aby dodać wyjaśnienie, w tym, co stosuje się ograniczenia i założenia. W szczególności, skąd pochodzą magiczne wartości 3959 i 37?
Toby Speight