GENERALIZATION
ALGORITHMS
Karel STANĚK, Ph.D.
Simplification
 Oldest task, Perkal '58
 Three basic types
 Weeder
 Smoother
 Unrestricted
 According scope
 Local
 Global
Simplification
 Approaches
 Random
 N-th point
 Level of change
 McMaster VectGen,
Jenks
 Fixing extremes
 Lang, DP
 Eliminate unimportant
 Visvalingam
 Fractal
 Walking divider,
 Li-Openshaw
 Perkalist
 Whirlpool,EdgeBuff
Simplification
 Complications
 Self-intersection
 Spikes
 Topological inconsistency
 Unwanted exaggeration
 Smoothing eliminate some complications
 Unrestricted algorithms are usually time
consuming
 Extended data models for prevention
Buildings simplification
 Special case, rectangular shapes
 Lichtner '76
 Various approaches tested, include typification
short edge
short edge
Collaps
 Feature to point
 Area to line
 Skeleton based methods
 Various centroid based methods
Aggregation and amalgamation
 Dissolve
 Convex Hull
 Mathematical morphology
 Dilation: thicken with disc, Minkowski sum
 Erosion: make thinner by thickening outside with a
disc, Minkowski subtraction
 Opening: first erosion, then dilation (same radius
circle
 Closure: first dilation, then erosion
Mathematical morphology
Displacement
 Incremental
 Feature per feature
 Hierarchy is needed
 Diameter-centroid displacement, Focus Line
displacement
 Global
 Voronoi diagram declustering
 Risk of spatial pastern destruction
 Time consuming
VD declustering
 Set P of points:
 Compute VD of P
 Move each point to the center of gravity of its
Voronoi cel
 Iterate (recompute VD)