# 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? Jul 19, 2011 at 21:03
• It's for shortest-path analysis. 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. 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? Jun 2, 2014 at 15:54
• Topology is key. Geometry can change a little. Z order has to stay intact. 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
Jul 19, 2011 at 14:12
• Is that image created in grass? Nov 5, 2011 at 10:46
• The image shows the results of GRASS v.clean visualized in QGIS. Nov 5, 2011 at 11:30
• Any issues with maintaining "weird intersections" or grade separated roads? May 29, 2014 at 16:49
• How about processing ST_SnapToGrid after v.clean? 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. Jul 19, 2011 at 8:56
• I really can't find a v.generalize method that will do what I want. 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
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. 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. 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? 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
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 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