Dividing and Computing Topological Relations between Complex Regions

doi:10.11947/j.AGCS.2017.20160209

Abstract

Abstract: A novel method was proposed for computing topological relations between complex regions based on 9-intersection (9I) matrices. A complex region was composed of a finite set of simple regions and its configuration was represented as a regular expression. Two 9I Boolean matrix operators were defined and used for computing the binary topological relations between complex regions while the relations between the decomposed regions were known. The establishing conditions of the operators were proved and analyzed in detail and the method of eliminating the ambiguities was given to make the computation correct. The approach can be used as a useful computation tool to analysis topological relations between spatial objects with specific configurations. In addition,the operators are dependent on definitions of complex regions and not suitable for regions which violate our definitions.

Key words: geographical information system, complex regions, topological relations, 9-intersection model

CLC Number:

P282

WANG Zhangang, DU Qunle, WANG Xianghong. Dividing and Computing Topological Relations between Complex Regions[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(8): 1047-1057.

References

[1] FRANK A U. Qualitative Spatial Reasoning about Distance and Directions in Geographic Space[J]. Journal of Visual Languages & Computing, 1992, 3(4):343-371.
[2] CLEMENTINI E, SHARMA J, EGENHOFER M J. Modelling Topological Spatial Relations:Strategies for Query Processing[J]. Computers & Graphics, 1994, 18(6):815-822.
[3] 陈军, 赵仁亮. GIS空间关系的基本问题与研究进展[J]. 测绘学报, 1999, 28(2):95-102. CHEN Jun, ZHAO Renliang. Spatial Relations in GIS:A Survey on Its Key Issues and Research Progress[J]. Acta Geodaetica et Cartographica Sinica, 1999, 28(2):95-102.
[4] EGENHOFER M J, CLEMENTINI E, DI FELICE P. Research Paper:Topological Relations between Regions with Holes[J]. International Journal of Geographical Information Systems, 1994, 8(2):129-142.
[5] EGENHOFER M J, FRANZOSA R D. Point-set Topological Spatial Relations[J]. International Journal of Geographical Information Systems, 1991, 5(2):161-174.
[6] EGENHOFER M J, HERRING J R. Categorizing Binary Topological Relations between Regions, Lines and Points in Geographic Databases[R]. Orono:University of Maine, 1991.
[7] RANDELL D A, CUI Z, COHN A G. A Spatial Logic Based on Regions and Connection[C]//Proceedings of the 3rd International Conference on Knowledge Representation and Reasoning. Los Altos:Morgan Kaufman, 1992:165-176.
[8] LI Sanjing, YING Mingsheng. Extensionality of the RCC8 Composition Table[J]. Fundamenta Informaticae, 2002, 55(3-4):363-385.
[9] CLEMENTINI E, DI FELICE P. Spatial Model for Complex Objects with a Broad Boundary Supporting Queries on Uncertain Data[J]. Data & Knowledge Engineering, 2001, 37(3):285-305.
[10] TANG Xinming,KAINZ W,WANG Hongyan.Topological Relations between Fuzzy Regions in a Fuzzy Topological Space[J]. International Journal of Applied Earth Observation and Geoinformation, 2010, 12(S2):S151-S165.
[11] WORBOYS M F, BOFAKOS P. A Canonical Model for a Class of Areal Spatial Objects[C]//Proceedings of the Third International Symposium on Advances in Spatial Databases. London:Springer-Verlag, 1993:36-52.
[12] OpenGIS® Implementation Specification for Geographic Information:Simple Feature Access:Part 2:SQL Option[R]. Reference Number:OGC 06-104r4, 2006.
[13] SCHNEIDER M, BEHR T. Topological Relationships between Complex Spatial Objects[J]. ACM Transactions on Database Systems, 2006, 31(1):39-81.
[14] LI Sanjiang. A Complete Classification of Topological Relations Using the 9-intersection Method[J]. International Journal of Geographical Information Science, 2006, 20(6):589-610.
[15] KURATA Y. The 9+-Intersection:A Universal Framework for Modeling Topological Relations[M]//COVA T J, MILLER H J, BEARD K, et al. Geographic Information Science. GIScience 2008. Lecture Notes in Computer Science. Berlin:Springer, 2008:181-198.
[16] CHEN Jun, LI Chengming, LI Zhilin, et al. Voronoi-based 9-intersection Model for Spatial Relations[J]. International Journal of Geographical Information Science, 2001, 15(3):201-220.
[17] LONG Zhiguo, LI Sanjiang. A Complete Classification of Spatial Relations Using the Voronoi-based Nine-intersection Model[J]. International Journal of Geographical Information Science, 2013, 27(10):2006-2025.
[18] 欧阳继红, 霍林林, 刘大有, 等. 能表达带洞区域拓扑关系的扩展9-交集模型[J]. 吉林大学学报(工学版), 2009, 39(6):1595-1600. OUYANG Jihong, HUO Linlin, LIU Dayou, et al. Extended 9-intersection Model for Description of Topological Relations between Regions with Holes[J]. Journal of Jilin University (Engineering and Technology Edition), 2009, 39(6):1595-1600.
[19] 李健, 欧阳继红, 王振鑫. 带双洞区域与简单区域间的拓扑关系[J]. 吉林大学学报(工学版), 2012, 42(5):1214-1218. LI Jian, OUYANG Jihong, WANG Zhenxin. Topological Relations between a Region with Two Holes and a Simple Region[J]. Journal of Jilin University (Engineering and Technology Edition), 2012, 42(5):1214-1218.
[20] 陈占龙, 冯齐奇, 吴信才. 复合面状对象拓扑关系的表达模型[J]. 测绘学报, 2015, 44(4):438-444. DOI:10.11947/j.AGCS.2015.20130708. CHEN Zhanlong,FENG Qiqi, WU Xincai. Representation Model of Topological Relations between Complex Planar Objects[J]. Acta Geodaeticaet Cartographica Sinica, 2015, 44(4):438-444. DOI:10.11947/j.AGCS.2015.20130708.
[21] 沈敬伟, 周廷刚, 朱晓波. 面向带洞面状对象间的拓扑关系描述模型[J]. 测绘学报, 2016, 45(6):722-730. DOI:10.11947/j.AGCS.2016.20150352. SHEN Jingwei, ZHOU Tinggang, ZHU Xiaobo. Topological Relation Representation Model between Regions with Holes[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(6):722-730. DOI:10.11947/j.AGCS.2016.20150352.
[22] DU Shihong, GUO Luo, WANG Qiao, et al. Efficiently Computing and Deriving Topological Relation Matrices between Complex Regions with Broad Boundaries[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2008, 63(6):593-609.
[23] EGENHOFER M J. Deriving the Composition of Binary Topological Relations[J]. Journal of Visual Languages & Computing, 1994, 5(2):133-149.
[24] TRYFONA N, EGENHOFER M J. Consistency among Parts and Aggregates:A Computational Model[J]. Transactions in GIS, 1996, 1(3):189-206.
[25] NGUYEN V H, PARENT C, SPACCAPIETRA S. Complex Regions in Topological Queries[C]//Proceedings of the International Conference on Spatial Information Theory:COSIT97. Laurel Highlands:Springer-Verlag, 1997:175-192.
[26] DU Shihong, FENG Chenchen, GUO Luo. Integrative Representation and Inference of Qualitative Locations about Points, Lines, and Polygons[J]. International Journal of Geographical Information Science, 2015, 29(6):980-1006.