Algorytm znajdowania najbliższego punktu

Mam listę kilkuset miast z ich szerokością / długością geograficzną. Biorąc pod uwagę inną lokalizację (także w długości / długości) muszę znaleźć najbliższe miasto.

Ponieważ nie używam żadnego GIS, oczywistym algorytmem jest teraz wykonanie pętli dla wszystkich miast, obliczenie odległości między punktami.

Tworzenie pętli jest dla mnie wykonalne, ale istnieje jakiś łatwy do zaimplementowania algorytm, aby osiągnąć to bardziej efektywnie? Lub jakaś lekka biblioteka Java, która może pomóc w rozwiązaniu tego problemu?

Uwagi : Nie potrzebuję / nie chcę kompletnego rozwiązania GIS ani ciężkiej / skomplikowanej biblioteki. Wolę mniej dobre, ale najłatwiejsze i lżejsze rozwiązanie, ponieważ to jedyna rzecz, którą muszę rozwiązać.

Dokładnie zbadałem to pytanie 20 lat temu, projektując GIS na komputery. Musieliśmy interaktywnie wyszukiwać odległości między punktami; naszym celem było wykonanie obliczeń w tysiącach punktów w czasie krótszym niż 1/2 sekundy. Testy (na komputerze PC 486 o częstotliwości 25 MHz!) Wykazały, że możemy obliczyć wszystkie odległości dokładnie tak, jak to opisujesz (za pomocą prostego oczywistego algorytmu), tak szybko, że nie ma sensu tworzyć bardziej wyrafinowanych rozwiązań, takich jak struktura quadtree. .

Do obliczania odległości do pojedynczego punktu „sondy” opcje obejmują (a) rzutowanie wszystkich punktów za pomocą jednakowo odległej projekcji wyśrodkowanej w punkcie sondy lub (b) przyjęcie sferycznego modelu ziemi i zastosowanie wzoru Haversine . Pierwszy jest odpowiedni, jeśli potrzebujesz dokładności modelu elipsoidalnego. W obu przypadkach obliczenia są dość szybkie, prawdopodobnie przyjmując mniej niż 1000 tyknięć: za pomocą jednego procesora można wykonać zapytanie o około milion punktów na sekundę.

Wystarczająco szybki dla ciebie? Jeśli nie, metoda brute-force łatwo zrównuje się i skaluje bezpośrednio z liczbą procesorów: wystarczy podzielić punkty między procesory, a następnie dokonać ostatecznego porównania najbliższego znalezionego przez każdy procesor.

Jeśli chcesz jechać szybciej, możesz użyć różnych przybliżeń do ekranowania punktów. Na przykład, jeśli masz szerokość między -88 a +88 stopni, a najbliższy znaleziony punkt znajduje się w odległości 200 km, to żaden punkt, którego szerokość różni się od szerokości punktu sondy o więcej niż 2 stopnie, nie może być bliżej (ponieważ gdziekolwiek na Ziemia, jeden stopień szerokości geograficznej przekracza około 110 km). W wielu przypadkach ten rodzaj wstępnej kontroli może umożliwić przetworzenie setek milionów punktów na sekundę.

Zgadzam się z innymi, że prosta pętla powinna być skuteczna dla „kilkuset miast”.

Biorąc pod uwagę twoje zastosowanie, radzenie sobie z odległościami elipsoidalnymi jest prawdopodobnie poważną przesadą - prawdopodobnie masz do czynienia z prognozami pogody, których lokalizacja nie przekracza zaledwie kilku metrów. Geometria sferyczna jest na tyle prosta, że ​​można to łatwo zrobić w pętli.

Może to być jeszcze prostsze (np. Użyj delta lat jako y i delta lon * cos (lat) jako x i znajdź minimum x ^ 2 + y ^ 2). Używasz cosinusa docelowej szerokości geograficznej, który obliczasz tylko raz. Będzie to coraz bardziej niedokładne dla odległych miast, ale i tak zostaną one odrzucone, więc nie ważne. Zakładając, że najbliższe miasto znajduje się zwykle w odległości kilkuset kilometrów, szanse na inny wynik (najbliższe miasto) przy użyciu tego vs przy użyciu dokładniejszej formuły są dość małe i wystąpiłyby tylko wtedy, gdy różnice są na tyle małe, że „która prognoza jest większa dokładne ”prawdopodobnie i tak zależeć będzie od innych czynników (tj. zagubionych w hałasie).

O ile nie korzystasz z wbudowanego systemu lub powolnego interpretera, prawdopodobnie możesz sobie pozwolić na użycie form form sferycznych, które sugerują inni.

Jest to dodatek do tego, co już powiedziano, ale pomyślałem, że zwrócę uwagę na znaczenie wyboru odpowiedniej struktury danych. Napisałem własny kod dla funkcji K w .NET i stwierdziłem, że użycie wydajnych kolekcji znacznie przyspieszyło sprawę. Niestety nie znam notacji O dla dokładnych prędkości. Użyłem dwóch słowników dla współrzędnych xiy z identyfikatorem punktu jako kluczem. Nie znam Javy, więc nie mogłem nic sugerować.

Pozdrawiam, David