Znajdowanie miast „terminalowych” na mapie

Chcę znaleźć wioski / miasta, które są końcami . To znaczy: potrzebuję tych wiosek, które są połączone z maksymalnie jedną wioską w odległości X km.

Zastanawiam się tylko, jak nazywa się ten algorytm (chyba ktoś wcześniej stworzył coś podobnego).

Czy jest na to narzędzie? Jak nazywa się ta koncepcja?

Na przykład

 City ------------ Village 1 ------- Village 2 ------ Village 3 - - - [ Mountain]
                    \                 \                                \
                     Village 4         |                                Road
                     |                  \                            in mountains
                     Village 5----------Village6---------Village7 - - - - -  

Tak długo, jak Droga w górach jest dłuższa niż Xkm Village 3i Village 7byłaby rozważana przeze mnie jako terminal , ponieważ są one połączone z jedną wioską (odpowiednio V2, V6).

W przeciwnym razie będę chciał zbudować taki z otwartymi danymi, które mamy.

Co próbowałem :

Pobieranie danych OSM dla mojego kraju (Rumunia) i importowanie wiosek i miast do bazy danych. Korzystając z funkcji geolokalizacji z bazy danych, mogę znaleźć wioski, które nie mają więcej niż X wiosek w promieniu R km.

Nie jest to jednak rozwiązanie w moim przypadku, ponieważ w moich przypadkach wioska może znajdować się po drugiej stronie góry, jak w powyższym przykładzie, ale nie ma na to dobrej drogi (lub żadnej drogi).

Wydaje mi się, że musisz przejść przez geometrię linii, wyszukując współrzędne dla każdego bufora punktu końcowego / końcowego, który wybiera geometrię linii (z twoich dróg fc), jeśli zwrócisz tylko jedną cechę, to jej punkt końcowy / końcowy, jeśli więcej niż jeden nie jest i zapętlić. Mam nadzieję, że to ma sens ...

Możesz to osiągnąć za pomocą QGIS i oprogramowania początkowo przeznaczonego do obliczania połączeń krajobrazowych, takich jak Graphab lub Conefor . Na przykład :

• Zaimportuj dane OSM do QGIS, przeciągając i upuszczając je lub używając wtyczki OpenStreetMap.
• Zapisz dane jako kształt (kliknij prawym przyciskiem myszy)
• Użyj wtyczki Conefor do wygenerowania plików węzłów i połączeń, jak wyjaśniono tutaj
• Oblicz ważność każdego węzła i łącza za pomocą Conefor. „Węzeł końcowy” nie będzie ważny dla łączności. Myślę, że można użyć metryki BC (IIC), ponieważ bierze ona pod uwagę „liczbę najkrótszych ścieżek między wszystkimi parami łatek przechodzących przez określony węzeł (...) [i] długość (liczbę linków) ścieżki między łatami, w które zaangażowany jest dany węzeł ” (patrz tutaj )

Nie byłem w stanie tego przetestować - niestety nie mam teraz wystarczająco dużo czasu. Ale myślę, że to może zadziałać, jeśli jesteś otwarty na trochę drobnych poprawek. Na przykład prawdopodobnie będziesz musiał usunąć łącza łączące dwa węzły znajdujące się po każdej stronie przeszkody (góra itp.), Ręcznie (jeśli nie jest ich zbyt wiele) lub za pomocą funkcji geoprzetwarzania i kształtu zawierającego przeszkody .