Szybszy sposób obliczania odległości geograficznej między dwoma punktami

Question

Pożyczyłem następującą metodę z dowolnego miejsca w Internecie (nie pamiętam gdzie). Ale robi to prosty proces, znajdując odległość między dwoma punktami GPS. Działa dobrze, z tym wyjątkiem, że może być trochę powolny, ponieważ używam go przez miliony punktów. Zastanawiam się, czy ktoś zna podejście, które byłoby obliczeniowo tańsze.

Dokładność musi być w obszarze ogólnym "poprawne", ale nie musi być w 100% dokładna.

private double distFrom(double lat1, double lng1, double lat2, double lng2) { 
    double earthRadius = 3958.75; 
    double dLat = Math.toRadians(lat2-lat1); 
    double dLng = Math.toRadians(lng2-lng1); 
    double a = Math.sin(dLat/2) * Math.sin(dLat/2) + 
      Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2)) * 
      Math.sin(dLng/2) * Math.sin(dLng/2); 
    double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
    return earthRadius * c; 
    } 
} 

P.s Rzeczywiście znalazłem wiele innych istotnych pytań, ale one tak naprawdę nie koncentrują się na moich obawach dotyczących prędkości.

Answer 1

Jeśli nie przeszkadza ignorując lekką spłaszczenia Ziemi (a pisał kod Haversine właśnie to robi tak) rozważyć sprzed konwersji wszystkich swoich kulisty (długość/szerokość geograficzna) koordynuje w 3D jednostek uczestnictwa długość współrzędne kartezjańskie pierwsze, za:

http://en.wikipedia.org/wiki/Spherical_coordinate_system

wówczas kulisty odległość między współrzędnych kartezjańskich p1 i p2 jest prosta:

r * acos(p1 . p2) 

Ponieważ p1 i p2 będzie miał długość jednostkową Zmniejsza cztery mnożenia, dwa dodatki i jednym odwrotnym trygonometrycznych działania na parę.

Należy również zauważyć, że obliczanie produktów z kropek jest idealnym kandydatem do optymalizacji, np. przez GPU, rozszerzenia MMX, bibliotek wektorów itp

Ponadto, jeśli zamiarem jest celu par według odległości, ignorując potencjalnie bardziej odległe pary, można odroczyć drogiego r*acos() część równania sortując listę tylko na wartość iloczynu skalarnego gdyż dla wszystkich poprawnych danych wejściowych (tj zakresie [-1, 1]), jest gwarantowane, że:

acos(x) < acos(y) if x > y 

wtedy po prostu wziąć acos() z wartościami jesteś rzeczywiście zainteresowany

Odp.: po niedokładności związane z używaniem acos(), są one naprawdę istotne tylko w przypadku używania zmiennych o pojedynczej precyzji float. Użycie znacznika cyfr o 16 cyfrach powinno zapewnić odległości z dokładnością do jednego metra lub mniejszą.

Answer 2

To algorytm haversine, zapewni ci przyzwoity poziom dokładności.

Jeśli to naprawdę "miliony" punktów, być może zaimplementuj pamięć podręczną obliczeń, które wykonałeś ... jeśli natkniesz się na parę współrzędnych, które są wystarczająco blisko pary, której odległości " ve już wyliczył, a następnie użyć wartości buforowanej?

Lub spróbuj wykonać buforowanie niektórych pośrednich kroków, np. konwersje stopni do radianów.

Answer 3

Jeśli poświęcisz dokładność, możesz wprowadzić pewne ulepszenia. O ile pamiętam, sin(x) jest approximately równa x dla małych x. Wygląda również na to, że kilka razy obliczasz te same rzeczy, na przykład: Math.sin(dLat/2) (która może być w przybliżeniu równa dLat/2, jak podano powyżej).

Jednak jeśli wykonujesz miliony takich operacji, to gdzie indziej.

• Czy Twój algorytm jest optymalny? Może robisz zbyt wiele prostych obliczeń?

• Jeśli punkty pochodzą z bazy danych, czy można wykonać obliczenia jako procedury przechowywane po stronie serwera bazy danych?

• Jeśli szukasz najbliższych punktów, możesz je jakoś zindeksować?

• Czy indeksy geoprzestrzenne mogą Ci pomóc?

Answer 4

Możecie spróbować twierdzenie cosinusów dla trygonometrii sferycznej:

a = sin(lat1) * sin(lat2) 
b = cos(lat1) * cos(lat2) * cos(lon2 - lon1) 
c = arccos(a + b) 
d = R * c 

Ale będzie być niedokładne na krótkich dystansach (i prawdopodobnie po prostu rośnie nieznacznie szybciej).

Istnieje pełna dyskusja here. Jednak formuła haversine jest najbardziej poprawną metodą, więc poza tym, co sugerują inni, może nie być wiele, co możesz zrobić. @ Odpowiedź Alnitaka może działać, ale sferyczne do kartezjańskich konwersji niekoniecznie są szybkie.