Accession Number:

ADA071124

Title:

STRIP TREES: A Hierarchical Representation for Map Features.

Descriptive Note:

Technical rept.,

Corporate Author:

ROCHESTER UNIV NY DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Ballard,Dana H.

Report Date:

1978-12-01

Pagination or Media Count:

40.0

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 0logn where n is the number of feature points. The map features can be efficiently encoded and displayed at various resolutions.

Descriptors:

• *DATA BASES
• IMAGE PROCESSING
• COMPUTER AIDED DESIGN
• TREES
• MAPS
• AERIAL PHOTOGRAPHS
• HIERARCHIES
• LINES(GEOMETRY)

Subject Categories:

• Cartography and Aerial Photography

Distribution Statement:

APPROVED FOR PUBLIC RELEASE