GRASS logo

NAME

v.generalize - Vector based generalization.

KEYWORDS

vector, generalization, simplification, smoothing, displacement, network generalization

SYNOPSIS

v.generalize
v.generalize help
v.generalize [-cr] input=name output=name [type=string[,string,...]] method=string threshold=float look_ahead=integer reduction=float slide=float angle_thresh=float degree_thresh=integer closeness_thresh=float betweeness_thresh=float alpha=float beta=float iterations=integer [layer=integer] [cats=range] [where=sql_query] [--overwrite] [--verbose] [--quiet]

Flags:

-c
Copy attributes
-r
Remove lines and areas smaller than threshold
--overwrite
Allow output files to overwrite existing files
--verbose
Verbose module output
--quiet
Quiet module output

Parameters:

input=name
Name of input vector map
output=name
Name for output vector map
type=string[,string,...]
Type
Feature type(s)
Options: line,boundary,area
Default: line,boundary,area
method=string
Generalization algorithm
Options: douglas,douglas_reduction,lang,reduction,reumann,remove_small,boyle,sliding_averaging,distance_weighting,chaiken,hermite,snakes,network,displacement
Default: douglas
douglas: Douglas-Peucker Algorithm
douglas_reduction: Douglas-Peucker Algorithm with reduction parameter
lang: Lang Simplification Algorithm
reduction: Vertex Reduction Algorithm eliminates points close to each other
reumann: Reumann-Witkam Algorithm
remove_small: Removes lines shorter than threshold and areas of area less than threshold
boyle: Boyle's Forward-Looking Algorithm
sliding_averaging: McMaster's Sliding Averaging Algorithm
distance_weighting: McMaster's Distance-Weighting Algorithm
chaiken: Chaiken's Algorithm
hermite: Interpolation by Cubic Hermite Splines
snakes: Snakes method for line smoothing
network: Network generalization
displacement: Displacement of lines close to each other
threshold=float
Maximal tolerance value
Options: 0-1000000000
Default: 1.0
look_ahead=integer
Look-ahead parameter
Default: 7
reduction=float
Percentage of the points in the output of 'douglas_reduction' algorithm
Options: 0-100
Default: 50
slide=float
Slide of computed point toward the original point
Options: 0-1
Default: 0.5
angle_thresh=float
Minimum angle between two consecutive segments in Hermite method
Options: 0-180
Default: 3
degree_thresh=integer
Degree threshold in network generalization
Default: 0
closeness_thresh=float
Closeness threshold in network generalization
Options: 0-1
Default: 0
betweeness_thresh=float
Betweeness threshold in network generalization
Default: 0
alpha=float
Snakes alpha parameter
Default: 1.0
beta=float
Snakes beta parameter
Default: 1.0
iterations=integer
Number of iterations
Default: 1
layer=integer
Layer number
A single vector map can be connected to multiple database tables. This number determines which table to use.
Default: 1
cats=range
Category values
Example: 1,3,7-9,13
where=sql_query
WHERE conditions of SQL statement without 'where' keyword
Example: income < 1000 and inhab >= 10000

DESCRIPTION

v.generalize is module for generalization of GRASS vector maps. This module comprises a bunch of algortihms for line simplification, line smoothing, network generalization and displacemet. (New methods may be added later) Also, this document contains only the descriptions of module and implemented methods. For more examples and nice pictures, check tutorial

NOTES

(Line) simplification is a process of reducing the compexity of vector features. It transforms a line into another line which consists of fewer vertices but still approximates the original line. The most of the algorithms described below selects a subset of points of the original line.

On the other hand, (line) smoothing is a "reverse" process which takes as an input a line and produces smoother line which approximates the original line. In some cases, this is achieved by inserting new vertices into the line. Sometimes, the increase of the number of vertices is dramatical (4000%). When this situation occurs, it is always a good idea to simplify the line after smoothing.

Smoothing and simplification algorithms implemented in this module work line by line. i.e simplification/smoothing of one line does not affect the other lines. They are treated separately. Also, the first and the last point of each line is never translated and/or deleted.

SIMPLIFICATION

v.generalize contains following line simplification algorithms

Different algorithms require different parameters, but all the algorithms have one parameter in common. It is threshold parameter. In general, the degree of simplification increases with the increasing value of threshold.
The following happens if r flag is presented. If some line is simplified and hence becomes shorter than threshold then it is removed. Also, if type contains area and a simplification algorithm is selected, the areas of area less than threshold are also removed.

DETAIL DESCRIPTION

Douglas-Peucker and Douglas-Peucker Reduction Algorithm use the same method to simplify the lines. Note that 

v.generalize input=in output=out method=douglas threshold=eps
is equivalent to 
v.generalize input=in output=out method=douglas_reduction threshold=eps reduction=100
However, in this case, the first method is faster. Also observe that douglas_reduction never outputs more vertices than douglas. And that, in general, douglas is more efficient than douglas_reduction. More importantly, the effect of 
v.generalize input=in output=out method=douglas_reduction threshold=0 reduction=X
is that 'out' contains approximately only X% of points of 'in'.

SMOOTHING

The following smoothing algorithms are implemented in v.generalize

One of the key advantages of Hermite Interpolation is the fact that the computed line always passes throught the points of the original line whereas the lines produced by the remaining algorithms never pass through these points. In some sense, this algorithm outputs the line which "circumsrcibes" given line. On the other hand, Chaiken's Algorithm outputs the line which "inscribes" given line. Moreover this line always touches/intersects the centre of the line segment between two consecutive points. For more iterations, the property above does not hold, but the computed lines are very similar to the Bezier Splines. The disadvantage of these two algorithm is that they increase the number of points. However, Hermite Interpolation can be used as another simplification algorithm. To achieve this, it is necessary to set angle_thresh to higher values (15 or so).

One restriction on both McMasters' Algorithms is that look_ahead parameter must be odd. Also note that these algorithms have no effect if look_ahead = 1.

Note that Boyle's, McMasters' and Snakes algorithm are sometime used in the signal processing to smooth the signals. More importantly, these algorithms never change the number of points on the lines. i.e they only translate the points, they do not insert any new points.

Snakes Algorithm is (asymptotically) the slowest among the algorithms presented above. Also, it requires quite a lot of memory. This means, that it is not very efficient for maps with the lines consisting of many segments.

DISPLACEMENT

The displacement is used when the lines (linear features) interact (overlap and/or are close to each other) at the current level of detail. In general, displacement methods, as name suggests, move the conflicting features apart so that they do not interact and can be distinguished.

This module implements algorithm for displacement of linear features based on the Snakes approach. This method has very good results. However, it requires a lot of memory and is not very efficient.

Displacement is selected by method=displacement. It uses following parameters:

The lines affected by the algorithm can be specified by the layer, cats and where parameters.

NETWORK GENERALIZATION

Is used for selecting "the most important" part of the network. This is based on the graph algorithms. Network generalization is applied if method=network. The algorithm calculates three centrality measures for each line in the network and only the lines with the values greater than thresholds are selected. The behaviour of algorithm can be altered by the following parameters:

All three parameters above can be presented at the same time. In that case, the algorithm selects only the lines which meet each criterion.

Also, the outputed network may not be connected if the value of betweeness_thresh is too large.

SEE ALSO

v.generalize Tutorial
 v.clean
 v.dissolve

AUTHORS

Daniel Bundala, Google Summer of Code 2007, Student
Wolf Bergenheim, Mentor

Last changed: $Date: 2007-11-01 09:43:24 -0700 (Thu, 01 Nov 2007) $

Main index - vector index - Full index

© 2003-2008 GRASS Development Team