Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

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

share|improve this question
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 '11 at 21:03
    
It's for shortest-path analysis. –  underdark Jul 19 '11 at 21:39
1  
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 at 15:54
    
Topology is key. Geometry can change a little. Z order has to stay intact. –  underdark Jun 4 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

share|improve this answer
    
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 at 16:49

Have you tried the GRASS v.generalize ?

Here comes a tutorial.

share|improve this answer
    
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
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 '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
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 '11 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

share|improve this answer
    
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

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

share|improve this answer

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
share|improve this answer
    
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 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 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 at 6:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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