How to simplify a routable network?

I have a network graph that I need to simplify in the sense of reducing the number of edges. The idea would be to merge nodes that are located close together and remove the connecting short edges.

How could this be achieved in PostGIS or GRASS? Or are there any better approaches to automatically simplify a network like this?

I've already tried ST_SnapToGrid function but I'm not happy with the results (grey = original, black = snapped):

• Are you doing this to simplify a network-based analysis or for display purposes? If it's the former, what analysis will be performed? Commented Jul 19, 2011 at 21:03
• It's for shortest-path analysis. Commented Jul 19, 2011 at 21:39
• Because many of the shortest-path algorithms are O(E+V), perhaps you don't even need this simplification? At the other extreme, for such analyses you can often make drastically more aggressive simplifications. For instance, that set of three parallel segments and their adjoining segments on the left (looking like an H-in-a-box) can be replaced by a triangle if no origin or destination lies within those segments. I mention this because I'm sure there is (non-GIS) code out there for such operations on (abstract) graphs. Commented Jul 19, 2011 at 21:49
• Do you want to maintain the geometry of the edges (e.g. curves) or is just maintaining topology + node XY sufficient? Also, do you need to ensure nodes at different Z (e.g. flyovers) do not snap together? Commented Jun 2, 2014 at 15:54
• Topology is key. Geometry can change a little. Z order has to stay intact. Commented Jun 4, 2014 at 13:31

The closest I've come so far is this:

``````v.clean input=roads output=snap5rmline tool=snap,rmline thresh=5
``````

It's snapping the roads with a tolerance of 5 meters and removing all zero-length lines. It's not an optimal solution since it seems to snap rather randomly to some vertex.

• Indeed, the result is maybe not accurate but that use of v.clean is interesting, thanks for sharing
– simo
Commented Jul 19, 2011 at 14:12
• Is that image created in grass? Commented Nov 5, 2011 at 10:46
• The image shows the results of GRASS v.clean visualized in QGIS. Commented Nov 5, 2011 at 11:30
• Any issues with maintaining "weird intersections" or grade separated roads? Commented May 29, 2014 at 16:49
• How about processing ST_SnapToGrid after v.clean? Commented May 25, 2016 at 13:46

Have you tried the GRASS v.generalize ?

`v.generalize` allows you to choose the generalization algorithm with the method attribute. There is a bunch : douglas,douglas_reduction,lang,reduction,reumann,boyle,sliding_averaging,distance_weighting,chaiken,hermite,snakes,network,displacement.

And additional parameters as `threshold`, `degree_thresh`, `angle_thresh` (depending on chosen algorithm) may help you to get an accurate result.

Here comes a tutorial.

• Thank you for the link. I'm giving it a try though I don't really get which combination of method and thresholds values will give the result I'm looking for. Commented Jul 19, 2011 at 8:56
• I really can't find a v.generalize method that will do what I want. Commented Jul 19, 2011 at 10:19
• It's a pity, the command is rich of many algorithms but as you said before, it's probably quite complex to set up for getting the expected result. Maybe a generalization algoritms guru, here? Have you tried also the snakes method?
– simo
Commented Jul 19, 2011 at 10:37
• Not an algo-guru here, but I find the snakes method the best for some of my v.genralize runs I made in the past. Commented Jul 19, 2011 at 11:28
• For the record, parameters have been simplified as of today in GRASS SVN. To become part of GRASS 6.4.2. Commented Jul 25, 2011 at 22:25

I haven't done this but I think I can suggest a direction.

1. Create a topology with PostGIS for your graph.
2. Find all nodes with only two edges.
3. Heal the edges.

ST_ModEdgeHeal will merge one edge into the other. ST_NewEdgeHeal will replace both with a new edge.

PostGIS Topology manual

• Thanks @Sean. Will that do anything else than merge two edges? Any idea about how to remove short edges and snap their nodes together? Commented Jul 20, 2011 at 19:33
• @Underdark, I don't see anything simple. You could do it all in PL/SQL but that probably doesn't help. Can you run ST_SnapToGrid first?
– Sean
Commented Jul 22, 2011 at 14:23

@underdark , I see that you have written a tool to densify lines in Sextante. Therefore I suggest the following algorithm to avoid "random" snapping one of your points.

Select the line segments that you want to get rid of based on their length.

For each of those segments, create a point at the middle point

Delete the small segment

Now you can use ST_Snap in PostGIS (see example here )

EDIT: note that in your case, you could also use v.net first in order to remove the pseudo-nodes (node that connect only two lines)

• Please elaborate how v.net can be used to remove pseudo-nodes. Thanks Commented May 9, 2017 at 8:01

Forwarding how Michaël Michaud analyzed this on the OpenJUMP developer list:

``````> Interesting question. There has been so much research works about
> generalization that it is surely not a simple task. I have tested the
> following approach with mitigated results :
> - make the layer planar with the noder plugin
> - detect small cycles with the graph plugin
> - merge adjacent cycles
> - create a point inside each cycles surface
> - remove network segments along these cycles (query + DE-9IM)
> - detect roads touching the cycles
> - project the center points of cycles to the road endpoints ==> replace small roundabout by simple nodes
>
> Possible improvements (probably need a dedicated plugin)
> - make it work on non planar graph (or just remove bridges/tunnels from the graph)
> - replace small edges between two nodes with degree 3+ by a single node,    not only small cycles
> - process iteratively starting with smallest edges/cycles
``````
• Thank you for posting this answer. I'm a bit confused why you would force the graph to planar. After all, street networks are not planar graphs (bridges, tunnels). Commented May 29, 2014 at 17:02
• Only because Michaël made a fast test with existing graph tools which he has written for OpenJUMP and they do not support non-planar graphs at the moment. Skip the first step if QGIS and GRASS have similar tools which support non-planar graphs. Commented May 29, 2014 at 19:45
• I think this is the right approach - seperate out the network into planar graphs. In each planar graph the problem is simpler - for example one could use the above approach, or simply triangulate and weed the TIN of short road edges. Then extract the road edges again and merge the layers together. Commented Jun 3, 2014 at 6:42