5

I have polygon layer which looks like this (here is small cutout): Original layer

What I need is to connect all polygons with line in somehow "logical" order - it means to go from first to last polygon (eventually point as I can create centroids) and create line connecting two nearest polygons BUT with one condition - there can't be closed polygon (it means I can't draw lines between three points so they create triangle) and there can be several branches - to make it clear below is the image how it should looks like.

What I get so far:

  • in QGIS I can't use Points to Path as I have no order field (all the polygons has same ID = 1)
  • in ArcMap I am able to use two function Generate Near Table and then XY to Line which connects at least some polygons together --> enter image description here
  • finally I need to manually draw lines for the rest --> enter image description here

Is there any automatic way to solve this using QGIS?

Maybe adding order field to layer with values based on location or something like that. I would ideally create an automatic model in the end as I deal with lots of these layers.

Improve this question
5
  • 4
    A set of connections between objects in maths is known as a "graph", and a graph without triangles (or other loops) is a "tree". I think you are trying to create a "minimum spanning tree" based on the polygon distances as weights. This might help you look for algorithms or code.
    – Spacedman
    Commented Jul 22, 2020 at 6:44
  • Do you only need the lines as a visual output or do you need the lines to have attributes that tell you which polygons they come from? In other words is this purely visual or are you going to be doing any analysis with the connections?
    – Spacedman
    Commented Jul 22, 2020 at 6:46
  • @Spacedman thanks it could help - actually I need to work with it further, so it should be separate line, eventually polygon layer
    – daky
    Commented Jul 22, 2020 at 7:08
  • Search MST tool for arcgis by Paterson it will solve 1st part.
    – FelixIP
    Commented Jul 22, 2020 at 7:48
  • 1
    If you wish to also ask how to do this in ArcGIS Desktop then please do that in a separate question.
    – PolyGeo ♦
    Commented Jul 22, 2020 at 9:35

1 Answer 1

Reset to default
7

There's a Minimum Spanning Tree plugin for QGIS:

enter image description here

If you don't see it in the plugins system make sure you have the settings to show experimental plugins.

Start it from the Plugins menu and the "Minimum Spanning Tree" entry. Using the "Automatic" tab:

enter image description here

I set a simple polygon layer as the "Vector Layer" and got out a line shapefile.

enter image description here

It seems to use the centroids of the polygons for the distance ("weight") algorithm rather than the distance of nearest approach between polygons. The lines connect centroids.

The attribute table of the lines doesn't show what polygons each line comes from so you may have to do some more overlaying and intersection to get that. First use "Extract Vertices" to get two points for each line connection, and then use "Intersection" of those points over the polygons to get another point layer with the attributes of the polygon at each point. I get this:

enter image description here

that tells me that the line with id=0 connects the polygon with i equal to 9 to the one with i equal to 12. The next line, with id=1, connect polygon 9 to polygon 6, and so on for the complete tree.

Note it only seems to work on Shapefiles rather than loaded layers. Its also "experimental" and I managed to break it once or twice. I don't understand the difference between the "Vector" and the "Automatic" tab sections, for example, but the "Automatic" one seemed to work for my simple case. Hmm the "Vector" tab says the input "must be linestring" so I'm not sure what that is doing. For polygons, "Automatic" does the job.

The MST plugin doesn't seem to expose itself as a Processing algorithm so you won't be able to build all this into a single Processing step. Perhaps worth suggesting as an enhancement on their github code page.

There's an article here: https://www.sciencedirect.com/science/article/pii/S2352711020301771

Improve this answer
6
  • 1
    It looks promising, thank you, but when I try to use it (from the Automatic tab, exactly as you do), I got Python error - TypeError: 'NoneType' object is not iterable. Actually I don't know what does it mean and where is the problem.
    – daky
    Commented Jul 22, 2020 at 11:53
  • That could be a bug in the plugin's Python code, or possibly an incompatibility of the code with the version of QGIS (unlikely but maybe). Can you share your shapefile?
    – Spacedman
    Commented Jul 22, 2020 at 12:36
  • Actually I tried it on three different versions of QGIS always with the same result. When I tried to draw manually few polygons as you also did and then use the plugin, it worked after while, but when I use it on this "bigger" file, there is always the same Python error. Of course I can share it, here is a link for WeTransfer: we.tl/t-fEquWLaDZ9 .
    – daky
    Commented Jul 22, 2020 at 12:56
  • if I convert your shapefile using "Multipart to Single Part" then it works. I suspect the plugin author has not considered Multipart geometry and only tested on Single Part. I see 178 features in both cases, so you don't actually have any Multipart features (A multipart feature is one where two separate "islands" are considered as a single feature in the shapefile).
    – Spacedman
    Commented Jul 22, 2020 at 13:49
  • 1
    Nailed it. The problem is because your shapefile name starts with a digit, and that causes a syntax error in an SQL expression. Am reporting a bug. Rename your shapefile to start with a character and it will work. Its nothing to do with multi/single polygons its just that when I converted it I saved it with a name starting with a letter!
    – Spacedman
    Commented Jul 22, 2020 at 21:37

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.