This tutorial presents and explains the functionality of GRASS vector module v.generalize. This module implements generalization operators for GRASS vector maps. The topics covered in this tutorial are: simplification, smoothing, network generalization and displacement. For the basic introduction to these operators chech the module's man pages or for the exhausting introduction check McMaster and Shea (TODO: add reference).
It is recommended to read the official man page before reading this document, or read these two documents at the same time since this tutorial does not contain the (detail) descriptions of input parameters whereas the man page has very few examples and no pictures at all. (Even the author of module and both of the documents must have consult the man page several times....) This document is also meant to be a "report" showing the work done during the Google Summer of Code 2007.
Most of the examples in this text work with Spearfish dataset, which can be downloaded here. Also, this tutorial assumes that the user is already running GRASS session with the Spearfish location and a monitor loaded. Also, if you click on any picture, it is shown in the full size.
All the algorithms presented in this document (try to) preserve the topology of the input maps. This means, for example, that the smoothing and simplification methods never remove the first and last points of lines and that displacement preserves the junctions.
v.generalize implements many simplification algorithms. The most widely used is Douglas-Peucker algorithm (TODO: reference). We can apply this algorithm to any vector map in the following way:
v.generalize input=roads output=roads_douglas method=douglas threshold=50
Number of vertices was reduced from 5468 to 2107[38%]
d.vect roads d.vect roads_douglas col=blue
The amount of the details removed can be specified by parameter: threshold. It is the case that the output map has fewer vertices and details for greater values of threshold. For example, if we run
v.generalize input=roads output=roads_douglas method=douglas threshold=200 --overwrite
v.generalize -r input=roads output=roads_douglas method=douglas threshold=200 --overwrite
It is also possible remove small lines/areas only (without any simplification). This is achieved by method=remove_small:
v.generalize input=roads output=roads_remove_small method=remove_small threshold=200
Douglas-Peucker Algorithm has very reasonable results, but it is very hard to find(guess) the right value of threshold. Moreover, it is also impossible to simplify each line to (for example) 40%. Exactly for such cases, v.generalize provides method=douglas_reduction. This algorithm is a modification of Douglas-Peucker Algorithm which takes another paratemer reduction which denotes (approximate) simplification of lines. For example,
v.generalize input=roads output=roads_douglas_reduction method=douglas_reduction threshold=0 reduction=50 --overwrite d.erase d.vect roads_douglas_reduction
v.generalize input=in output=out method=douglas threshold=eps v.generalize input=in output=out method=douglas_reduction threshold=eps reduction=100
Another algorithm implemented in this modules is "Vertex Reduction". This algorithm removes the consecutive poins (on the same line) which are closer to each other than threshold. For example,
v.generalize input=in output=out method=reduction threshold=0
The following four pictures show the results obtained by Reumann, Douglas, Lang
and Vertex Reduction algorithm resp. The algorithms were run with threshold set to 50
and Lang algorithm with look_ahead=7. The map produced by Reumann-Witkam algorithm contains 2522[46%] points,
Douglas: 2107[38%] points, Lang: 2160[39%] and Vertex Reduction: 4296[78%].
v.generalize also supports many smoothing algorithm. For basic descriptions, please consult the man page.
Probably, the best results are produced by "Chaiken", "Hermite" and "Snakes" algorithms/methods. However, the remaining algorithms may also produce very reasonable results. Although the Chaiken and Hermite methods may produce the maps with a lot of new points, the methods presented above (simplification) provide a good tool for tackling this problem.
If we run the following command
v.generalize input=roads output=roads_chaiken method=chaiken threshold=1
d.erase d.vect roads d.vect roads_chaiken col=blue
v.generalize input=roads output=roads_hermite method=hermite threshold=1
The algorithms mentioned above are suitable for smooth approximation of given lines. On the other hand, if the aim of smoothing is to "straighten" the lines then the better results are achieved by the other methods. For example,
v.generalize input=roads output=roads_sa method=sliding_averaging look_ahead=7 slide=1
Very similar results can be obtained by Distance Weighting Algorithm (method=distance_weighting). This is not very surprising since these algorithms are almost the same. For example, the image below shows the outputs of "Distance Weighting Algorithm". The image was generated by the following sequence of commands
v.generalize input=roads output=roads_dw1 method=distance_weighting look_ahead=7 slide=1 v.generalize input=roads output=roads_dw2 method=distance_weighting look_ahead=7 slide=0.3 d.erase d.vect roads d.vect roads_dw1 col=red d.vect roads_dw2 col=blue
v.generalize input=roads output=roads_snakes method=snakes alpha=1 beta=1
Last smoothing algorithm implemented in this module is "Boyle's Forward-Looking Algorithm" which is another "straightening" algorithm.
v.generalize input=roads output=roads_boyle method=boyle look_ahead=5
If we render entire Spearfish location, we can see in the upper half of the map two interstates which overlap. This is not logically correct (I hope, they do not evarlap in real) and it is also considered as an (presentation) error. For solving such problems, v.generalize provides "dislplacement" method. As the name suggests, this method displaces linear features which are close to each other so that they do not overlap/collide. Method implemented in this modules (based on Snakes) has very good results but not very good perfomance. Therefore the calculations may take few(several) minutes. For this reason, displacement is applied to the simplified lines in this document.
v.generalize input=roads output=roads_dr method=douglas_reduction threshold=0 reduction=50 v.generalize input=roads_dr output=roads_dr_disp method=displacement alpha=0.01 beta=0.01 threshold=100 iterations=35
Network generalization is suitable for selecting "the most important" subnetwork of a network. For example, to select highways, interstates from a road network. Examples in this section work with new GRASS default dataset, which can be downloaded here.
If we render map "streets_wake" we really cannot see the streets, but the only thing we can see is a big black rhombus. We will try to improve this. Firstly, network generalization requites quite a lot of time and memory. Therefore, we begin with simplification of "streets_wake":
v.generalize input=streets_wake output=streets_rs method=remove_small threshold=50
v.generalize input=streets_rs output=streets_rs_network method=network betweeness_thresh=50
v.generalize has some parameters and flags which affect the general behaviour of module.
The simplest one is -c flag. "C" stands for copy and if this flag is on then the attributes are copied from the old map to the new map. Note that the attributes of removed features are dropped.
Default behaviour of this module is that the selected algorithm/method is applied to the all lines/areas. It is possible to apply the most of the algorithms only to the selected features. This is achieved by "type", "layer", "cats" and "where" parameters. This works for all algorithms except "Network Generalization" which is always applied to the all features. For example, the following command applies "Douglas Reduction" algorithm to interstates and highways (cat<3) and leaves the other lines unaltered. It also copies the attributes
v.generalize -c input=roads output=roads_douglas_reduction2 method=douglas_reduction threshold=0 reduction=50 type=line where="cat<3"
v.generalize input=soils output=soils_remove_small method=remove_small threshold=200 type=area
v.generalize input=roads output=roads_displacement2 method=displacement threshold=75 alpha=0.01 beta=0.01 iterations=20 cats=1
We end up with a complex example of a generalization of "roads" in Spearfish location.
#straighten the lines v.generalize input=roads output=step1 method=snakes alpha=1 beta=1 #simplification v.generalize input=step1 output=step2 method=douglas_reduction threshold=0 reduction=55 #displacement v.generalize input=step2 output=step3 method=displacement alpha=0.01 beta=0.01 threshold=100 iterations=50 #remove small areas v.generalize input=step3 output=step4 method=remove_small threshold=75 #network generalization v.generalize input=step4 output=step5 method=network betweeness_thresh=5 closeness_thresh=0.0425 #smoothing v.generalize input=step5 output=step6 method=chaiken threshold=1 #simplification v.generalize input=step6 output=step7 method=douglas threshold=1 #remove temporary maps g.remove vect=step1,step2,step3,step4,step5,step6
Last changed: $Date: 2007/08/20 18:21:12 $