The Design And Realization Of Algorithms For The Topological Relations Between Simple Spatial Objects

The research of spatial reasoning starts from 1970s. In recent years, with the development of computer graphics, computer vision, image processing, robotics, spatial database etc, there are higher requirement for spaial reasoning and its application, in which more researchers are devote to the study on this field. Spatial reasoning has become one of the hot issues.As the most basic relation in space, the topological relation plays a very important role in spatial reasoning in which the reasoning prosess is one of the elementary problems. The topological relation between lines, and between line and region are commonly used in spatial reasoning. Therefore, researches on the application of relation between lines, between line and region are of significance. There are three kinds of methods for spatial relation processing in general: intersection-based method, interaction-based method and Voronoi based method.Based on the introduction of some current research work in spatial reasoning, the LR algorithm and OR algorithm are designed and implementedand, which using Java language under the JBluider developing environment to demonstrate the operation process, and also the correctness of lemma one and lemma three are verified.The main work and results included in this paper are as follows:1) The spatial relations and its descriptions in spatial reasoning are introduced.The studies of spatial relations and its application in recent years are summarized. The major methods for handling spatial relations are discussed which include intersection-based method, interaction-based method and Voronoi based method.2) The Java language and JBluider developing environment are introduced.The advantages of Java language and JBuilder developing environment in software development are summarized. 3) The topological relations between lines, between line and region which presented by Egenhofer are introduced.The LR algorithm on relation between lines, and the OR algorithm on relation between line and region are analyzed.The definitions and lemmas of corresponding concepts are given. The main idea of the algorithm and its ADL description are also presented.4) The implementing system of LR algorithm and OR algorithm are designed and implemented.The major functions of the system which composed of demonstrating, distinguishing and reasoning of topological relations are detaily introduced. The illustrations and 9-intersection matrix of topological relation involved in operating process and the derived relations are shown in the demonstrating function. In the distinguishing function, it can be judged whether the imput relation is valid and what the relation is. It also can be determined whether the connection points are matched, and it will be hinted when an input error is accured. The LR algorithm and OR algorithm can be used to derive relation from two basic topolgical relaltion.In the distinguishing process of non-connection points, the connection points are transformed into integer, thus the boundary information are computed by applying the plus-minus method. In the modification of resulting matrix, LR algorithm adopts a combination of multi-conditional mixed judging method, while in OR algorithm the direct assignment method for non-connection points is used.5) The running results of the demontrating system are given, and the correctness of lemma one and lemma three are verified.It is illustrated that fourteen topologicl relations between line and region can be derived from five basic topological relations between line and region by applying the OR algorithm. The correctness of lemma three is verified. It is also exemplified that twenty-eight topologicl relations between lines can be derived from five basic topological relations between lines by applying the LR algorithm. The correctness of lemma one is verified. The OR algorithm and LR algorithm presented in this paper can help to the reasoning of complex relations between line and region. In the demonstrating system, operations of OR algorithm and LR algorithm are complementd. The operation matrix and resulting matrix are shown intuitively which is easy to understand.To sum up, the work of this paper is the basis for the application of the presented algorithms, which is also a foundation of future work. Thus, the work of this paper is of importance to the application of spatial reasoning to some extend.