Finding "terminal" cities on the map

Question

I want to find villages/cities which are ends. That means: I need this villages which are linked to maximum one village on a distance of X km.

I'm just wondering how is this algorithm is called (I guess someone created something similar before).

Is there a tool for this? How is this concept called?

E.g.

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

As long the Road in mountains is longer than Xkm, Village 3 and Village 7 would be considered by me terminal, because they are linked to one village (V2, respectively V6).

Otherwise, I will want to build one with the open data we have.

What I've tried:

Downloading the OSM data for my country (Romania) and importing the villages and cities into the database. Using the geolocation functions from the database I'm able to find the villages which do not have more than X villages in the radius of R km.

However this is not a solution for my case because in my cases a village may be on the other side of the mountain, like in the example above, but there is no good way to it (or no way at all).

The concept is connectivity, and in graph theory would be represented as the number of 'edges' a 'node' has. You wuold be looking for nodes with one edge after you filtered out edges above your weight threshold. An actual solution would depend one what tools, language or software you're working with. — RoperMaps, Dec 14 '17 at 10:31
@RoperMaps I don't have any tools set up yet, but asking in general (and eventually, if somebody built something like this before). I would extend this, giving a score (how many ways shorter than X that node has). The greater the score, the more connected (and less terminal) it is. If I'd build it, probably I will end up by parsing some graphs using Node.js, but just wondering if someone else did it before. :D — Ionică Bizău, Dec 14 '17 at 10:33
@RoperMaps I guess I can use OSM for this, but I find it extremely difficult (e.g. there are ways connecting nodes, but these nodes are just points, not representing cities). I can write an algorithm to find the leafs in a graph or something a bit more extended for my case, but I'm not sure how to use the OSM data for this (or is there an easier way than OSM?). — Ionică Bizău, Dec 16 '17 at 16:12
what software are you using ? do you work in real distances or in bird flight distances ? — radouxju, Dec 18 '17 at 11:10
@radouxju My first working prototype was bird flight distances (radius, based on coordinates)–again, that's a start, but it's not what I want. I wrote my script in Node.js and using MongoDB. I prefer real distances: e.g. if there are two villages, separated by a hill, with no roads over the hill, then the distance between them will be the shortest road connecting them. — Ionică Bizău, Dec 18 '17 at 15:51

score 2 · Answer 1 · answered Dec 19 '17 at 14:39

2

It would appear to me that you need to step through the line geometry retrieving the coordinates for each end/terminal point buffer it select line geometry (from your roads fc) if you return only one feature its an end/terminal point, if more than one it is not and loop through. Hope this makes sense...

answered Dec 19 '17 at 14:39

user17260

106
4

Well, and how to do that? – Ionică Bizău Dec 19 '17 at 15:28
You may be able to do it with Modelbuilder and exporting to Python. ArcObjects is another route but more complicated. HAve you ever used Modelbuilder before? – user17260 Dec 19 '17 at 16:02
A spatial selection with the "touches" option might get you started. May narrow down original selection set when you invert the selection set to those that do not touch. – user17260 Dec 19 '17 at 16:18
I didn't use Modelbuilder. I need a step by step answer, because it's my first interaction with OSM data. :D It's very hard for me to even find tutorials about it. – Ionică Bizău Dec 19 '17 at 16:27
Wow, that's a big request. Do you have access to ArcInfo license of ArcMap? – user17260 Dec 19 '17 at 16:28
Yes, hence the bounty. :) I would prefer using open software... – Ionică Bizău Dec 20 '17 at 02:15
Unfortunately, I can only give you basic information there. – user17260 Dec 20 '17 at 14:24

Mefimefi · Answer 2 · 2017-12-20T14:45:45.820

2

You might be able to achieve this by using QGIS and a software initially aimed at calculating landscape connectivity like Graphab or Conefor. For example :

Import your OSM data into QGIS, either by drag and dropping it or by using the OpenStreetMap plugin.
Save your data as a shape (right-click)
Use the Conefor plugin to generate the nodes and connections files, as explained here
Calculate the importance of each node and link using Conefor. An "end node" will not be important for connectivity. I think you could use the BC(IIC) metric because it takes into account "the number of shortest paths between all pair of patches that go through a particular node (...) [and] the length (number of links) of the paths between patches in which a particular node is involved" (see here)

I haven't been able to test this - I unfortunately don't have enough time right now. But I think that it could work, if you're open to a little bit of tweaking. For example, you'll probably have to remove the links connecting two nodes that are on each side of an obstacle (mountain etc), either manually (if they aren't too many) or by using geoproccesing functions and a shape containing your obstacles.

edited Dec 20 '17 at 14:45

answered Dec 20 '17 at 14:28

Mefimefi

586
1
6
19

Thanks for this! Will try it soon. [and] the length (number of links) — will that give me the distance in kilometres (if not, how can I get that?)? – Ionică Bizău Dec 20 '17 at 17:11
To get the distance between points, you don't have to bother using any software other than QGIS. See here and here for example. The distance unit used depends on the layer coordinate system. – Mefimefi Dec 21 '17 at 08:32
Also, if you want more infos on tools focusing on landscape connectivity, you may want to have a look at this Researchgate discussion – Mefimefi Dec 21 '17 at 08:34
I found QGIS a bit buggy (at least on my macbook), but the last link is useful. Will check their answers as well. Thanks! – Ionică Bizău Dec 21 '17 at 19:22
Related: https://gis.stackexchange.com/q/266167/111144 – Ionică Bizău Dec 22 '17 at 14:10
Save your data as a shape (right-click) –– Nothing happens when I right click... – Ionică Bizău Dec 22 '17 at 14:19
Whoups, gived the bounty to the wrong answer... I wanted to give it to you, lol. Anyhow, both answers helped, but none of them are complete. I'd like to open another bounty, if I had the guarantee to have a step-by-step solution... – Ionică Bizău Dec 24 '17 at 18:44

Finding "terminal" cities on the map

2 Answers2

Linked