## Rechercher une page de manuel

# v.generalize

Langue: *en*

Version: *369880 (fedora - 01/12/10)*

Section: *1 (Commandes utilisateur)*

# Sommaire

## 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 = 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

- Douglas-Peucker Algorithm dqDouglas-Peucker Reduction Algorithm" Lang Algorithm Vertex Reduction Reumann-Witkam Algorithm Remove Small Lines/Areas

**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*- "Quicksort" of line simplification, the most widely used algorithm. Input parameters:**input**,**threshold**. For more information, please check: http://geometryalgorithms.com/Archive/algorithm_0205/algorithm_0205.htm.*Douglas-Peucker Reduction Algorithm*is essentially the same algorithm as the algorithm above. The difference is that it takes additional parameter**reduction**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, check: http://www.sli.unimelb.edu.au/gisweb/LGmodule/LGLangVisualisation.htm.*Vertex Reduction*- Simplest among the algorithms. Input parameters:**input**,**threshold**. Given line, this algorithm removes the points of this line which are closer to each other than**threshold**. Precisely, if p1 and p2 are two consecutive points and 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 check 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 of area (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.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*

*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. Paremeter**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 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 approximatelly**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 segements of line.*Snakes*is the method of minimization of the "energy" of the line. This method preserves the general characteristcs 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 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:

**threshold**- specifies critical distance. Two features interact iff they are closer than**threshold**appart.**alpha**,**beta**- These parameters define the rigidity of lines. For greater values of**alpha**,**beta**(>=1), the algorithm better preserves the original shape of the lines. On the other hand, the lines may not be move enough. 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. Probably, 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. Mostly, good values of**iterations**lies between 10 and 100.

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:

**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 measure at least**closeness_thresh**are selcted. The lines in the centre of a network have greater values of this measure then the lines near the border of a network. This means, that this parameters 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 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 neworks, these are highways, bypasses, main roads/streets....

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, StudentWolf Bergenheim, Mentor

*Last changed: $Date: 2007-11-02 13:11:31 +0100 (Fri, 02 Nov 2007) $*

Full index

© 2003-2008 GRASS Development Team

En effet, je ne prends, effrenée, le temps de chercher mes termes et de respecter les sept temps en ce bec !

-- Grivet, Claire

Contenus ©2006-2017 Benjamin Poulain

Design ©2006-2017 Maxime Vantorre