ST_MinimumSpanningTree — Fönsterfunktion som returnerar ett träd-id för varje indatageometri och klustrar indatageometrier i sammanhängande träd med algoritmen Minimum Spanning Tree.
integer ST_MinimumSpanningTree(geometry winset geom);
En fönsterfunktion som bygger sammanhängande grafer av linestrings utifrån indatageometriernas Minimum Spanning Tree (MST). Returvärdet är klusternumret som geometriargumentet ingår i, eller noll om det inte är del av det minimala trädet.
Minimum Spanning Tree sammanlänkar alla geometrier i fönsterpartitionen så att den sammanlagda längden av förbindelselinjerna minimeras. Om grafen inte är helt sammanhängande, till exempel vid oändligt avstånd mellan geometrier, skapas en Minimum Spanning Forest och varje sammanhängande komponent tilldelas ett unikt träd-id.
Tillgänglig sedan: 3.7.0
Kräver GEOS >= 3.15.0
Dessa sex kanter beskriver en kvadrat med båda diagonalerna. Det minimala spännträdet behåller tre kanter och utesluter resten.
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))