Transformations among Topological Relation Representation Models for Regions with Holes Using the 25-intersection Method

doi:10.11947/j.AGCS.2018.20160589

Abstract

Abstract: A variety of topological relation representation models for complex regions with holes have been put forward nowadays.Establishing the connections among different models can give full play to the advantages of these models in the derivation and analysis of topological relations.Based on the point-set topology theory and region decomposition,six topological relation representation models were analyzed.Two 25-intersection (25I) 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.Based on the operators,transformations among the description models were realized.Theoretical analysis proved that the relational matrix table and extended 9-intersection model have the same accurate expression of topological relations and can be transformed with each other,and so do the 4-tuple model and 25I model.Furthermore,the method of relational matrix table can be transformed to 25I model and classical 9-intersection model.The experimental analysis shows that our method can be used to link different topological relation representation models and derive topological relations between complex regions with holes.

Key words: region with holes, topological relation, 25-intersection model, model transformation

CLC Number:

P282

WANG Zhangang, QU Honggang, WANG Xianghong. Transformations among Topological Relation Representation Models for Regions with Holes Using the 25-intersection Method[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47(9): 1270-1279.

References

[1] WORBOYS M, BOFAKOS P. A Canonical Model for a Class of Areal Spatial Objects[C]//Proceedings of the 3rd International Symposium on Advances in Spatial Databases. London:Springer-verlag, 1993:36-52.
[2] EGENHOFER M J, CLEMENTINI E, DI FELICE P. Topological Relations Between Regions with Holes[J]. International Journal of Geographical Information Systems, 1994, 8(2):129-144.
[3] SCHNEIDER M, BEHR T. Topological Relationships between Complex Spatial Objects[J]. ACM Transactions on Database Systems, 2006, 31(1):39-81.
[4] 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.
[5] 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 Suppl 2:S151-S165.
[6] 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.
[7] EGENHOFER M J, FRANZOSA R D. Point-set Topological Spatial Relations[J]. International Journal of Geographical Information Systems, 1991, 5(2):161-174.
[8] EGENHOFER M J, HERRING J R. Categorizing Binary Topological Relations Between Regions, Lines and Points in Geographic Databases[R]. Orono:University of Maine, 1990.
[9] RANDELL D, CUI Zhan, COHN A G. A Spatial Logic based on Regions and Connection[C]//Proceedings of the 3rd International Conference on Knowledge Representation and Reasoning. San Mateo:Morgan Kaufmann Publishers, 1992:165-176.
[10] LI Sanjiang, YING Mingsheng. Extensionality of the RCC8 Composition Table[J]. Fundamenta Informaticae, 2003, 55(3-4):363-385.
[11] 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. Berlin:Springer, 2008, 5266:181-198.
[12] CHEN Jun, LI Chengming, LI Zhilin, et al. A Voronoi-based 9-intersection Model for Spatial Relations[J]. International Journal of Geographical Information Science, 2001, 15(3):201-220.
[13] 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.
[14] 欧阳继红, 霍林林, 刘大有, 等. 能表达带洞区域拓扑关系的扩展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.
[15] 陈占龙, 冯齐奇, 吴信才. 复合面状对象拓扑关系的表达模型[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 Geodaetica et Cartographica Sinica, 2015, 44(4):438-444. DOI:10.11947/j.AGCS.2015.20130708.
[16] 沈敬伟, 周廷刚, 朱晓波. 面向带洞面状对象间的拓扑关系描述模型[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.
[17] DU Shihong, FENG C H, 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.
[18] DU Shihong, QIN Qimin, WANG Qiao, et al. Reasoning About Topological Relations between Regions with Broad Boundaries[J]. International Journal of Approximate Reasoning, 2008, 47(2):219-232.
[19] DU Shihong. Analyzing Topological Changes for Structural Shapes Simplification[J]. Journal of Visual Languages & Computing, 2014, 25(4):316-332.
[20] EGENHOFER M J, VASARDANI M. Spatial Reasoning with a Hole[C]//Proceedings of the 8th International Conference on Spatial Information Theory. Melbourne:Springer-verlag, 2007:303-320.
[21] 李健, 欧阳继红, 富倩, 等. 凹形区域和带单洞区域间拓扑关系的表示[J]. 模式识别与人工智能, 2013, 26(3):225-230. LI Jian, OUYANG Jihong, FU Qian, et al. Representation of Topological Relations Between a Concave Region and a Simple Region with a Hole[J]. PR & AI, 2013, 26(3):225-230.
[22] 邓敏, 刘文宝, 冯学智. GIS面目标间拓扑关系的形式化模型[J]. 测绘学报, 2005, 34(1):85-90. DENG Min, LIU Wenbao, FENG Xuezhi. A Generic Model of Topological Relations Between Spatial Regions in GIS[J]. Acta Geodaetica et Cartographica Sinica, 2005, 34(1):85-90.
[23] TRYFONA N, EGENHOFER MJ. Consistency Among Parts and Aggregates:A Computational Model[J]. Transactions in GIS, 1996, 1(3):189-206.
[24] NGUYEN V H, PARENT C, SPACCAPIETRA S. Complex Regions in Topological Queries[C]//Proceedings of the International Conference on Spatial Information Theory. Laurel Highlands:Springer-verlag, 1997, 1329:175-192.
[25] HERRING J R. OpenGIS Implementation Standard for Geographic Information-simple Feature Access-Part 2:SQL option[S]. Wayland:OpenGIS Inc., 2010.
[26] 王占刚, 杜群乐, 王想红. 复杂区域对象拓扑关系分解与计算[J]. 测绘学报, 2017, 46(8):1047-1057. DOI:10.11947/j.AGCS.2017.20160209. 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. DOI:10.11947/j.AGCS.2017.20160209.
[27] 刘波, 李大军, 邹时林, 等. 带孔洞面域间的拓扑关系的组合推理[J]. 测绘学报, 2011, 40(2):262-267. LIU Bo, LI Dajun, ZOU Shilin, et al. Combinational Reasoning of Topological Relations Between Regions with Holes[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(2):262-267.
[28] 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.
[29] EGENHOFER M J. Deriving the Composition of Binary Topological Relations[J]. Journal of Visual Languages & Computing, 1994, 5(2):133-149.