Queries of nature neighbor objects on UnitsDelaunay structure in spatial database

摘要

In recent years, the research on models of spatial relation computation can be divided into two types: the spatial relation among intersected entities and the spatial relation among the non-intersected entities. Currently, the latter is often used distance, direction and coordinate systems and other methods to study. But these quantitative methods are difficult to sympathize with human natural language understanding and space cognitive habits.rnNature neighbor relationship is a vital space relationship. It can answer such questions as "Which hospital are adjacent to the moving object?" "Which schools are adjacent to the McDonald's shop?" In this paper, we analyzed two methods to compute the nature neighbor relationships: Voronoi diagram method and Delaunay triangulation method. We found the main problems for applying these methods to spatial selection are the overall and repetitive calculation. In some basic theory: (ⅰ) Define function f in order to distinct different types of triangle. According to the different sources of thernnodes, the f is individually equal to 0, 1 and 2. And then the 3x3 matrix C is built on the f According to the different values of |C|, we can divide the triangles as three types: α, β, γ. (ⅱ) Taking into account that the triangles of type α is not entirely internal concave polygon, we divide the type α into type α and δ on the condition whether the polygon includes the focus of the triangle or not. Then the D(P) composed by Q includes four types of triangles: α, β, γ and δ. (ⅲ) Demonstrate that the space scope of Q in R~2 is equal to the space scope of triangle set T of type α in D(P) , reasoned out the complement of Q in R~2 is equivalence with the set {T_β∪T_γ∪T_δ} and the nature neighbor relationship canrnonly exist in the set {T_β∪T_γ∪T_δ}. (ⅳ) For β and γ-tyPe triangle we posed a subset of their sources and demonstrated the certainty in the context of natural subset of the space adjacent to the existing relationship, and regarded the space scope of every subset as a Unit, defined the structure of UnitsDelaunay and proposed the construction algorithm of thernUnitsDelaunay. For the Quad GridFile: (ⅰ) Respectively approximated the Units composed of β and γ-tyPe triangles byrntwo methods of MBR of MCR and MBR. (ⅱ) Demonstrated the completeness of the closure of the result set of point querying. (ⅲ) Taking into account the update of GridFile, we proposed the Quad GridFile index structure, i.e. the structure added into quad tree spatial partition, replacing the update of structure by the reconstruction of GridFile structure, which the space scope of GridFile is represented by every leaf node. We utilized the extraction of candidate set of point spatial selection and self-join spatial selection as the instances. In the environment of Oracle 9.2.1 and Eclipse 3.1, we accomplished the proposed structures and related algorithm. Finally, we gave illustrations of the experimental results.