# Finding "terminal" cities on the map

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]
\                 \                                \
|                  \                            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. Dec 14, 2017 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 Dec 14, 2017 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?). Dec 16, 2017 at 16:12
• what software are you using ? do you work in real distances or in bird flight distances ? Dec 18, 2017 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. Dec 18, 2017 at 15:51

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

• Well, and how to do that? Dec 19, 2017 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? Dec 19, 2017 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. Dec 19, 2017 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. Dec 19, 2017 at 16:27
• Wow, that's a big request. Do you have access to ArcInfo license of ArcMap? Dec 19, 2017 at 16:28

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.

• 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?)? Dec 20, 2017 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. Dec 21, 2017 at 8:32
• Also, if you want more infos on tools focusing on landscape connectivity, you may want to have a look at this Researchgate discussion Dec 21, 2017 at 8: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! Dec 21, 2017 at 19:22
• Dec 22, 2017 at 14:10