Znajdowanie podobnych ścieżek mapy

Szukam algorytmu, który po podaniu określonej trasy na mapie z atrybutami takimi jak pochylenie / odległość / kształt / itp. Może znaleźć trasę podobną (pod względem atrybutów), ale rozpoczynającą się w innym punkcie lub w innym regionie na świecie.

Oczywiście prawie we wszystkich przypadkach niemożliwe będzie znalezienie idealnego dopasowania, ale szukam systemu „najlepiej dopasowanego” z metodą pomiaru podobieństwa również idealnie.

Próbowałem szukać, ale większość moich zapytań dotyczy problemów z dopasowaniem mapy lub podobieństwa tras dla punktów GPS na tej samej ścieżce. Mogę nie znać poprawnej terminologii! Czy istnieje nazwa tego problemu? Jakiego algorytmu mogę użyć do rozwiązania tego?

Dopasowywanie map różni się od tego, czego szukasz. Dopasowywanie map to właściwy sposób dopasowania obserwacji GPS błędu do liniowej sieci ulicznej. Twoje pytanie nie ma też nic wspólnego z punktami GPS. Ponieważ chcesz porównać wzór tras statycznych (nieczasowych) i znaleźć podobne. To, czego szukasz, to dopasowanie cech liniowych (w sensie GIS, a nie uczenia maszynowego) . Literatura związana ze śladem GPS dotyczy dopasowywania wzorców przestrzenno-czasowych, które znajdują się w rubryce „Eksploracja wzorców trajektorii (czasowo przestrzennych)”.

Aby uzyskać więcej informacji, zapoznaj się z rozdziałem (Trajektory Pattern Mining) z książki „ obliczanie trajektorii przestrzennej ”. Dostaniesz wiele pomysłów na porównanie i kontrast (np. Przez azymut, długość segmentów, falistość, linie itp.) Różnych tras lub trajektorii.

Twoje pytanie oparte jest na danych wektorowych. Sądzę jednak, że lepiej jest ci przy konwersji pytania na analizę rastrową. W ten sposób do pewnego stopnia uogólnisz swoje pytanie.

Algorytm rozwiązania twojego pytania wyglądałby następująco:

1. Rasteryzuj oryginalną trasę i spraw, aby każda komórka przenosiła parametry zgodnie ze specyfikacjami (nachylenie / odległość / kształt / itp.). Obecność drogi jest również parametrem. Staje się to jednowymiarową listą z n obiektami -> lista zadań (n)

2. Znajdź obszar testowy, w którym wiesz, że jest co najmniej jedna replika oryginalnej trasy. Rasteryzuj ten obszar z tymi samymi parametrami, co oryginalna trasa. To jest raster a.

3. Zacznij od komórki 1,1 w rastrze a i poruszaj się po całym rastrze w uporządkowany sposób.
4. Dla każdej komórki wywoływana jest funkcja. Ta funkcja sprawdza, czy komórka odpowiada liście zadań (0), jeśli tak, to samo sprawdzenie odbywa się na otaczających komórkach. Po sukcesie funkcja przechodzi do sprawdzania komórki pod kątem listy routingu (1) i tak dalej. W przypadku pomyślnego przejścia do listy tras (n) współrzędne są zapisywane jako alternatywna trasa w liście tras (n)
5. Powtarzaj, aż dojdziesz do ostatniego piksela w rastrze.

Powyżej zobaczysz trzy opcje tras zgodnie z parametrami w liście tras.

Ponadto:

• Próbki rastrów powyżej są mierzone według tylko jednego parametru. W prawdziwym wyzwaniu jeden piksel będzie kombinacją kilku parametrów.
• Gdybym miał to zadanie, spróbowałbym napisać funkcję wymienioną powyżej w sposób rekurencyjny. Byłoby to bardziej wydajne i rozwiązałoby problem „rozbieżnych ścieżek” - gdzie masz kilka alternatywnych ścieżek o tym samym punkcie początkowym.
• Zakręty trasy nie są uważane za problem. Oznacza to, że odpowiedzi to lista pikseli połączonych w tej samej kolejności, co oryginalna trasa. Zakręty i zakręty nie stanowią problemu. Być może będziesz musiał napisać algorytm, aby trasy przecinające się nie były częścią rozwiązania.
• Zaprojektuj algorytm, abyś mógł ustawić różne poziomy tolerancji dla kryteriów w grze. Zapewni to większą elastyczność.
• W ustawieniu operacyjnym cały proces można usprawnić, sprawdzając obszar pod kątem występowania pikseli zgodnie ze specyfikacją. Jeśli ich nie ma, obszar badania jest negatywny, więc nie ma powodu, aby tracić czas na analizę tego obszaru.