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
SELECT id, ST_AsText(geom), ST_MinimumSpanningTree(geom) OVER () AS msp
FROM (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)
) AS t(id, geom);
id | st_astext | msp
----+---------------------+-----
1 | LINESTRING(0 0,1 0) | 1
2 | LINESTRING(0 0,0 1) | 1
3 | LINESTRING(1 1,0 1) | 1
4 | LINESTRING(1 1,1 0) | 0
5 | LINESTRING(0 0,1 1) | 0
6 | LINESTRING(1 0,0 1) | 0
ST_ClusterDBSCAN, ST_ClusterKMeans, ST_ClusterIntersectingWin