Recherche de l'arbre couvrant minimum (MST)

Question

J'ai un ensemble de points auxquels je veux trouver l'arbre couvrant minimum avec PostGIS. Je n'ai pas de lignes entre eux, je n'ai que le point de départ à partir duquel commencer à construire l'arbre (le Multilinestring)

Je ne sais pas comment commencer à coder cela, serait-il préférable de le faire avec une requête récursive? peut-être implémenter les algorithmes Prim ou Kruskal en utilisant les distances entre les points?

Pour l'instant, j'ai un tableau avec les points (id, geom) et le point de départ ( start_point: = getStartPoint (points))

MST: l'arbre couvrant le poids minimum est un sous-ensemble des arêtes d'un graphe non orienté, pondéré par les arêtes, qui relie tous les sommets ensemble, sans aucun cycle et avec le poids total minimal possible des arêtes.

Answer 1

Grâce à @spacedman, j'ai pu le résoudre, en utilisant le code du post suivant: gist.github.com/andrewxhill/13de0618d31893cdc4c5

Je laisse un exemple pour ceux qui ont besoin de le reproduire, une fois les types et fonctions du post créés (je n'ai rien changé), vous pouvez appeler la fonction principale comme suit:

SELECT (minimum_spanning_tree_calc( minimum_spanning_tree(geom ,  id::text ORDER BY id ASC) )).* 
FROM tree_points 

Voici un mini ensemble de données à exécuter et voir le résultat:

with tree_points as(
    SELECT row_number() OVER () as id,geom 
    FROM
    unnest(array['POINT(0 0)'::geometry,'POINT(1 1)'::geometry,'POINT(2 2)'::geometry,'POINT(2 3)'::geometry,'POINT(3 3)'::geometry,'POINT(4 3)'::geometry,'POINT(4 4)'::geometry,'POINT(5 3)'::geometry,'POINT(5 5)'::geometry,'POINT(5 6)'::geometry,'POINT(5 7)'::geometry,'POINT(5 8)'::geometry,'POINT(6 6)'::geometry,'POINT(7 7)'::geometry]) as geom
)
SELECT (minimum_spanning_tree_calc( minimum_spanning_tree(geom ,  id::text ORDER BY id ASC) )).* 
FROM tree_points 

J'espère que cela a été compris, et merci à spacedman et andrewxhill pour votre temps!