Chciałbym zbudować aplikację, która da ci najbliższą restaurację w zależności od Twojej lokalizacji. Będziemy mieć bazę danych ze wszystkimi punktami POI odpowiadającymi restauracji, a my dostaniemy Twoją lokalizację z GPSem twojego telefonu ...Jaki jest dobry algorytm dla problemu najbliższego sąsiada w dwóch wymiarach?
Jaki algorytm będzie odpowiedni? Gdzie mogę znaleźć dobrego doktora na ten temat?
Dzięki
Oto prezentacja informacyjny: http://dimacs.rutgers.edu/Workshops/MiningTutorial/pindyk-slides.ppt
bym albo użyć Quadtree lub Kd-tree.
Zobacz niektóre testy porównawcze tutaj: http://www.flegg.net/brett/pubs/spatial/index.html. Wszystko zależy od rozmiaru i zasięgu danych.
Głównym problemem jest przechowywanie i wyszukiwanie danych. Jeśli używasz bazy danych SQL, która nie obsługuje indeksów przestrzennych (powiedzmy SQLite na Androidzie), rozważ konwersję danych przestrzennych na krzywą liniową Z-order. Algorytm jest prosty, wiem o (dobrze, napisałem) implementacji this.
To świetny kod Thomas, chapeau! –
Wykonywanie zapytań dotyczących najbliższego sąsiada na dużej bazie danych nie wydaje się być dobrą rzeczą do zrobienia bezpośrednio na Androidzie. Serwer bazy danych jest po to, aby w pierwszej kolejności wykonać takie podnoszenie ciężarów. –
@Tim Zgadzam się Z-order nie jest tak wspaniały dla dużej bazy danych. Przy okazji, od czasu mojej odpowiedzi w 2010 r., Zaimplementowałem [R-Tree] (http://h2database.com/html/mvstore.html#r_tree), które powinno umożliwić wydajne zapytania najbliższego sąsiada (po zaimplementowaniu) i powinien również działać na Androidzie. Ale nie korzysta z SQLite. –