Next: Digitizing.
Up: Geometric problems in
Previous: Data Structure Tuning.
Since almost all GIS systems allow a user to zoom in on data, there is
no intrinsic scale associated with the computer representation of a
map. Nevertheless, there is an associated level of detail which
determines a range of scales at which the data can be displayed
without being too crowded or too sparse. Generalization is the
process whose goal is to extend this range [23].
Several geometric
problems fall under the heading of generalization:
- LINE SIMPLIFICATION:
- Approximate a polygonal line by one with
less data (but hopefully the same information). This is has been the
subject of much research in
GIS, image processing, and computational
geometry. Interesting
problems remain for simplifying several lines (as in a contour map) or
for demanding topological properties (e.g., forbidding
self-intersection) from the result.
- CLUSTERING:
- Separate geometric objects can be aggregated and
represented symbolically as a polygon or as a point.
- DISTORTION:
- Moving or changing the representation of geometric
objects to enhance readability of the output. A railway that
parallels a river may need to be displayed at lower resolution. A
driver would prefer that a winding mountain road have some bends
exaggerated on a map rather than being simplified to a line segment.
The more advanced generalization tasks are difficult to define a
precise geometric optimization problems. Automating these tasks is
often seen as an application for artificial intelligence techniques
and ``knowledge-based'' heuristics. Computational geometry can offer
not only efficient implementation of lower-level primitives, but also
structures such as Voronoi diagrams and constrained triangulations that
provide a more continuous model of space.