【作者】 赵羽；

【导师】 欧阳继红；

【作者基本信息】 吉林大学 ， 软件工程， 2007， 硕士

【摘要】 目前,大多数空间关系的表示及推理主要采用逻辑方法和代数方法进行理论研究,最著名的逻辑和代数模型是Cohn等人提出的区域连接演算RCC和Egenhofer等人提出的9-交集模型。随着地理信息和空间技术的发展,空间推理的研究已成为众多领域的研究热点,如何应用空间推理理论方法解决实际问题已成为该领域迫切需要解决的问题。本文设计并实现了空间线与面、线与线的拓扑关系表示算法LR和算法OR,并通过演示结果证明了相关引理的正确性。主要工作包括:(1)对空间推理进行了介绍,重点介绍了空间关系描述及其研究的现状;(2)对Java语言及Jbluider进行了介绍和分析;(3)详细介绍了OR算法和LR算法及相关定义;(4)设计并实现了LR算法和OR算法演示系统;(5)通过演示结果证明了相关引理的正确性。本文实现的OR算法与LR算法有助于推导更加复杂的线面关系;LR算法和OR算法的演示系统,完成了LR算法和OR算法的运算,运算矩阵和结果矩阵的显示直观、形象,很容易接受。本文的工作验证了线和线及线和区域拓扑关系9-交集矩阵优化算法的优化作用,为算法的应用奠定了一定的基础,对空间关系的应用具有一定的意义。更多还原

【Abstract】 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.更多还原