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?


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

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

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

  • Well, and how to do that? Commented 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?
    – user17260
    Commented 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.
    – user17260
    Commented 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. Commented Dec 19, 2017 at 16:27
  • Wow, that's a big request. Do you have access to ArcInfo license of ArcMap?
    – user17260
    Commented 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?)? Commented 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.
    – Mefimefi
    Commented 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
    – Mefimefi
    Commented 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! Commented Dec 21, 2017 at 19:22
  • Related: gis.stackexchange.com/q/266167/111144 Commented Dec 22, 2017 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.