# 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? – whuber Jul 19 '11 at 21:03
It's for shortest-path analysis. – underdark Jul 19 '11 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. – whuber Jul 19 '11 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? – AnserGIS Jun 2 '14 at 15:54
Topology is key. Geometry can change a little. Z order has to stay intact. – underdark Jun 4 '14 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 '11 at 14:12
Is that image created in grass? – NetConstructor.com Nov 5 '11 at 10:46
The image shows the results of GRASS v.clean visualized in QGIS. – underdark Nov 5 '11 at 11:30
Any issues with maintaining "weird intersections" or grade separated roads? – dassouki May 29 '14 at 16:49
How about processing ST_SnapToGrid after v.clean? – kttii May 25 at 13:46

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? – underdark Jul 20 '11 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 '11 at 14:23

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.

-

We're looking for long answers that provide some explanation and context. Don't just give a one-line answer; explain why your answer is right, ideally with citations. Answers that don't include explanations may be removed.

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. – underdark Jul 19 '11 at 8:56
I really can't find a v.generalize method that will do what I want. – underdark Jul 19 '11 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 '11 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. – maning Jul 19 '11 at 11:28
For the record, parameters have been simplified as of today in GRASS SVN. To become part of GRASS 6.4.2. – markusN Jul 25 '11 at 22:25

@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)

-

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
> - 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). – underdark May 29 '14 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. – user30184 May 29 '14 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. – AnserGIS Jun 3 '14 at 6:42