4

I have a set of points at which I want to find the minimum spanning tree with PostGIS. I have no lines between them, I only have the starting point from which to start building the tree (the Multilinestring)

I don't know how to start coding this, would it be better to do it with a recursive query? maybe implement the Prim or Kruskal algorithms using the distances between the points?

For now, I have a table with the points (id, geom) and the starting point (start_point: = getStartPoint (points))

enter image description here

MST: minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

  • 2
    Its not very documented but does this work? gist.github.com/andrewxhill/13de0618d31893cdc4c5 Not sure if its working on lines or points, but if lines you could create a full graph connecting all your points and work on that. – Spacedman Sep 15 at 15:19
  • 1
    maybe pg_routing ? : docs.pgrouting.org/3.0/en/spanningTree-family.html – J. Monticolo Sep 15 at 15:21
  • thank you both! @spacedman that solution works like a charm! – liap307 Sep 16 at 15:22
  • 1
    I can't get it to work with a quick test - how about you answer your question with an example? That would very helpful! I think I've not got my data right or an incompatible version of something. @liap307 – Spacedman Sep 16 at 16:37
  • 1
    of course! give me some time – liap307 Sep 16 at 18:40
4

Thanks to @spacedman I was able to solve it, using the code from the following post: gist.github.com/andrewxhill/13de0618d31893cdc4c5

I leave an example for those who need to reproduce it, once the types and functions of the post have been created (I didn't change anything), you can call the main function as follows:

SELECT (minimum_spanning_tree_calc( minimum_spanning_tree(geom ,  id::text ORDER BY id ASC) )).* 
FROM tree_points 

Here is a mini dataset to run and see the result:

with tree_points as(
    SELECT row_number() OVER () as id,geom 
    FROM
    unnest(array['POINT(0 0)'::geometry,'POINT(1 1)'::geometry,'POINT(2 2)'::geometry,'POINT(2 3)'::geometry,'POINT(3 3)'::geometry,'POINT(4 3)'::geometry,'POINT(4 4)'::geometry,'POINT(5 3)'::geometry,'POINT(5 5)'::geometry,'POINT(5 6)'::geometry,'POINT(5 7)'::geometry,'POINT(5 8)'::geometry,'POINT(6 6)'::geometry,'POINT(7 7)'::geometry]) as geom
)
SELECT (minimum_spanning_tree_calc( minimum_spanning_tree(geom ,  id::text ORDER BY id ASC) )).* 
FROM tree_points 

enter image description here

I hope it was understood, and thanks to spacedman and andrewxhill for your time!

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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