Skip to content

Instantly share code, notes, and snippets.

@geozelot
Last active October 28, 2022 09:40
Show Gist options
  • Save geozelot/a9c461383e11c22d1ff675eb02a752d5 to your computer and use it in GitHub Desktop.
Save geozelot/a9c461383e11c22d1ff675eb02a752d5 to your computer and use it in GitHub Desktop.
PostgreSQL/PostGIS - Fast MST over a set of POINT geometries.
/*
* Generates the minimum spanning tree (MST) over a set
* of POINT geometries. In pure SQL, this is about the most
* performant way for the specific case of point sets,
* given proper spatial indexing of the <graph> table/MV.
*
* Assumes the presence of an <id> and <geom> column in <graph>.
*/
WITH RECURSIVE
tree AS (
SELECT
g.<geom>::GEOMETRY AS vtcs,
NULL::GEOMETRY AS segment,
ARRAY[g.<id>] AS ids
FROM
<graph> AS g
WHERE
g.<id> = 1
UNION ALL
SELECT
ST_Union(t.vtcs, v.<geom>),
ST_ShortestLine(t.vtcs, v.<geom>),
t.ids || v.<id>
FROM
tree AS t
CROSS JOIN LATERAL (
SELECT
g.<id>, g.<geom>
FROM
<graph> AS g
WHERE
NOT g.<id> = ANY(t.ids)
ORDER BY
t.vtcs <-> g.<geom>
LIMIT
1
) AS v
)
SELECT
segment
FROM
tree
WHERE
segment IS NOT NULL
;
@geozelot
Copy link
Author

This may or may not benefit from a PL/pgSQL impementation...

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment