Znajdowanie miast „terminalowych” na mapie

13

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).

Ionică Bizău
źródło
3
Pojęciem jest łączność, a w teorii grafów byłby reprezentowany jako liczba „krawędzi”, które ma „węzeł”. Będziesz szukał węzłów z jedną krawędzią po odfiltrowaniu krawędzi powyżej progu masy. Rzeczywiste rozwiązanie zależy od tego, z jakim narzędziem, językiem lub oprogramowaniem pracujesz.
RoperMaps,
@RoperMaps Nie mam jeszcze skonfigurowanych narzędzi, ale pytam ogólnie (i ostatecznie, czy ktoś wcześniej zbudował coś takiego). Rozszerzyłbym to, podając ocenę (o ile sposobów jest krótszy niż X tego węzła). Im wyższy wynik, tym bardziej jest połączony (i mniej terminalu ). Jeśli go zbuduję, prawdopodobnie skończę na analizie niektórych wykresów przy użyciu Node.js, ale zastanawiam się, czy ktoś inny to zrobił wcześniej. : D
Ionică Bizău,
@RoperMaps Chyba mogę do tego użyć OSM, ale uważam, że jest to niezwykle trudne (np. Istnieją sposoby łączenia węzłów, ale te węzły to tylko punkty, nie reprezentujące miast). Mogę napisać algorytm, aby znaleźć liście na wykresie lub coś nieco bardziej rozszerzonego dla mojego przypadku, ale nie jestem pewien, jak do tego użyć danych OSM (czy jest łatwiejszy sposób niż OSM?).
Ionică Bizău
z jakiego oprogramowania korzystasz? czy pracujesz na prawdziwych odległościach czy w odległościach lotu ptaka?
radouxju,
@radouxju Moim pierwszym działającym prototypem były odległości lotu ptaka (promień, oparty na współrzędnych) - znowu, to początek, ale nie tego chcę. Skrypt napisałem w Node.js i używając MongoDB. Wolę prawdziwe odległości: np. Jeśli są dwie wioski, oddzielone wzgórzem, bez dróg nad wzgórzem, to odległość między nimi będzie najkrótszą drogą łączącą je.
Ionică Bizău,

Odpowiedzi:

2

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 ...

użytkownik17260
źródło
No i jak to zrobić?
Ionică Bizău,
Możesz to zrobić w programie Modelbuilder i eksportowaniu do Pythona. ArcObjects to kolejna trasa, ale bardziej skomplikowana. Czy kiedykolwiek używałeś wcześniej Modelbuildera?
user17260,
Wybór przestrzenny z opcją „dotknięcia” może zacząć. Może zawęzić oryginalny zestaw zaznaczeń podczas odwracania zestawu zaznaczeń na te, które nie dotykają.
user17260,
Nie korzystałem z Modelbuildera. Potrzebuję odpowiedzi krok po kroku, ponieważ jest to moja pierwsza interakcja z danymi OSM. : D Bardzo trudno mi nawet znaleźć tutoriale na ten temat.
Ionică Bizău,
Wow, to duża prośba. Czy masz dostęp do licencji ArcInfo ArcMap?
user17260,
2

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 .

Mefimefi
źródło
Dzięki za to! Spróbuję wkrótce. [i] długość (liczba linków) - czy to da mi odległość w kilometrach (jeśli nie, jak mogę to zdobyć?)?
Ionică Bizău,
Aby uzyskać odległość między punktami, nie musisz zawracać sobie głowy używaniem oprogramowania innego niż QGIS. Zobacz tutaj i tutaj na przykład. Zastosowana jednostka odległości zależy od układu współrzędnych warstwy.
Mefimefi
Ponadto, jeśli chcesz uzyskać więcej informacji o narzędziach skupiających się na łączeniu krajobrazowym, możesz
rzucić
Uważam, że QGIS jest trochę wadliwy (przynajmniej na moim Macbooku), ale ostatni link jest przydatny. Sprawdzą również ich odpowiedzi. Dzięki!
Ionică Bizău
Powiązane: gis.stackexchange.com/q/266167/111144
Ionică Bizău