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

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!

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.

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

Rozszerzenia GIS PostgreSQL mogą być pomocne - podobnie jak w przypadku, mogą już implementować wiele funkcji, o których myślisz.

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;

Pomocne mogą okazać się te pytania:

• Formuły do ​​obliczania odległości geograficznej
• Maksymalna długość dziesiętnej szerokości / długości geograficznej Stopień?

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?”.

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

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.

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.

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

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;