Znaleźć najbliższy punkt do danego punktu

Question

Szukałem w tym wszystkim, ale nie mogę znaleźć najlepszego sposobu na to. Mam około 22000 lat/lon punktów i chcę znaleźć najbliższy do aktualnej lokalizacji iPhone'a. Widziałem ludzi pytających o Quad Trees, algorytm Dijkstry i przestrzenne bazy danych. Który jest najlepszy dla iPhone'a? Bazy danych przestrzennej wydają się najłatwiejsze, ale nie jestem pewien.

EDYCJA: w rzeczywistości jest ponad 20 000 punktów. Myślisz, że powtarzanie przez nich wszystkich jest sposobem na zrobienie tego? Ale dzięki za twój wkład.

Dzięki.

Answer 1

Właściwie najlepiej jest użyć obliczenia Haversine (wielkie koło) dla punktów długości/długości, w przeciwnym razie coraz większe odległości będą błędne, szczególnie jeśli użyjesz prostego triggera, takiego jak w Jherico's answer.

Szybkie wyszukiwanie udostępnia ten przykład javascript:

var R = 6371; // km Radius of earth 
var dLat = (lat2-lat1).toRad(); 
var dLon = (lon2-lon1).toRad(); 
var a = Math.sin(dLat/2) * Math.sin(dLat/2) + 
     Math.cos(lat1.toRad()) * Math.cos(lat2.toRad()) * 
     Math.sin(dLon/2) * Math.sin(dLon/2); 
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
var d = R * c; 

Pod względem datastructure, Geohash warto przyjrzeć.

Answer 2

Jak jesteś na iPhone, można użyć CoreLoaction wykonać dystans geograficzny - używając CLLocation na – getDistanceFrom:

byłbym skłonny do korzystania z brute szukanie siły liniowej choć wszystkie 2k punktów NAD, jeśli nie jest to szybko wystarczy przełączyć się na coś takiego jak GeoHash, aby przechowywać dane meta względem twoich punktów do wyszukiwania.

Answer 3

Jeśli potrzebujesz czegoś lepszego niż O (N), możesz go zdobyć tylko, jeśli najpierw zapłacisz Ng N za zbudowanie jakiegoś spacji przestrzennej (kwadratu, ósemki, siatki siatki lub podobnego). Wtedy każdy test będzie w przybliżeniu O (lg N) i może być znacznie lepszy, zwykle poprzez cachowanie ostatniej sprawdzonej lokalizacji, jeśli jest dużo spójności (ogólnie rzecz biorąc, istnieje).

Prawdopodobnie zbudowałbym ósemkę w przestrzeni Eulera (geocentryczne, XYZ), ponieważ pozwala mi to uzyskać "prawdziwą" odległość, a nie "zniekształconą" odległość lat/lon. Jednak w praktyce drzewo quad w przestrzeni lat/lon prawdopodobnie będzie działać wystarczająco dobrze. Po trafieniu trzymasz się tego węzła drzewa (zakładając, że drzewo nie zostanie ponownie zbudowane w środowisku wykonawczym), a następne zapytanie rozpocznie się od tego węzła drzewa i będzie tylko martwić się o węzły, które mogą być bliższe, jeśli poprzedni punkt oddalił się od poprzedniej odpowiedzi.

Answer 4

Dlaczego nie rozmieścić globusa w regionach? (Zastanów się.) Następnie, dodając punkty do listy lub w jednej dużej pętli przetwarzania wstępnego dla każdego punktu, zapisz region, w którym się znajduje.

Następnie, szukając punktów w pobliżu punktu A w heksie X, wystarczy sprawdzić punkty w heksie X i maksymalnie 3 sąsiednich heksach.

Jeśli nadal jest zbyt wiele punktów do sprawdzenia, dodaj podregiony.

Answer 5

myślę, że ten algorytm działa:

Utwórz tablicę posortowanych według szerokości utworzyć tablicę klasyfikowane według długości

Aby znaleźć najbliższy najpierw odnaleźć najbliżej od szerokości geograficznej przez robi binarne wyszukiwanie w szerokość geograficzna. Wykonaj to samo dla tablicy długości. Teraz masz 2 punkty, jeden najbliżej szerokości geograficznej, drugi najbliżej długości geograficznej. Obliczyć odległości do każdego punktu za pomocą twierdzenia Pitagorasa. Najbliższy punkt wygrywa.

Roger

Answer 6

należy wziąć pod uwagę, że aby korzystać z Dijkstra trzeba znać swoją pozycję węzła na wykresie, to zamiast problem starasz się rozwiązać; nie jesteś na wykresie, ale chcesz wiedzieć najbliższy punkt dla ciebie

tak po prostu, jak już mówiłem Chaos, należy obliczyć wszystkie dystanse beetween swoją pozycję i wszystkie 20.000 punktów, a następnie posortować je