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
    
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
    
Did you find any solution to this problem? I'm doing a similar task just manually, with a custom script: gis.stackexchange.com/questions/21823/… –  culebrón Mar 16 '12 at 14:36
1  
@culebrón I've posted my solution below gis.stackexchange.com/a/12380/187 –  underdark Mar 17 '12 at 12:17
add comment

3 Answers

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
show 1 more comment

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
add comment

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
add comment

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.