Cześć, piszę teraz hobbystyczny projekt, backend w Springu, a frontend na Androidzie.
Głównie w backendzie, ale też w Androidzie będę trzymał dane o dużej ilości miejsc, każde miejsce będzie przechowywało informacje o współrzędnych geolokalizacyjnych.
Jak napisać algorytm by zwracać listę n najbliżych miejsc od podanych współrzędnych? Znacie może jakiś algorytm lub opracowanie podobnego problemu?
Gdybyś podzielił miejsca(punkty) na kubeczki to sprawdzając tylko aktualny kubeczek i jego sąsiadów a wyniki zapisując do kopca, a trzymał byś racjonalnym nakładem pracy posortowane wszystkie punkty, w promieniu r = miedzy 1 a 1,5 *rozmiarBokuKubeczka (zależy wktórym miescu kubeczka jestes). Ps. nie licz odległości w twierdzenia pitagorasa bo tak jakby prowdzić tunel przez środek ziemi.
Do tego zazwyczaj używa się drzewa R: https://en.wikipedia.org/wiki/R-tree
topik92: dzięki za podpowiedź, pomysł z kubeczkami całkiem niezły. Wadą tego rozwiązania, który widzę w tej chwili będzie kłopot z paginacją kolejnych wyników. Będzie mi dosyć trudno zwracać kolejne najbliższe 50 miejsc z API, za każdym razem bym musiał uwzględniać więcej sąsiadów, a później wykluczać wcześniejsze wyniki.
Afish: Drzewo R to też fajny pomysł, umożliwia łatwą paginację kolejnych wyników, tylko trochę się obawiam, że będzie zwracało mi wynik przybliżony, a nie idealnie posortowane punkty w stosunku co do najbliższego dystansu.
Wczytuję się w temat, chętnie usłyszę więcej podpowiedzi.
No ale co za problem? Wyciągasz punkty z jakiegoś sensownego dystansu (ulica/dzielnica/miasto/10 kilometrów), potem sortujesz i zwracasz tylko te najbliższe spełniające warunki.
To na tym przykładzie: https://en.wikipedia.org/wiki/File:R-tree.svg
Załóżmy, że wyszukujemy po współrzędnej w dolnym prawym rogu R8 z stronicowaniem do 3 elementów. Zacznę przeszukiwać drzewo, trafię do węzła R3. Akurat ma 3 dzieci więc super zwracam. Pierwsza zwrotka przyjdzie mi z węzła R3 czyli: R8, R9, R10. A powinno zwrócić R8, R10, R12 bo to były najbliższe prostokąty od punktu. Dlatego jakaś niedokładność będzie. Oczywiście posortuję później ten mniejszy zbiór, ale szkoda, że w pesymistycznych przypadkach jest ta granica błędu.
Bierzesz dolny prawy róg R8, traktujesz go jako środek prostokąta A o wymiarach 20 kilometrów na 10 kilometrów. Znajdujesz wszystkie prostokąty X przecinające się z prostokątem A. Następnie sprowadzasz każdy prostokąt X do punktu (środek ciężkości czy cokolwiek tam chcesz, restauracja na mapie i tak może być traktowana jako punkt), sortujesz po odległości od rogu R8 i zwracasz n najbliższych.
Masz rację, załóżmy, że w ten sposób uzyskałem 1000 miejsc. Będę musiał trzymać tą listę w pamięci przez jakiś czas, tak by pozwolić urządzeniom mobilnym zaciągać ją powoli. Chciałbym tego uniknąć, bo to by oznaczało, że na jednego usera będzie program dużo mielił. A w takim wypadku mógłbym od razu wszystkie miejsca przetwarzać i trzymać listę w pamięci.
Tylko mi chodzi o coś skalowalnego w czasie, z kolejnymi krokami zaciągania kolejnych stron najbliższych miejsc. Z pomocą drzewa R jest to do zrobienia tylko nie dokładne. Wyjaśniłem wyżej czemu, a to inne podejście co opisałeś sprowadza się do kubeczków wspomnianych przez topik92. Też dobre, ale nie jestem przekonany czy do RestAPI.
Tworzysz kubeczki o dowolnych zadowalających Cie rozmiarach tak żeby się nie zazębiały przechowujesz je w zmodyfikowanje hasz tablicy z pointem jako kluczek, tablica ma działać tak by zwracać Ci kubeczek w wnętrzu którego leży ten punkt. Piszesz funkcje która dla wybranego punktu "kreśli" okręgi (wybiera punkty na średnicy) o coraz to większych promieniach. te pukty to współdłużne kubeczka do sprawdzenia. Liczysz dla każdego ptk w kubku odległość zapisujesz do zmodyfikowanego kopca który, przechowuje zawsze tylko określoną ilość elementów. gdy Ci się ten kopiec zapełni możesz przerwać szukanie po przeleceniu aktualnego promienia do końca, kazdy punkt o większym promieniu siła rzeczy będzie dalej. będziesz potrzebował skończoną znaną z góry ilość pamięci na użytkownik. Może da rade to za implementować sensownie.
Ostatnio/Aktualnie wczytane kubki można przechowywać w wspólnej strukturze danych, najpierw sprawdzasz czy masz już wczytany ten kubeczek, jesli nie to wczytujesz i przeliczasz. Samo to plus zmodyfikowany kopiec powinno dużo zasobów oszczedzić.
Moze da rade zrobić to tak że dzielisz metodą dziel i zwyciężaj, na cześci o coraz większej rodzielczości, np połowa ziemi jedna czwarta jedna ósma, szesnasta itd. Dla każdej takiej sekcji przechowujesz ilość ptk wewnątrz, tak długo i zmienisz średnice swojeko kólka(zwiekszasz rozdzielczość) aż ilosć ptk w środku będzie będzie najbliższa to szukanej wartości(metodą biskcji broń boze liniowo), bierzesz pierścień o jeden rozmiar większy(bład kwantowania) i filtrujesz zewnętrzną krawędź aż będzie Ci się zgadzać liczba punktów. Punktu głębiej przepisujesz w ciemno
MAM!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
To samo w druga stronę kreślisz coraz większe koła po kubeczkach nie czytasz ich tylko ich rozmiar aż n wyniesię tyle ile trzeba domykasz pierścień i sprawdzasz zewnętrzna krawędz :D. Łatwe w implementacji :)
W sumie to teraz to nie są kubki z ptk tylko mapa gęstości ptk, jeśli napiszesz takich map kilka o coraz mniejszej rozdzielczości to będziesz miał gęstość uśrednioną, a to pozwoli Ci zgadnąć wymiary koła bez kreślenia kółek :D W sumie to przed ostatnia metoda ale forma wydaje się bardzie przystępna.
jeśli będziesz współdzielił dane miedzy userami to wyjdzie elegancko :D.
Jakbyś napisał osobne metody dal małych dancyh, i nie zależnie wysyłał środek i obliczał zewnetrzny promień to by byla bajka :D
A jeśli gdzieś sensownie spamiętasz skuteczność trafień, pudło jest kosztowne, to po będziesz mógł z optymalizować swój algorytm, i bedzie śmigal szybciej :D
Jej, dzięki topik92 :D Naprawdę podoba mi się tutaj pomysł dziel i rządź do wyboru średnicy koła oraz zastosowanie map o różnych rozdzielczościach. Przy czym każdy kafelek takiej mapy sprowadziłbym do punktu ciężkości tak jak wspominał Afish z prostokątami. I tak miałbym ilość miejsc na kafelek, a sprawdzenie czy kafelek się zawiera w kole za pomocą sprawdzenia czy punkt ciężkości został złapany. Za pomocą używania map z większą lub mniejszą rozdzielczością mógłbym optymalizować wyszukiwanie bez straty dokładności. Gęstość uśredniona mogłaby mi pomóc w wyborze rozdzielczości mapy adekwatnej do limitu wyszukiwań :)
W sumie z drzewa R miałbym także mapę gęstości, tylko położenie punktów gęstości byłoby nierównomiernie ułożone, obliczanie drzewa jest ciut kosztowne, ale za to każdy punkt miałby równą ilość miejsc. Myślę, że równomiernie położone punkty gęstości będą mimo wszystko lepsze.
Jeszcze tematu nie zamykam, bo jeszcze będę myślał nad tematem. Jeśli ktoś ma jakiś fajny pomysł jeszcze to byłbym wdzięczny.
Gdyby zamiast "kwadratów" zastosować kubeczki w kształcie trójkątów równo ramiennych i to zamiast to kólek mozna by szukać za pomocą 6-katów foremnych one lepiej się do tego nadają niż kwadraty http://www.matematykam.pl/images/l17e10.jpg, problem jest taki że ziemia nie jest płaska i przy za duzych rozmiarach to nie bedą 6katy i nie wiem czy to będzie sie dobrze skalować ;/
