Tìm cây bao trùm tối thiểu (MST)

Question

Tôi có một tập hợp các điểm mà tôi muốn tìm cây bao trùm tối thiểu với PostGIS. Tôi không có ranh giới nào giữa chúng, tôi chỉ có điểm bắt đầu để bắt đầu xây dựng cây (Chuỗi đa tuyến)

Tôi không biết làm thế nào để bắt đầu mã hóa điều này, sẽ tốt hơn nếu làm điều đó với một truy vấn đệ quy? có thể thực hiện các thuật toán Prim hoặc Kruskal bằng cách sử dụng khoảng cách giữa các điểm?

Hiện tại, tôi có một bảng với các điểm (id, geom) và điểm bắt đầu ( start_point: = getStartPoint (points))

MST: cây bao trùm trọng số tối thiểu là một tập hợp con của các cạnh của đồ thị vô hướng có trọng số cạnh được kết nối, kết nối tất cả các đỉnh với nhau, không có bất kỳ chu trình nào và với tổng trọng số cạnh nhỏ nhất có thể.

Answer 1

Nhờ @spacedman, tôi đã có thể giải quyết nó, bằng cách sử dụng mã từ bài đăng sau: gist.github.com/andrewxhill/13de0618d31893cdc4c5

Tôi để lại một ví dụ cho những ai cần tạo lại nó, một khi các kiểu và chức năng của bài đăng đã được tạo (tôi không thay đổi gì cả), bạn có thể gọi hàm chính như sau:

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

Đây là một tập dữ liệu nhỏ để chạy và xem kết quả:

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 

Tôi hy vọng nó đã được hiểu, và cảm ơn spacedman và andrewxhill đã dành thời gian của bạn!