Research On Representation And Reasoning Of Topological Relation Between Simple Spatial Objects

In recent years, researches on theory and application of spatial information are getting more and more attentions in Artificial Intelligence(AI), Geographical Information System(GIS), Spatial Database and other relating fields. The relations of spatial objects are various, and sometimes rely on the domain specific applications. The research on cognition, description and representation of spatial relations are the basis of effective applications. At present, there are mainly two kinds of methods on spatial relation representation, i.e. logical and algebraic methods.Topological relation is the most elementary relation in space, and is one of the basic problems in qualitative spatial reasoning. Spatial TRLR and TRLL is one of the most important spatial relation. The representation of Spatial TRLR and TRLL is just irrelatated for every spatial relations,so it is meaningful to find the internal relation of all the spatial relations. This paper is focused on qualitative representation ,reasoning and the internal connection between spatial Line-Region and Line-Line. The paper summarized and analysed the state of arts in representation and reasoning about Topological Relations between Line and Region(TRLR), Topological Relations between Line and Line(TRLL) based on the two essential methods in spatial relation description. Based on the denotative method about spatial topological relations between line and region ,and topological relations between line and line which was presented by Egenhofer,we give them the basic set of these relations for each other ;We reason about other relations with algorithm OR and algorithm LR;We proved its correctnessabout algorithm OR and algorithm LR; At last ,we give the compositiontable between spatial topological relation about line and region and spatial topological relation about line and line.Although the research on spatial TRLR and TRLL has madeprogress,these relations are interrelate.The research on internal relation of the spatial TRLR and TRLL,the relation between TRLR and TRLL is still less.The main work and results included in this paper are as follows:Firstly, the paper summarized and analysed the state of arts in representation about qualitative topological relations of spatial objects based on the two essential methods in spatial relation description. It introduces 9-intersection model and the topological representation about spatial TRLR and TRLL.The related research works in topological relations of spatial objects are surveyed and analyzed.Secondly, Based on the denotative method about nineteen spatial topological relations between line and region which was presented by Egenhofer, this paper gave algorithm OR and five basic topological relations about line and region and proved that algorithm OR is correct. Based on the essential 9-intersection model which was the main method to represent the topological relation between line and region, Egenhofer defines nineteen topological relations between line and region. On the basis of Egenhofer's work, we find that these topological relations can be reducedto five basic topological relations. Based on the theory about matrixoperation, we brought forward algorithm OR, give the ADL representation about algorithm OR, the reasoning process and illustrating diagram that reason about other relations from five basic topological relations.Thirdly, based on the denotative method about thirty-three spatial topological relations between line and line which was put forward by Egenhofer, this paper gave algorithm LR and five basic topological relations about line and region and proved that algorithm LR is correct.By analysing the thirty-three topological relations between line and line, we find that these topological relations can be reduced to five basic topological relations. Based on the theory about matrix operation, we putforward algorithm LR, give the ADL representation about algorithm LR and the reasoning process and diagram that five basic topological relations reason about other topological relations between line and line.Fourthly, we gave the composition table between spatial TRLL and TRLR.Based on the composition table between spatial TRLR and topological relation about region and region which was presented by Alia, we analysed its reasoning process in detail and gave the composition table between 33 TRLL and 19 TRLR.Fifthly, a demonstrating system about algorithm OR and algorithm LRis designed and implemented. The demo system is composed of three main functions, that is, demonstrating, estimating and reasoning of topological relations.The algorithm OR and algorithm LR proposed in this paper increase the diversity of the reasoning method about topological relations and can be applied in path querying and composition; The five topological relations proposed in this paper equal with the spatial TRLR and TRLL in expression and make the expression terse;The composition of spatial TRLL and TRLR enrich the expressive power of topological relation to some extent and can be the theoretical basis to solve the reasoning between linear spatial object and planar spatial object. The demonstrating system about algorithm OR and algorithm LR can be applied directly to the automatic reasoning of two spatial TRLL or two spatial TRLR. It is of importance both in theory and application in some degree.In a word, the study results of the paper are of both theoretical and practical benefit to further researches in spatial relations on spatial reasoning, spatial query language and geographic information system (GIS).