Orientation adaptive quadtrees
Loading...
Files
Date
1990
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This thesis addresses the area of spatial data structures. There are numerous hierarchical data structuring techniques in use for representing raster data. One commonly used method that is based on recursive decomposition is the quadtree. Its development has been motivated to a large extent by a desire to reduce the amount of space required to store raster data representations of objects. The Orientation Adaptive Quadtree (OAQ) representation is a new quadtree representation which positions the quadtree axes centered at the object's centroid and aligned with the object's principal axis of inertia. This approach is explained along with a quick method for computing the orientation of the object. Boolean operations on two OAQs representing two objects which differ in position, orientation, and resolution are also presented. The method maintains the quadtree structure, and it consists of two major operations : extracting polygons produced by intersecting every two blocks representing two specified nodes from different OAQs, and merging those polygons which results in an object to be represented as another OAQ. The result of Boolean OAQ opereation has its own orientation. O A Q representations for 17 different geographical objects are compared to their standard quadtree representations, with an average reduction of 9.5% in the number of nodes required for their representation. Two objects were also used to test the Boolean intersection and union operations on OAQs. OAQ representation of rectangular objects gives a reduction in the number of nodes of more than 80%.