![GRASS logo](grass_logo.png)
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,...]
- Feature type
- 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.generalise
is a module for the generalization of GRASS vector maps. This module
consists of algorithms for line simplification, line smoothing,
network generalization and displacement (new methods may be added later).
For more examples and nice pictures, see
tutorial
NOTES
(Line) simplification is a process of reducing the complexity of vector features.
The module transforms a line into another line consisting of fewer vertices, that
still approximate the original line. Most of the algorithms described below
select a subset of points on the original line.
(Line) smoothing is a "reverse" process which takes as input a line and
produces a smoother approximate of the original.
In some cases, this is achieved by inserting new vertices into the original line, and can
total up to 4000% of the number of vertices in the original. In such an instance,
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.generalise contains following line simplification algorithms:
- Douglas-Peucker Algorithm
- "Douglas-Peucker Reduction Algorithm"
- Lang Algorithm
- Vertex Reduction
- Reumann-Witkam Algorithm
- Remove Small Lines/Areas
Different algorithms require different parameters, but all the algorithms have
one parameter in common: the threshold parameter. In general, the degree
of simplification increases with the increasing value of threshold.
If the -r flag is passed, simplified lines that become shorter becomes shorter than the
threshold value are removed. Additionally, if the type parameter contains area
and a simplification algorithm is selected, then areas less than threshold are also removed.
ALGORITHM DESCRIPTIONS
- Douglas-Peucker - "Quicksort" of line simplification, the most widely used
algorithm. Input parameters: input, threshold. For more
information, please see: http://geometryalgorithms.com/Archive/algorithm_0205/algorithm_0205.htm.
- Douglas-Peucker Reduction Algorithm is essentially the same algorithm as the
algorithm above, the difference being that it takes additional reduction parameter
which denotes the percentage of the number of points on the new line with respect
to the number of points on the original line. Input parameters: input,
threshold, reduction.
- Lang - Another standard algorithm. Input parameters: input, threshold, look_ahead.
For an excellent description, see: http://www.sli.unimelb.edu.au/gisweb/LGmodule/LGLangVisualisation.htm.
- Vertex Reduction - Simplest among the algorithms. Input parameters: input, threshold.
Given a line, this algorithm removes the points of this line which are closer to each other than threshold.
More precisely, if p1 and p2 are two consecutive points, and the distance between p2 and p1 is less
than threshold, it removes p2 and repeats the same process on the remaining points.
- Reuman-Witkam - Input parameters: input, threshold. This algorithm quite
reasonably preserves the global characteristics of the lines. For more information
see http://www.ifp.uni-stuttgart.de/lehre/vorlesungen/GIS1/Lernmodule/Lg/LG_de_6.html(german)
- Remove Small Lines/Areas - removes the lines (strictly) shorter than threshold and areas (strictly) less than threshold.
Other lines/areas/boundaries are left unchanged. Input parameters: input, threshold
Douglas-Peucker and Douglas-Peucker Reduction Algorithm use the same method
to simplify the lines. Note that
v.generalise input=in output=out method=douglas threshold=eps
is equivalent to
v.generalise 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.generalise 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.generalise
- Boyle's Forward-Looking Algorithm - The position of each point depends on the
position of the previous points and the point look_ahead ahead.
look_ahead consecutive points. Input parameters: input, look_ahead.
- McMaster's Sliding Averaging Algorithm - Input Parameters: input, slide, look_ahead.
The new position of each point is the average of the look_ahead points around. Parameter slide
is used for linear interpolation between old and new position (see below).
- McMaster's Distance-Weighting Algorithm - Works by taking the weighted average of look_ahead consecutive points
where the weight is the reciprocal of the distance from the point to the currently smoothed point. And parameter slide is used
for linear interpolation between the original position of the point and newly computed position where value 0 means the original position.
Input parameters: input, slide, look_ahead.
- Chaiken's Algorithm - "Inscribes" a line touching the original line such that the points on this new line
are at least threshold apart. Input parameters: input, threshold. This algorithm
approximates the given line very well.
- Hermite Interpolation - This algorithm takes the points of the given line as the control
points of hermite cubic spline and approximates this spline by the points approximately threshold apart.
This method has excellent results for the small values of threshold, but in this case it produces
a huge number of new points and some simplification is usually needed. Input parameters: input, threshold, angle_thresh.
Angle_thresh is used for reducing the number of the outputed points. It denotes the minimal
angle (in degrees) between two consecutive segments of line.
- Snakes is the method of minimisation of the "energy" of the line. This method preserves the
general characteristics of the lines but smooths the "sharp corners" of the line. Input parameters input, alpha, beta.
This algorithm works very well for small values of alpha and beta (between 0 and 5). These
parameters affects the "sharpness" and the curvature of the computed line.
One of the key advantages of Hermite Interpolation is the fact that the computed line
always passes through 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
a line which "circumscribes" the input line.
On the other hand, Chaiken's Algorithm outputs a line which "inscribes" a given line.
The output line always touches/intersects the centre of the input 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 the two algorithms given above 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 sometimes used in the signal processing to smooth the signals.
More importantly, these algorithms never change the number of points on the lines; they only
translate the points, and 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 overlap and/or are close to each other at the current
level of detail. In general, displacement methods moves 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 generally yields 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:
-
threshold - specifies critical distance. Two features interact if they are
closer than threshold apart.
-
alpha, beta - These parameters define the rigidity of lines. For greater
values of alpha, beta (>=1), the algorithm does a better job at retaining the original
shape of the lines, possibly at the expense of displacement distance. If the values of alpha,
beta are too small (<=0.001), then the lines are moved sufficiently, but the geometry and topology of lines can
be destroyed. Most likely the best way to find the good values of alpha, beta
is by trial and error.
-
iterations - denotes the number of iterations the interactions between
the lines are resolved. Good starting points for values of iterations are between 10 and 100.
The lines affected by the algorithm can be specified by the layer,
cats and where parameters.
NETWORK GENERALIZATION
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:
-
degree_thresh - algorithm selects only the lines which share a point
with at least degree_thresh different lines.
-
closeness_thresh - is always in the range (0, 1]. Only the lines with
the closeness centrality value at least closeness_thresh apart are selected.
The lines in the centre of a network have greater values of this measure than
the lines near the border of a network. This means that this parameter can be used
for selecting the centre(s) of a network. Note that if closeness_thresh=0 then everything is selected.
-
betweeness_thresh - Again, only the lines with a betweeness centrality
measure at least betweeness_thresh are selected. This value is always
positive and is larger for large networks. It denotes to what extent a line
is in between the other lines in the network. This value is great for the lines
which lie between other lines and lie on the paths between two parts of a network.
In the terminology of the road networks, these are highways, bypasses, main roads/streets, etc.
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.clean,
v.dissolve
v.generalize Tutorial (from GRASS-Wiki)
AUTHORS
Daniel Bundala, Google Summer of Code 2007, Student
Wolf Bergenheim, Mentor
Last changed: $Date: 2009-10-10 07:37:03 -0700 (Sat, 10 Oct 2009) $
Main index - vector index - Full index
© 2003-2010 GRASS Development Team