Research On Topological Relation Query In Three-dimensional Space

The topological relation is one of the most important spatial relations in spatialdatabase, and for the spatial data representation, storage, spatial query analysis andpractical application, it has very important significance. It is very importantespecially in the field of geographic information system (GIS) and image databaseapplication. It is often used as selected conditions in spatial inquires, and the queryefficiency of topological relationship inquires is paied close attention to by theacademic circles. At present, the research of topological query mainly concentratesin the two-dimensional space, and in three-dimensional inquirys the study isrelatively small. In this case, this paper did same related research towardsthree-dimensional topological query and explored a new three-dimensional indexstructure to support spatial query.First of all, this paper proposed a new 3D spatial CTR-tree index mechanismand its operation method. To create the structure of CTR-tree ,we use K-meansalgorithm to divide spatial objects with three-dimensional cluster grouping, then forthe packet after grouping, we establishes CTR-tree structure with 3D topologyrestriction.Secondly, Based on the defect of traditional spatial query which using only theminimum bounding box (MBB) can not accurately show the true spatial object,thereby causing the topological relation not ccurate, and we have to further inspectthe shape property, we proposed three-dimensional topology relation queryprocessing method which based on the combination of the minimum bounding boxand the maximum internal box combined abbreviate as MBB&IB method.Based on the traditional 3D topological relations query method, we add themaximal internal bounding box abbreviate as IB into the index structure, and wealso proposed 3D topological relation query processing method based on MBB&IB.We also gave the corresponding algorithm of topological operations, and throughexperimental results we proved the correctness and the integrity of the algorithm soas to the query efficiency of the method. Finally, according to the 3D topological relation query processing methodwhich based on the MBB&IB method proposed in this paper, and the using of theCTR tree index structure for three-dimensional spacial topological query, in theexperiment we compared this new method with traditional 3D query method througI/O performance contrast. The experimental results show that the proposed 3Dtopological query processing method based on MBB&IB and CTR - tree index showhigh query efficient advantages in the processing of 3D spatial topological relations.