Minimum yayılma ağacını (MST) bulma

Question

PostGIS ile minimum yayılma ağacını bulmak istediğim bir dizi noktam var. Aralarında çizgim yok, sadece ağacı oluşturmaya başlamak için başlangıç ​​noktasına sahibim (Multilinestring)

Bunu kodlamaya nasıl başlayacağımı bilmiyorum, bunu özyinelemeli bir sorgu ile yapmak daha iyi olur mu? noktalar arasındaki mesafeleri kullanarak Prim veya Kruskal algoritmalarını uygulayabilir mi?

Şimdilik, noktaları (id, geom) ve başlangıç ​​noktası ( start_point: = getStartPoint (points)) olan bir tablom var

MST: minimum ağırlık kapsayan ağaç, tüm köşeleri herhangi bir döngü olmaksızın ve mümkün olan minimum toplam kenar ağırlığıyla birbirine bağlayan, bağlantılı, kenar ağırlıklı, yönsüz grafiğin kenarlarının bir alt kümesidir.

Answer 1

@Spacedman sayesinde aşağıdaki gönderideki kodu kullanarak çözebildim : gist.github.com/andrewxhill/13de0618d31893cdc4c5

Yeniden üretmesi gerekenler için bir örnek bırakıyorum, yazının türleri ve işlevleri oluşturulduktan sonra (hiçbir şeyi değiştirmedim), ana işlevi şu şekilde çağırabilirsiniz:

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

İşte çalıştırmak ve sonucu görmek için mini bir veri kümesi:

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 

Umarım anlaşılmıştır ve zaman ayırdığınız için uzaylı adam ve Andrewxhill'e teşekkürler!