Znajdź punkty w pobliżu LineString w mongodbach posortowane według odległości

Question

Mam tablicę punktów reprezentujących ulicę (czarna linia) i punkty reprezentujące miejsca na mapie (czerwone punkty). Chcę znaleźć wszystkie punkty w pobliżu określonej ulicy, posortowane według odległości. Muszę również mieć możliwość określenia maksymalnej odległości (niebieskie i zielone obszary). Oto prosty przykład:

Myślałem o użyciu operatora $near ale przyjmuje tylko Point jako wejście, nie LineString.

W jaki sposób mongodb może obsłużyć tego typu zapytania?

Answer 1

Jak wspomniano, Mongo obecnie nie obsługuje niczego innego niż Point. Czy spotkałeś się z pojęciem boksera trasy? 1 To było bardzo popularne kilka lat temu w Mapach Google. Biorąc pod uwagę linię, którą narysowałeś, znajdź postoje, które znajdują się w zakresie dist(x). Dokonano tego, tworząc serię obwiedni wokół każdego punktu w linii i szukając punktów, które mieszczą się w wiadrze.

Natknąłem się na twoje pytanie po tym, jak po prostu zdałem sobie sprawę, że Mongo działa tylko z punktami, co jest rozsądne, zakładam.

Mam już kilka opcji, jak to zrobić (rozwijają się zgodnie z tym, co @mnemosyn mówi w komentarzu). Z zestawem danych, nad którym pracuję, wszystko jest po stronie klienta, więc mogłem używać routboxera, ale chciałbym go wdrożyć po stronie serwera ze względu na wydajność. Oto moje propozycje:

1. przerwa LineString dół na jego indywidualne zestawy współrzędnych i zapytania dla $near przy użyciu każdego z tych, połączyć wyniki i wyodrębnić unikalny zestaw. Istnieją algorytmy, które upraszczają złożoną linię, zmniejszając liczbę punktów, ale prosty jest łatwy do napisania.

2. wykonaj to samo jak powyżej, ale jako procedura/funkcja zapisana w bazie. Nie grałem z przechowywanymi funkcjami Mongo i nie wiem, jak dobrze pracują z kierowcami, ale może to być szybsze niż pierwsza opcja powyżej, ponieważ nie będziesz musiał wykonywać okrążeń iw zależności od maszyny, która Twoje instancje Mongo są hostowane, obliczenia mogą być szybsze o mikrosekundy.

3. Implementacja podejścia serwerowego po stronie serwera (została wykonana w PHP), a następnie użyj jednego z powyższych 2, aby znaleźć przystanki, które są $within wynikowymi ramkami ograniczającymi. Heck, ponieważ metoda routeboxer zwraca prostokąty, możliwe byłoby scalenie wszystkich tych prostokątów w jeden wielokąt obejmujący twoją trasę, i po prostu wykonaj na tym $within. (Co sugerował @mnemosyn).

4. EDIT: Myślałem o tym, ale zapomniał o tym, ale może to być możliwe do osiągnięcia niektórych z powyższych pomocą ramy agregacji.

To coś, co mam zamiar pracować nad wkrótce (mam nadzieję) będę, open-source mój wynik (i) w oparciu o który mi skończyć się z.

EDIT: muszę wspomnieć jednak, że 1 i 2 mają wadę, że jeśli masz 2 punkty w linii, które są od siebie powiedzieć 2km, a chcesz punkty, które są w zasięgu 1.8 km od twojej linii, oczywiście stracisz wszystkie punkty pomiędzy tą częścią linii. Rozwiązaniem jest wstrzykiwanie punktów na linię podczas jej upraszczania (wiem, że cel ten polega na redukcji punktów przy ponownym dodawaniu nowych).

Wadą o wartości 3 jest to, że nie zawsze będzie to dokładne, ponieważ niektóre punkty w Twoim wielokącie prawdopodobnie będą miały odległość większą od limitu, chociaż różnica nie będzie stanowić znacznego procentu limitu.

[1]google maps utils routeboxer

Answer 2

Jak powiedział Mongo na $ pobliżu działa tylko w kwestiach nie linie jako punktu środkowego jednak jeśli przerzucić przesłankę z punktów znalezisko w pobliżu linii, aby znaleźć linię pobliżu punktu następnie możesz wykorzystać swoje punkty jako centrum i linii jako cel

jest to różnica pomiędzy

foreach line find points near it 

i

foreach point find line near it 

jeśli masz dużą liczbę punktów, aby sprawdzić się może połączyć to z odpowiedzią nevi_me by zmniejszyć listę punktów, które wymagają sprawdzania w znacznie mniejszym podzbioru