Wednesday 22 February 2017

routing - How to compute the smallest network that connects all points using PostGIS?


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?




No comments:

Post a Comment

arcpy - Changing output name when exporting data driven pages to JPG?

Is there a way to save the output JPG, changing the output file name to the page name, instead of page number? I mean changing the script fo...