Research On The Model Of Direction Relations And The Combination With Topological Relations

Spatial relations are the relation with spatial character between spatial objects. These relations are the bases of spatial data organizing, querying, analyzing and reasoning. Spatial relation is one of the most important theoretical problems in the fields of spatial reasoning, Geographical Information System (GIS), computer vision and spatial databases.The research on direction relations is a important area and is widely used. These researches concentrate on three basic problems of direction relations including the model of direction relations,its operations and the problem of qualitative reasoning. Direction relation matrix is the most expressive model of direction relations, but it can't be used efficiently in the operations and qualitative reasoning of direction relations. Inverse of direction relations is the basic operation, the method of the inverse of direction relations are all based on the minimum bounding rectangles(MBR), the description based on MBR ignored the shape of objects and is too coarse to take on reasoning; Researches on the qualitative reasoning of direction relations, the most efficient methods of composition is proposed by Skiadopoulos, but this method only presents the idea of composition and described it by natural language, these cause it can't be realized.Direction relation is just one side of spatial relations, many kinds of spatial relations should be considered in daily life. Topological relation is the most basic and important relation, the combination of direction relation with topological relations is very significant. Now, researches on the combination of the two relations concentrate on single-tile direction relations. Due to RCC8 is sensitive to the boundary of regions but direction relation isn't, there's no efficient method of combination of direction relation with RCC8 relations.This paper focuses on three basic problems of direction relations mentioned above, and the combination of direction relations with topological relations. The main work and results included in this paper are as follows:Firstly, there is a short introduction on background and significance of this paper. We summarized and analyzed the state of arts on the direction relation model and the combination of topological and direction relations in recent years.Secondly, introduce the model of direction relations—direction relation matrix, the model of topological relations—RCC8, the theory of rectangle relations, the operation of direction relations and the qualitative reasoning of direction relations. Until now, direction relation matrix is recognized as the most efficient model for representing direction relations and RCC8 is the best model of topological relations.Thirdly, we refined direction relation matrix to make it can be used in the operation and reasoning of direction relation matrix easily. Based on this work, we combined the method of the inverse of rectangle algebra relations with direction relation matrix, proposed the method of the inverse of direction relations. This paper gave the definition of matrices with similar positions. Through obtaining the position of a matrix, we could get all matrices with the similar positions. Through this method, we improved the coarseness of the MBR description. We realized the algorithm—Inverse and also gave the algorithm's basic idea and its ADL language description.Fourthly, We use the refined direction relation matrix formalized the method of composition proposed by Skiadopoulos, then refined the thought of composition. We proposed the method of composing direction relation matrix by usage of the minimum and maximum operator, we realized the algorithm Most, this is the basis of composition; through the definition of the power operator, we realized the algorithm of atom-basic composition called AB_Compose; then by defining the disjunction operator, we realized the algorithm of basic composition named BB_Compose; based on these works, we realized the algorithm—Compose and also gave the algorithm's basic idea and its ADL language description. The composition algorithm can give out the result of composing direction relation matrix.Fifthly, on the basis of the researches of the combination of direction with topological relations, we presented the interactive table of direction relations and topological relations. Then we proposed the expression model for the combination of direction relations with topological relations—interior-boundary direction relations, IBDR. We also gave the formal expression—D-direction relation matrix for this model. On the basis of these works, through defining the operator of combine, we presented the representation of combination of direction relations with RCC8, then gave the algorithm of the consistency checking. The uniform expression of the combinative relations establishes foundation for reasoning of combined direction-topological relations.Finally, we designed and implemented Compose algorithm and Inverse algorithm system. This system is based on the MVC design ideas, and accomplished by MATLAB R2006a technology. The modules of this system have low coupling between each other, and the interior of the modules has stronger cohesion. The whole system is of high efficiency.Firstly, we refined the direction relation matrix, enhanced its ability of expression and made it could be applied to the operation and reasoning of direction relations easily. The proposal of the method of inverse, could give a more accurate result, on the basis of this work we proposed the algorithm of inverse. The proposal of the algorithm of compose made it stepped into practical area from theory. The expression system of the combination of direction relations with topological relations can syncretize the two relations and made the combination relations could be expressed in a uniform way, the combination of the two relations increases the accuracy of expression, and establishes good foundation for formal representation and reasoning of spatial regions. In a word, the study results of this paper have both theoretical and practical benefits, it can be applied to represent and analyze the spatial relations among objects in spatial reasoning, spatial query language and geographic information system.