ST_MinimumSpanningTree — Window function that returns a tree id for each input geometry, clustering input geometries into connected trees using the Minimum Spanning Tree algorithm.
integer ST_MinimumSpanningTree(geometry winset geom);
A window function that builds connected graphs of line strings based on the Minimum Spanning Tree (MST) of the input geometries. The return value is the cluster number that the geometry argument participates in, or zero if it is not part of the minimum tree.
The Minimum Spanning Tree connects all geometries in the window partition such that the total length of the connecting lines is minimized. If the graph is not fully connected (e.g. infinite distance between some geometries), it produces a Minimum Spanning Forest, and each connected component is assigned a unique tree ID.
Availability: 3.7.0
Requires GEOS >= 3.15.0
These six edges describe a square with both diagonals. The minimum spanning tree keeps three edges and excludes the rest.
WITH edges(id, geom) AS (
VALUES
(1, 'LINESTRING(0 0,1 0)'::geometry),
(2, 'LINESTRING(0 0,0 1)'::geometry),
(3, 'LINESTRING(1 1,0 1)'::geometry),
(4, 'LINESTRING(1 1,1 0)'::geometry),
(5, 'LINESTRING(0 0,1 1)'::geometry),
(6, 'LINESTRING(1 0,0 1)'::geometry)
), marked AS (
SELECT id,
geom,
ST_MinimumSpanningTree(geom) OVER (ORDER BY id) AS tree_id
FROM edges
)
SELECT string_agg(id::text, ',' ORDER BY id)
FILTER (WHERE tree_id > 0) AS tree_edge_ids,
ST_Collect(geom ORDER BY id)
FILTER (WHERE tree_id > 0) AS tree_edges,
string_agg(id::text, ',' ORDER BY id)
FILTER (WHERE tree_id = 0) AS excluded_edge_ids,
ST_Collect(geom ORDER BY id)
FILTER (WHERE tree_id = 0) AS excluded_edges
FROM marked;
-[ RECORD 1 ]----- tree_edge_ids | 1,2,3 tree_edges | MULTILINESTRING((0 0,1 0),(0 0,0 1),(1 1,0 1)) excluded_edge_ids | 4,5,6 excluded_edges | MULTILINESTRING((1 1,1 0),(0 0,1 1),(1 0,0 1))