A Hybrid Edge and Region Quadtree

摘要

The choice of spatial data structure has implications in terms of accuracy and precision but also in terms of a data storage and retrieval efficiency. The most common structures fall into one of two categories, either encoding the boundary (exterior) of an object using a vector representation or the interior, using pixels or tiles. This paper describes a quadtree variatn used to encode regional data which contains explicit edge information, and hence is readily available for use in certain GIS operations. The advantages and disadvantages of this new quadtree are examined, both in terms of algorithm performance and storage requirements. The quadtree has some interesting properties which are desiable for certain GIS operations, specifically those reliant on edge data such as dilation (buffering) and perimeter extraction. Additionally, a boundary-based representation of the quadtree can be extracted straightforwardly for use in vector-based representation of the quadtree can be extracted straightforwardly for use in vector-based algorithms. The structure, properties and algorithms relating to this new quadtree are presented.