1v.generalize(1) Grass User's Manual v.generalize(1)
2
6 v.generalize - Vector based generalization.
7
9 vector, generalization, simplification, smoothing, displacement, net‐
10 work generalization
11
13 v.generalize
14 v.generalize help
15 v.generalize [-cr] input=name output=name [type=string[,string,...]]
16 method=string threshold=float look_ahead=integer reduction=float
17 slide=float angle_thresh=float degree_thresh=integer close‐
18 ness_thresh=float betweeness_thresh=float alpha=float beta=float itera‐
19 tions=integer [layer=integer] [cats=range] [where=sql_query]
20 [--overwrite] [--verbose] [--quiet]
21 Flags:
23 -c
24 Copy attributes
25 -r
27 Remove lines and areas smaller than threshold
28 --overwrite
30 Allow output files to overwrite existing files
31 --verbose
33 Verbose module output
34 --quiet
36 Quiet module output
37 Parameters:
39 input=name
40 Name of input vector map
41 output=name
43 Name for output vector map
44 type=string[,string,...]
46 Type
47 Feature type(s)
48 Options: line,boundary,area
49 Default: line,boundary,area
50 method=string
52 Generalization algorithm
53 Options: douglas,douglas_reduction,lang,reduc‐
54 tion,reumann,remove_small,boyle,sliding_averaging,distance_weight‐
55 ing,chaiken,hermite,snakes,network,displacement
56 Default: douglas
57 douglas: Douglas-Peucker Algorithm
58 douglas_reduction: Douglas-Peucker Algorithm with reduction parame‐
59 ter
60 lang: Lang Simplification Algorithm
61 reduction: Vertex Reduction Algorithm eliminates points close to
62 each other
63 reumann: Reumann-Witkam Algorithm
64 remove_small: Removes lines shorter than threshold and areas of
65 area less than threshold
66 boyle: Boyle's Forward-Looking Algorithm
67 sliding_averaging: McMaster's Sliding Averaging Algorithm
68 distance_weighting: McMaster's Distance-Weighting Algorithm
69 chaiken: Chaiken's Algorithm
70 hermite: Interpolation by Cubic Hermite Splines
71 snakes: Snakes method for line smoothing
72 network: Network generalization
73 displacement: Displacement of lines close to each other
74 threshold=float
76 Maximal tolerance value
77 Options: 0-1000000000
78 Default: 1.0
79 look_ahead=integer
81 Look-ahead parameter
82 Default: 7
83 reduction=float
85 Percentage of the points in the output of 'douglas_reduction' algo‐
86 rithm
87 Options: 0-100
88 Default: 50
89 slide=float
91 Slide of computed point toward the original point
92 Options: 0-1
93 Default: 0.5
94 angle_thresh=float
96 Minimum angle between two consecutive segments in Hermite method
97 Options: 0-180
98 Default: 3
99 degree_thresh=integer
101 Degree threshold in network generalization
102 Default: 0
103 closeness_thresh=float
105 Closeness threshold in network generalization
106 Options: 0-1
107 Default: 0
108 betweeness_thresh=float
110 Betweeness threshold in network generalization
111 Default: 0
112 alpha=float
114 Snakes alpha parameter
115 Default: 1.0
116 beta=float
118 Snakes beta parameter
119 Default: 1.0
120 iterations=integer
122 Number of iterations
123 Default: 1
124 layer=integer
126 Layer number
127 A single vector map can be connected to multiple database tables.
128 This number determines which table to use.
129 Default: 1
130 cats=range
132 Category values
133 Example: 1,3,7-9,13
134 where=sql_query
136 WHERE conditions of SQL statement without 'where' keyword
137 Example: income = 10000
138
140 v.generalize is module for generalization of GRASS vector maps. This
141 module comprises a bunch of algortihms for line simplification, line
142 smoothing, network generalization and displacemet. (New methods may be
143 added later) Also, this document contains only the descriptions of mod‐
144 ule and implemented methods. For more examples and nice pictures, check
145 tutorial
146
149 (Line) simplification is a process of reducing the compexity of vector
150 features. It transforms a line into another line which consists of
151 fewer vertices but still approximates the original line. The most of
152 the algorithms described below selects a subset of points of the origi‐
153 nal line.
154 On the other hand, (line) smoothing is a "reverse" process which takes
156 as an input a line and produces smoother line which approximates the
157 original line. In some cases, this is achieved by inserting new ver‐
158 tices into the line. Sometimes, the increase of the number of vertices
159 is dramatical (4000%). When this situation occurs, it is always a good
160 idea to simplify the line after smoothing.
161 Smoothing and simplification algorithms implemented in this module work
163 line by line. i.e simplification/smoothing of one line does not affect
164 the other lines. They are treated separately. Also, the first and the
165 last point of each line is never translated and/or deleted.
166
168 v.generalize contains following line simplification algorithms
169 Douglas-Peucker Algorithm "Douglas-Peucker Reduction Algorithm"
170 Lang Algorithm Vertex Reduction Reumann-Witkam Algorithm Remove
171 Small Lines/Areas
172 Different algorithms require different parameters, but all the algo‐
173 rithms have one parameter in common. It is threshold parameter. In gen‐
174 eral, the degree of simplification increases with the increasing value
175 of threshold.
176 The following happens if r flag is presented. If some line is simpli‐
177 fied and hence becomes shorter than threshold then it is removed. Also,
178 if type contains area and a simplification algorithm is selected, the
179 areas of area less than threshold are also removed.
180
182 Douglas-Peucker - "Quicksort" of line simplification, the most
183 widely used algorithm. Input parameters: input, threshold. For
184 more information, please check: http://geometryalgo‐
185 rithms.com/Archive/algorithm_0205/algorithm_0205.htm. Douglas-
186 Peucker Reduction Algorithm is essentially the same algorithm as
187 the algorithm above. The difference is that it takes additional
188 parameter reduction which denotes the percentage of the number
189 of points on the new line with respect to the number of points
190 on the original line. Input parameters: input, threshold, reduc‐
191 tion. Lang - Another standard algorithm. Input parameters:
192 input, threshold, look_ahead. For an excellent description,
193 check: http://www.sli.unimelb.edu.au/gisweb/LGmodule/LGLangVisu‐
194 alisation.htm. Vertex Reduction - Simplest among the algo‐
195 rithms. Input parameters: input, threshold. Given line, this
196 algorithm removes the points of this line which are closer to
197 each other than threshold. Precisely, if p1 and p2 are two con‐
198 secutive points and distance between p2 and p1 is less than
199 threshold, it removes p2 and repeats the same process on the
200 remaining points. Reuman-Witkam - Input parameters: input,
201 threshold. This algorithm quite reasonably preserves the global
202 characteristics of the lines. For more information check
203 http://www.ifp.uni-stuttgart.de/lehre/vorlesungen/GIS1/Lernmod‐
204 ule/Lg/LG_de_6.html(german) Remove Small Lines/Areas - removes
205 the lines (strictly) shorter than threshold and areas of area
206 (strictly)less than threshold. Other lines/areas/boundaries are
207 left unchanged. Input parameters: input, threshold
208 Douglas-Peucker and Douglas-Peucker Reduction Algorithm use the same
210 method to simplify the lines. Note that
211 v.generalize input=in output=out method=douglas threshold=eps
212 is equivalent to
213 v.generalize input=in output=out method=douglas_reduction threshold=eps
214 reduction=100
215 However, in this case, the first method is faster. Also observe that
216 douglas_reduction never outputs more vertices than douglas. And that,
217 in general, douglas is more efficient than douglas_reduction. More
218 importantly, the effect of
219 v.generalize input=in output=out method=douglas_reduction threshold=0
220 reduction=X
221 is that 'out' contains approximately only X% of points of 'in'.
222
224 The following smoothing algorithms are implemented in v.generalize
225 Boyle's Forward-Looking Algorithm - The position of each point
226 depends on the position of the previous points and the point
227 look_ahead ahead. look_ahead consecutive points. Input parame‐
228 ters: input, look_ahead. McMaster's Sliding Averaging Algorithm
229 - Input Parameters: input, slide, look_ahead. The new position
230 of each point is the average of the look_ahead points around.
231 Paremeter slide is used for linear interpolation between old and
232 new position (see below). McMaster's Distance-Weighting Algo‐
233 rithm - Works by taking the weighted average of look_ahead con‐
234 secutive points where the weight is the reciprocal of the dis‐
235 tance from the point to the currently smoothed point. And param‐
236 eter slide is used for linear interpolation between the original
237 position of the point and newly computed position where value 0
238 means the original position. Input parameters: input, slide,
239 look_ahead. Chaiken's Algorithm - "Inscribes" a line touching
240 the original line such that the points on this new line are at
241 least threshold apart. Input parameters: input, threshold. This
242 algorithm approximates given line very well. Hermite Interpola‐
243 tion - This algorithm takes the points of the given line as the
244 control points of hermite cubic spline and approximates this
245 spline by the points approximatelly threshold apart. This
246 method has excellent results for the small values of threshold,
247 but in this case it produces a huge number of new points and
248 some simplification is usually needed. Input parameters: input,
249 threshold, angle_thresh. Angle_thresh is used for reducing the
250 number of the outputed points. It denotes the minimal angle (in
251 degrees) between two consecutive segements of line. Snakes is
252 the method of minimization of the "energy" of the line. This
253 method preserves the general characteristcs of the lines but
254 smooths the "sharp corners" of the line. Input parameters input,
255 alpha, beta. This algorithm works very well for small values of
256 alpha and beta (between 0 and 5). These parameters affects the
257 "sharpness" and the curvature of the computed line.
258 One of the key advantages of Hermite Interpolation is the fact that the
260 computed line always passes throught the points of the original line
261 whereas the lines produced by the remaining algorithms never pass
262 through these points. In some sense, this algorithm outputs the line
263 which "circumsrcibes" given line. On the other hand, Chaiken's Algo‐
264 rithm outputs the line which "inscribes" given line. Moreover this line
265 always touches/intersects the centre of the line segment between two
266 consecutive points. For more iterations, the property above does not
267 hold, but the computed lines are very similar to the Bezier Splines.
268 The disadvantage of these two algorithm is that they increase the num‐
269 ber of points. However, Hermite Interpolation can be used as another
270 simplification algorithm. To achieve this, it is necessary to set
271 angle_thresh to higher values (15 or so).
272 One restriction on both McMasters' Algorithms is that look_ahead param‐
274 eter must be odd. Also note that these algorithms have no effect if
275 look_ahead = 1.
276 Note that Boyle's, McMasters' and Snakes algorithm are sometime used in
278 the signal processing to smooth the signals. More importantly, these
279 algorithms never change the number of points on the lines. i.e they
280 only translate the points, they do not insert any new points.
281 Snakes Algorithm is (asymptotically) the slowest among the algorithms
283 presented above. Also, it requires quite a lot of memory. This means,
284 that it is not very efficient for maps with the lines consisting of
285 many segments.
286
288 The displacement is used when the lines (linear features) interact
289 (overlap and/or are close to each other) at the current level of
290 detail. In general, displacement methods, as name suggests, move the
291 conflicting features apart so that they do not interact and can be dis‐
292 tinguished.
293 This module implements algorithm for displacement of linear features
295 based on the Snakes approach. This method has very good results. How‐
296 ever, it requires a lot of memory and is not very efficient.
297 Displacement is selected by method=displacement. It uses following
299 parameters:
300 threshold - specifies critical distance. Two features interact
301 iff they are closer than threshold appart. alpha, beta - These
302 parameters define the rigidity of lines. For greater values of
303 alpha, beta (>=1), the algorithm better preserves the original
304 shape of the lines. On the other hand, the lines may not be move
305 enough. If the values of alpha, beta are too small (<=0.001)
306 then the lines are moved sufficiently, but the geometry and
307 topology of lines can be destroyed. Probably, the best way to
308 find the good values of alpha, beta is by trial and error.
309 iterations - denotes the number of iterations the interactions
310 between the lines are resolved. Mostly, good values of itera‐
311 tions lies between 10 and 100.
312 The lines affected by the algorithm can be specified by the layer, cats
314 and where parameters.
315
317 Is used for selecting "the most important" part of the network. This is
318 based on the graph algorithms. Network generalization is applied if
319 method=network. The algorithm calculates three centrality measures for
320 each line in the network and only the lines with the values greater
321 than thresholds are selected. The behaviour of algorithm can be
322 altered by the following parameters:
323 degree_thresh - algorithm selects only the lines which share a
324 point with at least degree_thresh different lines. close‐
325 ness_thresh - is always in the range (0, 1]. Only the lines with
326 the closeness centrality measure at least closeness_thresh are
327 selcted. The lines in the centre of a network have greater val‐
328 ues of this measure then the lines near the border of a network.
329 This means, that this parameters can be used for selecting the
330 centre(s) of a network. Note that if closeness_thresh=0 then
331 everything is selected. betweeness_thresh - Again, only the
332 lines with betweeness centrality measure at least betwee‐
333 ness_thresh are selected. This value is always positive and is
334 larger for large networks. It denotes to what extent a line is
335 in between the other lines in the network. This value is great
336 for the lines which lie between other lines and lie on the paths
337 between two parts of a network. In the terminology of the road
338 neworks, these are highways, bypasses, main roads/streets....
339 All three parameters above can be presented at the same time. In that
341 case, the algorithm selects only the lines which meet each criterion.
342 Also, the outputed network may not be connected if the value of betwee‐
344 ness_thresh is too large.
345
347 v.generalize Tutorial
348 v.clean
349 v.dissolve
350
353 Daniel Bundala, Google Summer of Code 2007, Student
354 Wolf Bergenheim, Mentor
355 Last changed: $Date: 2007-11-02 13:11:31 +0100 (Fri, 02 Nov 2007) $
357 Full index
359 © 2003-2008 GRASS Development Team
361GRASS 6.3.0 v.generalize(1)