Browse Prior Art Database

STRIP TREES: A Hierarchical Representation for Map Features

IP.com Disclosure Number: IPCOM000128617D
Original Publication Date: 1978-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 15 page(s) / 42K

Publishing Venue

Software Patent Institute

Related People

Dana H. Ballard: AUTHOR [+3]

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, 19731 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. All these properties depend on the hierarchical tree structure which allows primitive operations to be performed at the lowest possible resolution with great computational savings. The strip tree representation also can allow parts of the map feature to be accessed sequentially. This feature is usually desired when the map feature is used in analyzing images. The price paid for the improved performance is an increased storage cost. .This is approximately 4n, where n is the storage needed to represent the xy coordinates. The research described in this report was supported partially by DARPA Grant #NO0014-78-C-0164 and partially by NIH Grant #R23-HL-21253-01. Page 3

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 12% of the total text.

Page 1 of 15

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

STRIP TREES: A Hierarchical Representation for Map Features

Dana H. Ballard Computer Science Department University of Rochester

TR 32 December 1978

JA0,Y

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, 19731 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. All these properties depend on the hierarchical tree structure which allows primitive operations to be performed at the lowest possible resolution with great computational savings. The strip tree representation also can allow parts of the map feature to be accessed sequentially. This feature is usually desired when the map feature is used in analyzing images.

The price paid for the improved performance is an increased storage cost. .This is approximately 4n, where n is the storage needed to represent the xy coordinates.

The research described in this report was supported partially by DARPA Grant #NO0014-78-C- 0164 and partially by NIH Grant #R23-HL-21253-01. Page 3

introduction

We present a general representation for polylines (ccnnected line segments) and areas (closed poly."Unes). Although this representation may have wide applications, its principal motivation arose from the problem of representing geographical data bases of map features.

A map has several interestinq kinds of features such as contour lines, lakes, rivers, roads, etc. These can be roughly divided into four feature classes for representation in the computer rSloan, 19781:

(Equation Omitted)

University of Rochester Page 1 Dec 31, 1978

Page 2 of 15

STRIP TREES: A Hierarchical Representation for Map Features

our main interest is in representing lines and regions. A point is such a simple datum that it can be easily treated as a primitive in any representation. Collections of points from a single class can be efficiently represented as k-d trees rBently, 1975; Barrow et.al., 1977] and so points are not the focus o...