sortowanie danych geograficznych do szybkiego wyszukiwania

Question

Mam kilka obiektów, które są geolokalizowane (mam dla każdego obiektu szerokość + długość geograficzna). Moja aplikacja musi wyświetlać obiekty w odległości 3 kilometrów od pozycji GPS urządzenia przenośnego. Mam kilka tysięcy obiektów i są one zlokalizowane na dużym obszarze (na przykład kilka stanów USA, kilka małych krajów), co oznacza, że ​​na mojej liście obiektów mogę znajdować się w Nowym Jorku, a inne w Miami, ale mogę też mieć obiekty, które są bardzo blisko (kilka metrów).

Obecnie moja aplikacja wykonuje wyszukiwanie iteracyjne. Dla każdego obiektu obliczam odległość z położeniem GPS, a jeśli odległość wynosi < = 3KM, to zatrzymuję obiekt, który go zignorowałam. Ten algorytm nie jest bardzo wydajny i szukam algorytmu, który zapewni lepszą wydajność.

Przypuszczam, że istnieje sposób sortowania obiektów za pomocą funkcji geo coord, a następnie szybsze znajdowanie obiektów znajdujących się w pobliżu pozycji GPS.

Mój obecny pomysł polega na obliczeniu prostokąta z "skrajnymi punktami", Północ/Południe/Wschód/Zachód (z 3 km od pozycji GPS), aby ograniczyć strefę wyszukiwania. Następnie obliczę odległość tylko dla obiektów znajdujących się w tym polu. myślę, że coś można zrobić lepiej, ale ja nie mam pojęcia ...

Każda propozycja zostanie doceniona ;-) Dzięki,

SEB.

Answer 1

Brzmi jak nearest neighbor search, ale nie z maksymalną liczby sąsiadów (jak w KNN), ale o maksymalnej odległości progu.

Wspólnym podejściem jest umieszczenie obiektów w specjalnej strukturze danych, aby umożliwić szybkie wykluczenie dużych części przestrzeni poszukiwań. Jednak są one zwykle robione z myślą o przestrzeniach euklidesowych, a nie dla sferycznej (lat/lon-) płaszczyzny (problemy zwijane). Dlatego, że prawdopodobnie trzeba konwertować do 3D współrzędnych współrzędne w kartezjańskim układzie w stosunku do środka sfery, zanim będzie można zastosować jedną z następujących struktur danych, aby skutecznie szukać swoich obiektów:

• Octree
• kd-tree

Answer 2

innych odpowiedzi przywołujące indeksy przestrzenne są poprawne, ale niekoniecznie najprostszym rozwiązaniem dla Ciebie.

Chciałbym rozważyć coś prostszego: Grupuj elementy według krajów, a następnie według stanu, regionu, miasta, a na końcu - przez kilka punktów orientacyjnych w gęstych miastach (gdzie masz dużo obiektów o).

Następnie wystarczy wykonać kilka zapytań (sprawdź, w jakim kraju się znajdujesz, w jakim stanie, regionie itp.), Aby ograniczyć się do bardzo małego zestawu obiektów, bez wprowadzania zaawansowanych struktur danych w aplikacji mobilnej .

Answer 3

Jednym ze sposobów wykonania tej czynności bez specjalistycznej bazy danych wydaje się sortowanie dwóch kopii danych - raz po długości geograficznej, raz po szerokości geograficznej. Wszystko, co binarnie wyszukuje, aby zamknąć zarówno na długie jak i długie, jest blisko.

Podobnie można użyć zwykłego drzewa (szybkie) lub czerwono-czarne (mała zmienność).

Ale prawdopodobnie istnieją zalety korzystania z drzewa r-tree lub kd-tree. To, co opisałem, jest prawdopodobnie tylko po to, by unikać podejmowania nowych zależności lub unikania kodowania nowej struktury danych od zera.