Research On Deriving The Conceptual Neighborhood Graphs Of Topological Relations Between Regions With Holes Automatically

The object in life is complex. For example, the planar region is complex withholes, or some separate sub-sections. Such as there is a small lake in the central of thepark or there is number of separate islands in some countries. In order to meet theactual application requirements, the study of spatial relationships from the simplerelationship between the spatial object are gradually towards to the development ofrelationships between complex spatial objects.Previous studies focused on the relationship between simple spatial objects, theyare topology, direction, measure the relationship, sequence and so on. Therepresentative of models of topological relations are the4-/9-/9-intersection modelwhich is based on point set topology proposed by Egenhofer, Randell and Clarke’sRCC-8(Region Connection Calculus)which is on the basis of space calculus logicaxiom. Complex spatial objects and their relationships reasoning is becoming a focusfor researchers to present, most studies have focused on the holey area witch havemultiple disconnected sub-part of the objects and their relationships.With the rapid development of spatial and temporal reasoning, conceptualneighborhood graph gains more and more attention. The conceptual neighborhoodgraph is the collection of the concept of neighbor relations connected with the graphstructure. The conceptual neighborhood graph for the temporal and spatial databasequeries, the classification of topological relations between spatial objects and spacescenes conversion judgment. The objects witch conceptual neighborhood graphstudied are from simple lines to regions and more complex spatial objects.In this paper, we will study and give a discussion in two aspects about thederivation of the conceptual neighborhood graph between complex spatial objectrelations.1. In order to derive the concept neighborhood automatically, we need anappropriate relationship model of the representation. We choose the n-intersectionmodel, and extend it. The two sides of intersectional elements are divided in more detail. And we give the15-intersection representation about the relations between asimple region and a region with a hole.2. In the spirit of the idea from simple to complex, we apply the algorithmproposed by Kurata to more complex spatial objects. Based on the previoustheoretical studies we split the space object into a few simple objects, and then studyeach neighborhood of the relation between simple object and simple object, and thencompose the two neighborhood of simple object-simple object into the conceptneighborhood automatically. We give the algorithm to derive the conceptneighborhood of the relations between simple region and region with a hole.The specific work and research results of this paper are as follows1. Summarize and analyze the research status of conceptual neighborhood graphabout spatial relationships between objects, the background and significance of thisarticle.2. Descript the theoretical basis this work related. Introduce the9-/+-intersectionmodel from relational models about object space, the tRRh model about the relationsbetween simple region and a region with a hole. Introduce the concept neighborhoodgraph derived semi-automatically proposed by Kurata which applied to topologicalrelations based on9-intersection and Max J. Egenhofer’s theories about conceptneighborhood graph of the relations of region-region by deformation strategy.3. Based on the idea of Egenhofer, we propose to use the intersection betweenprimitives to represent complex topological relations, and give the representationmodel. According to the characteristic of a hole,3×5topological relation matrixrepresentation are gained4. Based on the theory of Kurata etc, we give another automatic deduction aboutconceptual neighborhood graph of topological relations, It is more complex thanKurata’s, and give the derivation of the concept neighborhood graph between a simpleregion and a region with a hole as instance We get the conceptual neighborhood graphof RCC23, and compared with other relevant algorithms: it have wider range ofapplications than Kurata and achieve semi-automatically.5. Finally, we design and implement a demonstration system for deriving theconcept neighborhood graph of the relations RCC8represented by9-intersectionaland the relations between a simple region and a region with a hole represented by3×5matrix.In order to derive the concept of neighborhood graph of the topological relations expediently, this article uses the n-intersection model to represent the topologicalrelations between complex objects.3×5intersection matrix is proposed based on theEgenhofer’s tRRh model. There are23kinds of topological relations between thesimple region and region with a hole, and93kinds of topological relations between asimple unclosed curve and region with a hole. We extend Kurata’s method to theregion with holes, and get the method of deriving concept neighborhood graph oftopological regions between the complex spatial objects. We achieve a demonstratesystem about how to derive the conceptual neighbor of the topological relationsbetween region with holes and complex spatial objects. It is able to query theconceptual neighbor of the relations between simple objects and region-region with ahole. The practical significance of this study is on the temporal and spatial reasoning,and geographic information query and so on.