analysis. With the quadtree searching algorithm, regardless of the region of interest, the 
search always starts from the root which includes the entire spatial extent of a library and 
traverses the tree until a match occurs. If the interest of a user is very localized, then the 
searching algorithm should somehow bubble up all the information of the localized area 
near the root of the tree for faster access. This is the basis of the splay tree searching 
algorithm. A binary tree is built in which the nodes are pointers to quadtree cells, with the 
most-recently accessed cells being nearest to the root of the splay tree. For more 
discussion, see (Cobb 1995). 
In the Figure 2, implementation of spatial indexing scheme can be seen at the top 
right rectangle. Each instance of the VPFSpatialDataCeh has variables of a collection of 4 
sub-cells representing the 4 quadrants, a collection of features, identification of its level 
from the root and the super cell. The collection of features provides all the features whose 
bounding rectangles are contained within this cell. Each feature in this collection has its 
complete information, both spatial and non-spatial. 
A working model of OVPF that is integrated with the ObjectStore ODBMS, has a 
separate spatial index for each coverage. This can be seen in Figure 3. As shown, there 
Figure 3. ObjectStore Database Segments 
are four physical groupings of objects (called segments in ObjectStore). The default 
segment stores the database metadata. The spatial segment stores data relating to the spatial 
index. The feature segment stores all feature-level (non-spatial) data. Finally, the primitive 
segment stores all graphic primitive (spatial) data. As seen in Figure 3, the primld of the 
Prim Segment has a pointer to SpatialDataMgr of the Spatial Segment. This implies a 
possibility to implement a different spatial indexing scheme for each feature coverage. 
4. WINGED-EDGE TOPOLOGY 
Currently, four levels of topology are defined in VPF: