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

enter image description here

  • 1
    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, 2011 at 21:03
  • It's for shortest-path analysis.
    – underdark
    Jul 19, 2011 at 21:39
  • 2
    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, 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?
    – AnserGIS
    Jun 2, 2014 at 15:54
  • Topology is key. Geometry can change a little. Z order has to stay intact.
    – underdark
    Jun 4, 2014 at 13:31

5 Answers 5


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.

enter image description here

  • 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.
    – underdark
    Nov 5, 2011 at 11:30
  • 1
    Any issues with maintaining "weird intersections" or grade separated roads?
    – dassouki
    May 29, 2014 at 16:49
  • How about processing ST_SnapToGrid after v.clean?
    – kttii
    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.
    – underdark
    Jul 19, 2011 at 8:56
  • I really can't find a v.generalize method that will do what I want.
    – underdark
    Jul 19, 2011 at 10:19
  • 2
    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.
    – maning
    Jul 19, 2011 at 11:28
  • 1
    For the record, parameters have been simplified as of today in GRASS SVN. To become part of GRASS 6.4.2.
    – markusN
    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?
    – underdark
    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
    – osmjit
    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).
    – underdark
    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.
    – user30184
    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.
    – AnserGIS
    Jun 3, 2014 at 6:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.