This thesis presents a novel 3D R-tree data structure for the efficient spatial indexing and searching of X3DOM scenes in HTML5-capable browsers. Its applicability is further boosted through the provision of a modular model for the implication of spatial relations between the 3D dataset, while experimental evaluation pointed out its computational speed and independency of the underlying platform.
Spatial Indexing
The spatial indexing of X3D objects takes place with the assistance of a 3D R-tree data structure, which has its algorithmic operations based on slightly modified versions of the Insertion and Quadratic strategies proposed by Guttman in the original R-tree index structure.
Spatial Searching
The implemented 3D R-tree structure provides the three most commonly used types of queries for the sufficient spatial searching into the indexed dataset. These queries are none others than the Point, Region, and k-NN queries where each one comes with a carefully designed tree traversing methodology.
Spatial Relations
Any 3D R-tree instance integrates a computational model for the automated implication of spatial relations between its indexed 3D objects. Such relations come in the form of spatial operators which are divided into topological and directional relations. Amongst them, topological relations comply with DE-9IM standard to deduct Disjoint, Touch, Equal, Contains, Covers, Within, CoveredBy and Overlap relations, while directional relations make use of similar boundary representation methodologies to infer Left, Right, Above, Below, Over, Front and Behind relations.
