Figure 2. Sample OVPF Objects for a DNC Coastline Feature and Its Metadata
3. SPATIAL INDEXING SCHEME
Indexes are built according to some criteria to facilitate faster retrieval of database
records. For spatial data, this criteria can be the spatial location or bounding rectangle.
Within the OVPF implementation, the quadtree indexing method (Samet, 1995) is used to
organize VPF data. This is one of most common indexing schemes used for spatial data.
The principle of this indexing scheme is based on a simple, recursive subdivision of spatial
data into four equal-sized cells or quadrants. Each feature is placed in the smallest quadtree
cell which will completely contain it. The quadtree subdivision terminates based on one of
two criteria: (1) a preset number of iterations has been reached, or (2) all the data have
been placed in a cell. In OVPF, the quadtree has been preset to not exceed 20 levels of
subdivision.
The quadtree structure has been the pre-dominant searching mechanism to access
features in the OVPF. The root of the quadtree is determined during the program
initialization. It is usually set to the spatial extent of a VPF library chosen to import. Each
feature also has its bounding rectangle defined by the VPF specification. Bounding
rectangles for area features are stored directly in the VPF source tables. However,
bounding rectangles for line features must be computed by merging the bounding
rectangles of component edges of each line feature. Bounding rectangles for point features
or node features are created by offsetting the coordinate points in four directions by a small
constant. Once the feature bounding box is known, the minimum sized quadtree cell that
can include the feature’s bounding box is determined.
With one of the working models of OVPF, an option to use a splay tree searching
algorithm is provided. A splay tree is an unbalanced binary tree in which the most-
recently-accessed node is rotated to the top of the tree. This searching algorithm works
very well given typical usage patterns for working with a spatial database. Within the GIS
community, the user tends to focus in on an area of interest for query, display, and