STRIP TREES: A Hierarchical Representation for Map Features.
Abstract
There is increasing interest in map features such as points, lines and regions both as a pictoral data base for resource management and as an aid to identifying objects in aerial images. Owing to the very large amount of data involved, and the need to perform operations on this data efficiently, the representation of such features is a crucial issue. We describe a hierarchical representation of map features that consists of binary trees with a special datum at each node. This datum is called a strip and the tree that contains such data is called a strip tree. Lower levels in the tree corresponds to finer resolution representations of the map feature. The strip tree structure is a direct consequence of using the method for digitizing lines given by Duda & Hart, 1973; Turner, 1974; Douglas & Peucker, 1973) and retaining all intermediate steps. This representation has several desirable properties. For features which are well-behaved, calculations such as point-membership and intersection can be resolved in 0(logn) where n is the number of feature points. The map features can be efficiently encoded and displayed at various resolutions.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1978
- Accession Number
- ADA071124
Entities
People
- Dana H. Ballard
Organizations
- University of Rochester