简单空间对象间拓扑关系算法的设计与实现
摘要
目前,大多数空间关系的表示及推理主要采用逻辑方法和代数方法进行理论研究,最著名的逻辑和代数模型是Cohn等人提出的区域连接演算RCC和Egenhofer等人提出的9-交集模型。随着地理信息和空间技术的发展,空间推理的研究已成为众多领域的研究热点,如何应用空间推理理论方法解决实际问题已成为该领域迫切需要解决的问题。
本文设计并实现了空间线与面、线与线的拓扑关系表示算法LR和算法OR,并通过演示结果证明了相关引理的正确性。主要工作包括:(1)对空间推理进行了介绍,重点介绍了空间关系描述及其研究的现状;(2)对Java语言及Jbluider进行了介绍和分析;(3)详细介绍了OR算法和LR算法及相关定义;(4)设计并实现了LR算法和OR算法演示系统;(5)通过演示结果证明了相关引理的正确性。
本文实现的OR算法与LR算法有助于推导更加复杂的线面关系;LR算法和OR算法的演示系统,完成了LR算法和OR算法的运算,运算矩阵和结果矩阵的显示直观、形象,很容易接受。本文的工作验证了线和线及线和区域拓扑关系9-交集矩阵优化算法的优化作用,为算法的应用奠定了一定的基础,对空间关系的应用具有一定的意义。
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.
本文设计并实现了空间线与面、线与线的拓扑关系表示算法LR和算法OR,并通过演示结果证明了相关引理的正确性。主要工作包括:(1)对空间推理进行了介绍,重点介绍了空间关系描述及其研究的现状;(2)对Java语言及Jbluider进行了介绍和分析;(3)详细介绍了OR算法和LR算法及相关定义;(4)设计并实现了LR算法和OR算法演示系统;(5)通过演示结果证明了相关引理的正确性。
本文实现的OR算法与LR算法有助于推导更加复杂的线面关系;LR算法和OR算法的演示系统,完成了LR算法和OR算法的运算,运算矩阵和结果矩阵的显示直观、形象,很容易接受。本文的工作验证了线和线及线和区域拓扑关系9-交集矩阵优化算法的优化作用,为算法的应用奠定了一定的基础,对空间关系的应用具有一定的意义。
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.
引文
[1] 廖士中,王建民,王海山.空间推理研究的方法学辽宁师范大学学报.2000,06(23) :147-151.
[2] Egenhofer MJ, Herring JR. Categorizing binary topological relationships between regions, lines and points in geographic database[J]. International Journal of Geographical Information Systems, 1991, 5(2):161-174.
[3] David Mark and Max Egenhofer. Modeling Spatial Relations Between Lines and Regions: Combining Formal Mathematical Models and Human Subjects Testing[J]. Cartography and Geographical Information Systems 21 (3): 195-212, 1994.
[4] Egenhofer,M. Definitions of Line-Line Relations for Geographic Databases.Data Engineering 1994,16(11):479-481.
[5] B. A. El-Geresy and A. I. Abdelmoty (1997). Order in Space: A General Formalism for Spatial Reasoning. International Journal of Artificial Intelligence Tools, IJAIT, World Scientific Publishing, 6(4), pp. 423-450, (Special Issues on Best Papers of TAI'96).
[6] B.A. El-Geresy and A.I. Abdelmoty. Towards a General Theory for Modelling Qualitative Space[J]. International Journal on Artificial Intelligence Tools, IJAIT, World Scientific Publishing, 11(3), pp. 347-367, 2002.
[7] 陈军, 赵仁亮.GIS 空间关系的基本问题与研究进展. 测绘学报, 1999, 28(2): 95~102.
[8] 马宝超,二维空间目标间的拓扑关系的研究,吉林大学研究生论文,2007.4
[9] 刘万增,陈军,赵仁亮.基于平面扫描算法的空间冲突检测算法.国家基础地理信息中心.100044.
[10] 杨树林,胡洁萍,Java 语言最新实用案例教程,清华大学出版社,2006,1 第一版.
[11] 耿祥义,Java 基础教程。清华大学出版社,2004,9 第一版.
[12] Bruce Eckel 陈昊鹏,饶若楠译,Java 编程思想,机械工业出版社,2005,8第三版.
[13] 虞强源. 空间区域拓扑关系分析方法的研究. 吉林大学博士学位论文. 2003.
[14] Isli.A.(2002) A Ternary Relation Algebra of Directed Lines.Technical Report FBIHH-M-313/02,Fachbereich Informatik,Universitaet Hamburg.
[15] Cristani,M. Reasoning about Qualitative Relations between Straight Lines.Technical Report RR,Department di Informatica,University of Verona,Verona,Italy 06/2003.
[16] Gottfried,B.(2003)Tripartite Line Tracks-Bipartite Line Tracks.in:Proceedings of KI 2003:Advances in Artificial Intelligence,Lecture Notes in Artificial Intelligence 2821,pp.535-549,B.Neumann(ed.)Springer-Verlag.Berlin.
[17] Kostas Nedas, Max Egenhofer, and Dominik Wilmsen. Metric Details of Topological Line-Line Relations. International Journal of Geographical Information Science 21(1): 21-48, 2007.
[18] D. Randell, Z. Cui, and A. Cohn. A spatial logic based on regions and connection. In Proceedings of the 3rd International Conference on Knowledge Representation and Reasoning, pages 165--176. Morgan Kaufmann, 1992.
[19] Egenhofer MJ, Franzosa RD, Point-set topological spatial relations, International Journal of Geographical Information Systems, 1991, 5(2):161-174.
[20] Egenhofer MJ, Herring J. Categorizing binary topological relationships between regions, lines and points in geographical database. Technical Report. Department of Surveying Engeering, University of Maine, 1991.
[21] S. LeNsniewski, Grundzuge eines neuen Systems der Grundlagen der Mathematik, Fundamenta Mathematicae 14 pp1– 81. 1929.
[22] Egenhofer MJ, Franzosa RD, Point-set topological spatial relations, International Journal of Geographical Information Systems, 1991, 5(2):161-174.
[23] Grigni M, Papadias D and Papadimitriou C. Topological inference. In: Proc of 14th Int Joi Conf on Artificial Intelligence, volume I. San Francisco: Morgan Kaufmann, 1995, 901-906.
[24] Egenhofer, M.J., Franzosa, R. Point-set topological spatial relations. International Journal of Geographical Information Systems, 1991, 5(2): 161~174.
[25] Chen Jun, Li Cheng-Ming, Li Zhi-Lin, Gold, C.M. In: Lee, Y.C., Li, Z.L. eds. Improving 9-Intersection Model by Replacing the Complement with VoronoiRegion. Proceedings of International Workshop on Dynamic and Multi-dimensional GIS. Hong Kong, 1997. 36~48.
[26] Egenhofer, M.J., Herring J. A Mathematical Framework for the Definition of Topological Relationships. In: Zurich, K.B., Kishimoto, H. eds. Proceedings of 4th International Symposium on Spatial Data Handling, 1990. 803~813.
[27] 闫浩文, 郭仁忠. 空间方向关系分类研究. 测绘工程, 2001, 10(4): 13~15.
[2] Egenhofer MJ, Herring JR. Categorizing binary topological relationships between regions, lines and points in geographic database[J]. International Journal of Geographical Information Systems, 1991, 5(2):161-174.
[3] David Mark and Max Egenhofer. Modeling Spatial Relations Between Lines and Regions: Combining Formal Mathematical Models and Human Subjects Testing[J]. Cartography and Geographical Information Systems 21 (3): 195-212, 1994.
[4] Egenhofer,M. Definitions of Line-Line Relations for Geographic Databases.Data Engineering 1994,16(11):479-481.
[5] B. A. El-Geresy and A. I. Abdelmoty (1997). Order in Space: A General Formalism for Spatial Reasoning. International Journal of Artificial Intelligence Tools, IJAIT, World Scientific Publishing, 6(4), pp. 423-450, (Special Issues on Best Papers of TAI'96).
[6] B.A. El-Geresy and A.I. Abdelmoty. Towards a General Theory for Modelling Qualitative Space[J]. International Journal on Artificial Intelligence Tools, IJAIT, World Scientific Publishing, 11(3), pp. 347-367, 2002.
[7] 陈军, 赵仁亮.GIS 空间关系的基本问题与研究进展. 测绘学报, 1999, 28(2): 95~102.
[8] 马宝超,二维空间目标间的拓扑关系的研究,吉林大学研究生论文,2007.4
[9] 刘万增,陈军,赵仁亮.基于平面扫描算法的空间冲突检测算法.国家基础地理信息中心.100044.
[10] 杨树林,胡洁萍,Java 语言最新实用案例教程,清华大学出版社,2006,1 第一版.
[11] 耿祥义,Java 基础教程。清华大学出版社,2004,9 第一版.
[12] Bruce Eckel 陈昊鹏,饶若楠译,Java 编程思想,机械工业出版社,2005,8第三版.
[13] 虞强源. 空间区域拓扑关系分析方法的研究. 吉林大学博士学位论文. 2003.
[14] Isli.A.(2002) A Ternary Relation Algebra of Directed Lines.Technical Report FBIHH-M-313/02,Fachbereich Informatik,Universitaet Hamburg.
[15] Cristani,M. Reasoning about Qualitative Relations between Straight Lines.Technical Report RR,Department di Informatica,University of Verona,Verona,Italy 06/2003.
[16] Gottfried,B.(2003)Tripartite Line Tracks-Bipartite Line Tracks.in:Proceedings of KI 2003:Advances in Artificial Intelligence,Lecture Notes in Artificial Intelligence 2821,pp.535-549,B.Neumann(ed.)Springer-Verlag.Berlin.
[17] Kostas Nedas, Max Egenhofer, and Dominik Wilmsen. Metric Details of Topological Line-Line Relations. International Journal of Geographical Information Science 21(1): 21-48, 2007.
[18] D. Randell, Z. Cui, and A. Cohn. A spatial logic based on regions and connection. In Proceedings of the 3rd International Conference on Knowledge Representation and Reasoning, pages 165--176. Morgan Kaufmann, 1992.
[19] Egenhofer MJ, Franzosa RD, Point-set topological spatial relations, International Journal of Geographical Information Systems, 1991, 5(2):161-174.
[20] Egenhofer MJ, Herring J. Categorizing binary topological relationships between regions, lines and points in geographical database. Technical Report. Department of Surveying Engeering, University of Maine, 1991.
[21] S. LeNsniewski, Grundzuge eines neuen Systems der Grundlagen der Mathematik, Fundamenta Mathematicae 14 pp1– 81. 1929.
[22] Egenhofer MJ, Franzosa RD, Point-set topological spatial relations, International Journal of Geographical Information Systems, 1991, 5(2):161-174.
[23] Grigni M, Papadias D and Papadimitriou C. Topological inference. In: Proc of 14th Int Joi Conf on Artificial Intelligence, volume I. San Francisco: Morgan Kaufmann, 1995, 901-906.
[24] Egenhofer, M.J., Franzosa, R. Point-set topological spatial relations. International Journal of Geographical Information Systems, 1991, 5(2): 161~174.
[25] Chen Jun, Li Cheng-Ming, Li Zhi-Lin, Gold, C.M. In: Lee, Y.C., Li, Z.L. eds. Improving 9-Intersection Model by Replacing the Complement with VoronoiRegion. Proceedings of International Workshop on Dynamic and Multi-dimensional GIS. Hong Kong, 1997. 36~48.
[26] Egenhofer, M.J., Herring J. A Mathematical Framework for the Definition of Topological Relationships. In: Zurich, K.B., Kishimoto, H. eds. Proceedings of 4th International Symposium on Spatial Data Handling, 1990. 803~813.
[27] 闫浩文, 郭仁忠. 空间方向关系分类研究. 测绘工程, 2001, 10(4): 13~15.