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)