[SCM] PostGIS branch master updated. 3.6.0rc2-420-gf92f80d77
git at osgeo.org
git at osgeo.org
Tue Mar 31 15:38:56 PDT 2026
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "PostGIS".
The branch, master has been updated
via f92f80d776d2d8eb88b2c8f67908b69b2922251c (commit)
from a7c7a837809bbed24ca7d5a474411ef784f555ee (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commit f92f80d776d2d8eb88b2c8f67908b69b2922251c
Author: Paul Ramsey <pramsey at cleverelephant.ca>
Date: Tue Mar 31 15:36:29 2026 -0700
Add Window function ST_MinimumSpanningTree(geometry)
Takes in SetOf LineString, builds a graph with start/end points
as nodes, finds the MST for each connected graph,
and returns an integer for each LineString,
with a non-zero value indicating participation in the
MST, and those numbers being distinct for each connected
graph.
diff --git a/doc/reference_cluster.xml b/doc/reference_cluster.xml
index dfe7e90eb..e86b917a8 100644
--- a/doc/reference_cluster.xml
+++ b/doc/reference_cluster.xml
@@ -363,6 +363,68 @@ FROM clusterrelate;
</refentry>
+ <refentry xml:id="ST_MinimumSpanningTree">
+ <refnamediv>
+ <refname>ST_MinimumSpanningTree</refname>
+
+ <refpurpose>Window function that returns a tree id for each input geometry, clustering input geometries into connected trees using the Minimum Spanning Tree algorithm.</refpurpose>
+ </refnamediv>
+
+ <refsynopsisdiv>
+ <funcsynopsis>
+ <funcprototype>
+ <funcdef>integer <function>ST_MinimumSpanningTree</function></funcdef>
+ <paramdef><type>geometry winset </type> <parameter>geom</parameter></paramdef>
+ </funcprototype>
+ </funcsynopsis>
+ </refsynopsisdiv>
+
+ <refsection>
+ <title>Description</title>
+
+ <para>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.</para>
+ <para>The <link xlink:href="https://en.wikipedia.org/wiki/Minimum_spanning_tree">Minimum Spanning Tree</link> 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.</para>
+
+ <para role="availability" conformance="3.7.0">Availability: 3.7.0</para>
+ <para role="geos_requirement" conformance="3.15.0">Requires GEOS >= 3.15.0</para>
+ </refsection>
+
+ <refsection>
+ <title>Examples</title>
+ <programlisting>
+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
+ </programlisting>
+ </refsection>
+ <refsection>
+ <title>See Also</title>
+ <para>
+ <xref linkend="ST_ClusterDBSCAN"/>,
+ <xref linkend="ST_ClusterKMeans"/>,
+ <xref linkend="ST_ClusterIntersectingWin"/>
+ </para>
+ </refsection>
+
+ </refentry>
+
+
<refentry xml:id="ST_ClusterKMeans">
<refnamediv>
diff --git a/postgis/lwgeom_window.c b/postgis/lwgeom_window.c
index 920f2716d..2870527fe 100644
--- a/postgis/lwgeom_window.c
+++ b/postgis/lwgeom_window.c
@@ -1037,3 +1037,93 @@ Datum ST_CoverageUnion(PG_FUNCTION_ARGS)
PG_RETURN_POINTER(result);
}
+
+extern Datum ST_MinimumSpanningTree(PG_FUNCTION_ARGS);
+PG_FUNCTION_INFO_V1(ST_MinimumSpanningTree);
+Datum ST_MinimumSpanningTree(PG_FUNCTION_ARGS)
+{
+#if POSTGIS_GEOS_VERSION < 31500
+ lwpgerror("The GEOS version this PostGIS binary "
+ "was compiled against (%d) doesn't support "
+ "'ST_MinimumSpanningTree' function (3.15.0+ required)",
+ POSTGIS_GEOS_VERSION);
+ PG_RETURN_NULL();
+#else
+
+ WindowObject win_obj = PG_WINDOW_OBJECT();
+ uint32_t row = WinGetCurrentPosition(win_obj);
+ uint32_t ngeoms = WinGetPartitionRowCount(win_obj);
+ cluster_context* context = fetch_cluster_context(win_obj, ngeoms);
+
+ if (row == 0) /* beginning of the partition; do all of the work now */
+ {
+ uint32_t i;
+ GEOSGeometry** geoms = palloc(ngeoms * sizeof(GEOSGeometry*));
+ size_t* cluster_ids;
+
+ context->is_error = LW_TRUE; /* until proven otherwise */
+
+ initGEOS(lwpgnotice, lwgeom_geos_error);
+
+ for (i = 0; i < ngeoms; i++)
+ {
+ bool geom_is_null;
+ geoms[i] = read_geos_from_partition(win_obj, i, &geom_is_null);
+
+ if (!geoms[i])
+ {
+ lwpgerror("Error reading geometry.");
+ PG_RETURN_NULL();
+ }
+
+ context->clusters[i].is_null = geom_is_null;
+ /* If read_geos_from_partition returned a value (even empty) for a
+ non-null input, we keep it. If it was null, is_null is true. */
+ }
+
+ /* Call GEOS */
+ /* Note: GEOSMinimumSpanningTree signature assumed:
+ size_t* GEOSMinimumSpanningTree(GEOSGeometry* const* geoms, size_t ngeoms);
+ */
+ cluster_ids = GEOSMinimumSpanningTree(geoms, ngeoms);
+
+ if (cluster_ids)
+ {
+ context->is_error = LW_FALSE;
+ for (i = 0; i < ngeoms; i++)
+ {
+ context->clusters[i].cluster_id = (uint32_t)cluster_ids[i];
+ }
+ /* Release the array returned by GEOS */
+ GEOSFree(cluster_ids);
+ }
+ else
+ {
+ /* Usually GEOS functions return NULL on error, but also check for context error */
+ /* However, if ngeoms is 0, it might return NULL but that's handled by loop */
+ /* If GEOS failed, we error out */
+ if (ngeoms > 0)
+ lwpgerror("GEOSMinimumSpanningTree failed");
+ else
+ context->is_error = LW_FALSE; /* Empty set is fine */
+ }
+
+ for (i = 0; i < ngeoms; i++)
+ {
+ if (geoms[i]) GEOSGeom_destroy(geoms[i]);
+ }
+ pfree(geoms);
+
+ if (context->is_error)
+ {
+ lwpgerror("Error during MST clustering");
+ PG_RETURN_NULL();
+ }
+ }
+
+ if (context->clusters[row].is_null)
+ PG_RETURN_NULL();
+
+ PG_RETURN_INT32(context->clusters[row].cluster_id);
+#endif
+}
diff --git a/postgis/postgis.sql.in b/postgis/postgis.sql.in
index e378a453d..41a7ee22a 100644
--- a/postgis/postgis.sql.in
+++ b/postgis/postgis.sql.in
@@ -1948,6 +1948,13 @@ CREATE OR REPLACE FUNCTION ST_ClusterRelateWin(geom geometry, relate_matrix text
LANGUAGE 'c' IMMUTABLE STRICT WINDOW PARALLEL SAFE
_COST_HIGH;
+-- Availability: 3.7.0
+CREATE OR REPLACE FUNCTION ST_MinimumSpanningTree(geometry)
+ RETURNS int
+ AS 'MODULE_PATHNAME', 'ST_MinimumSpanningTree'
+ LANGUAGE 'c' IMMUTABLE STRICT WINDOW PARALLEL SAFE
+ _COST_HIGH;
+
-- Availability: 1.2.2
CREATE OR REPLACE FUNCTION ST_LineMerge(geometry)
RETURNS geometry
diff --git a/regress/core/spanningtree.sql b/regress/core/spanningtree.sql
new file mode 100644
index 000000000..063c18855
--- /dev/null
+++ b/regress/core/spanningtree.sql
@@ -0,0 +1,42 @@
+
+-- Connected graph (all one cluster)
+SELECT 'connected', id, ST_MinimumSpanningTree(geom) OVER (ORDER BY id) 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);
+
+-- Disconnected graph (two clusters)
+SELECT 'disconnected', id, ST_MinimumSpanningTree(geom) OVER (ORDER BY id) 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(11 11,11 10)'::geometry),
+ (5, 'LINESTRING(10 10,11 11)'::geometry),
+ (6, 'LINESTRING(11 10,10 11)'::geometry)
+) AS t(id, geom);
+
+
+-- NULL handling
+SELECT 'nulls', id, ST_MinimumSpanningTree(geom) OVER (ORDER BY id), ST_AsText(geom) FROM (VALUES
+ (1, 'LINESTRING(0 0,1 0)'::geometry),
+ (2, 'LINESTRING(0 0,0 1)'::geometry),
+ (3, NULL::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);
+
+-- Empty geometry handling
+SELECT 'empty', id, ST_MinimumSpanningTree(geom) OVER (ORDER BY id), ST_AsText(geom) FROM (VALUES
+ (1, 'LINESTRING(0 0,1 0)'::geometry),
+ (2, 'LINESTRING EMPTY'::geometry),
+ (3, 'LINESTRING EMPTY'::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);
+
diff --git a/regress/core/spanningtree_expected b/regress/core/spanningtree_expected
new file mode 100644
index 000000000..8421fd061
--- /dev/null
+++ b/regress/core/spanningtree_expected
@@ -0,0 +1,24 @@
+connected|1|1
+connected|2|1
+connected|3|1
+connected|4|0
+connected|5|0
+connected|6|0
+disconnected|1|1
+disconnected|2|1
+disconnected|3|1
+disconnected|4|2
+disconnected|5|2
+disconnected|6|2
+nulls|1|1|LINESTRING(0 0,1 0)
+nulls|2|1|LINESTRING(0 0,0 1)
+nulls|3||
+nulls|4|1|LINESTRING(1 1,1 0)
+nulls|5|0|LINESTRING(0 0,1 1)
+nulls|6|0|LINESTRING(1 0,0 1)
+empty|1|1|LINESTRING(0 0,1 0)
+empty|2|0|LINESTRING EMPTY
+empty|3|0|LINESTRING EMPTY
+empty|4|1|LINESTRING(1 1,1 0)
+empty|5|0|LINESTRING(0 0,1 1)
+empty|6|1|LINESTRING(1 0,0 1)
diff --git a/regress/core/tests.mk.in b/regress/core/tests.mk.in
index a2f66dad1..d34642e3d 100644
--- a/regress/core/tests.mk.in
+++ b/regress/core/tests.mk.in
@@ -166,6 +166,11 @@ else
$(top_srcdir)/regress/core/concave_hull
endif
+ifeq ($(shell expr "$(POSTGIS_GEOS_VERSION)" ">=" 31500),1)
+ TESTS += \
+ $(top_srcdir)/regress/core/spanningtree
+endif
+
ifeq ($(shell expr "$(POSTGIS_GEOS_VERSION)" ">=" 31200),1)
TESTS += \
$(top_srcdir)/regress/core/coverage
-----------------------------------------------------------------------
Summary of changes:
doc/reference_cluster.xml | 62 ++++++++++++++++++++++++++
postgis/lwgeom_window.c | 90 ++++++++++++++++++++++++++++++++++++++
postgis/postgis.sql.in | 7 +++
regress/core/spanningtree.sql | 42 ++++++++++++++++++
regress/core/spanningtree_expected | 24 ++++++++++
regress/core/tests.mk.in | 5 +++
6 files changed, 230 insertions(+)
create mode 100644 regress/core/spanningtree.sql
create mode 100644 regress/core/spanningtree_expected
hooks/post-receive
--
PostGIS
More information about the postgis-tickets
mailing list