R.S. Iverach, G.A. West, and S. Cox (Australia)
Boundary representation, Vertex Set extraction.
A new family of hybrid data structures, known as Dual Representation Spatial Data Structures (DRSDS), that are raster based yet explicitly incorporate boundary information, has been developed. There are a number of ways, some simple, some complex, to describe the boundaries of regions and the simplest form is the complete Vertex Set. The Vertex Set is the optimal set of points that uniquely defines the extent of the perimeter of a region in 2D and the surface of an object in 3D. This paper describes an efficient, scalable method to extract the Vertex Set from 2 and 3 dimensional DRSDS. We employ a construct based on the binary search tree called a “Nexus Tree” to retain information gathered from the input stream, which could be either a 2D EEQ (Edge Encoded Quadtree) or a 3D FEO (Face Encoded Octree). The search key for nodes stored in the Nexus Tree are Morton Numbers, which are the numbers formed by the interleaving of the coordinates that address each interesting node in the input stream. The extraction of the vertex set is achieved by an in-order traverse of the Nexus tree compiling a list of all valid Morton Indexes. The final list of Morton numbers is then converted back into spatial coordinates, which is the complete Vertex Set.
Important Links:
Go Back
