[GIS] How to compute the smallest network that connects all points using PostGIS

postgisrouting

I have a set of postgis scripts which generates two tables – one of a set of points and the second a set of roads which surround them. All data is in the same projection and both outputs are stored in postgres 9.2 tables with postgis 2.1

The pgrouting topology of the road network has been created and the points table has a column containing the nearest road segment.

I'd like then to generate a subset of the road network which represents the smallest network that connects all points using something like a minimum spanning tree. The road network is undirected, and costs are simply the route length.

I can do this in QGIS/Grass using the v.net family of modules but ideally I'd like to keep this final step in SQL as well.

I've looked at the new apspWarshall postgis function but I'm at a loss as to how it can be encouraged to focus its energy on connecting the points and not the whole network.

This is the short script I've put together in an attempt to create a framework to solve this but I can't see where its possible to focus the function to start with a subset of the edges. 

SELECT seq, id1 AS node, id2 AS edge, cost, the_geom
FROM   pgr_apspWarshall('SELECT gid AS id, 
                                source, 
                                target, 
                                st_length(the_geom) AS cost 
                         FROM   road_network
                        ',
                        false, false
                       ) AS tree
JOIN   road_network As roads
ON     tree.id2 = roads.gid

In single path shortest path problems the function asks for the start and end but apparently not in the all points problems. Equally in Grass the v.net.spanningtree and v.net.steiner expect a set of points and lines as a combined network to work with.

Does anyone have an suggestions for how to do this in PostGIS?

Best Answer

This answer is not complete or tested, but try something like this:

according to questions/39210:

with index_query as (
SELECT
        ,ST_Distance(i.geom, i.b_geom) AS dist
        ,ST_MakeLine(i.geom, i.b_geom) as geom
FROM(
SELECT
        ,a.geom
        ,b.geom AS b_geom
        ,rank() OVER (PARTITION BY a.id ORDER BY ST_Distance(a.centroid_geom, b.the_geom)) AS pos
FROM points a, points b 
WHERE a.id <> b.id) i
WHERE pos = 1
) select ST_Union(geom) from index_query;

i think this is not very efficient.

Related Question