Research On Qualitative Methods Of Representation And Reasoning Of Spatial Concave Objects

In recent years, researches on theory and application on spatialinformation are getting more and more attentions in ArtificialIntelligence(AI), Geographical Information System(GIS), Spatial Databaseand other relating fields. The relations of spatial objects are various, andsometimes rely on the domain specific applications. The research oncognition, description and representation of spatial relations are the basis ofan effective application. At present, there are two main methods on spatialrelation representation: logic-based methods and point-set topology basedmethods.Topological relation is the most elementary relation in space, and is oneof the basic problems in qualitative spatial reasoning. Qualitative shaperepresentation is one important aspect in qualitative reasoning. Unlike thetraditional quantitative methods, the qualitative shape measures concernmainly on abstracting and representing the qualitative properties of objects'shape. It is meaningful to apply the exiting qualitative spatial methods intothe shape representation. This paper is focused on representation andreasoning about qualitative shape, topological representation of spatialobjects.The main work and results included in this paper are as follows:Firstly, the paper summarized and analysed the state of arts inrepresentation about qualitative shape and topological relations of spatialobjects based on the two essential methods in spatial relation description. Itintroduces some basic theories including Allen's interval calculus, RegionConnection Calculus(RCC) and 9-intersection model. The relate researchworks in topological relations of spatial objects are surveyed and analyzed. Itdescribes a hierarchical representation of qualitative shape based onconnection and convexity presented by Cohn, and a process-grammar shaperepresentation methods proposed by Leyton.Secondly, this paper gave a detailed introduction of a hierarchicalrepresentation of qualitative shape based on connection and convexitypresented by Cohn. We proposed a SameSide deducing method on the basisof concavity transforming, and give the arithmetic description. Based on theessential binary relation 'connection' and the concept of 'convex hull', Cohnhad presented a hierarchical representation of qualitative shape to describemany kinds of concave regions. During the analyzing process, we found thatillogical results would be derived by directly using the SameSide predicatefor some kinds of concave regions. Based on Allen's interval algebra, wepresent a method CTS by distinguishing the type of the concavities makinguse of tangent scanning measure. The results derived from method CTSaccords with people's cognition.Thirdly, on the basis of Cohn's RCC23 and Egenhofer's 9-intersectionmodel, we proposed a model TSC, defined TSC31, and gave the conceptualneighborhood and closest topological relation graph. The RCC formal modeland 9-intersection model are the most typical theory models in therepresentation of spatial topological relations. Combining the idea of the twomethods, we constructed a model TSC. The model consists of two parts,namely the representing system and the reasoning system. Based on RCC23,we defined TSC31 by introducing eight new topological relations, and alsogave the conceptual neighborhood and closest topological relation graph ofTSC31. The model TSC is more expressive than RCC23, the topologicalrelations of two concave regions are represented more finely, thus much moreand rich spatial relations can be described. The limitation of 9-intersectionmodel is that it can only represents the topological relations between simpleconvex regions. The model TSC extends the objects into simple concaveregions. It is more general and applicable to practical application fields.Fourthly, we designed and implemented a demonstrating system ofmodel TSC. The demo system is composed of three main functions, that is,demonstrating, distinguishing and reasoning of topological relations. The partof topological relations reasoning can be applied directly to the automaticreasoning of composition table. It is of importance both in theory andapplication in some degree.The method CTS proposed in this paper increases the correctness andreasonableness of the deriving results using SameSide predicate. Based onRCC23 and 9-intersection model, we extend RCC23 by introducing eightnew topological relations besides the original 23 topological relations. Thus,it will enrich the expressive power of topological relations to some extend,obtain more spatial relations and can be the theoretical basis of automaticreasoning of composition table on topological relations.In a word, the study results of the paper are of both theoretical andpractical benefit to further researches in spatial relations on spatial reasoning,spatial query language and geographic information system (GIS).