﻿ 基于25交模型实现带洞面域拓扑关系描述模型间的转换
 文章快速检索 高级检索

1. 中国矿业大学地球科学与测绘工程学院, 北京 100083;
2. 中国地质调查局发展研究中心, 北京 100037

Transformations among Topological Relation Representation Models for Regions with Holes Using the 25-intersection Method
WANG Zhangang1 , QU Honggang2 , WANG Xianghong2
1. College of Geosciences and Surveying Engineering, China University of Mining and Technology, Beijing 100083, China;
2. Development and Research Centre, China Geological Survey, Beijing 100037, China
Foundation support: The National Natural Science Foundation of China (Nos. 41672326;41202238);The Work Project of China Geological Survey (No. DD20189134);The Fundamental Research Funds for the Central Universities
First author: WANG Zhangang(1980—), male, PhD, majors in geological Information science.E-mail:millwzg@163.com
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

1 带洞面域定义 1.1 带洞面域的构成结构

 图 1 复杂面域的5个拓扑子集 Fig. 1 Five topologically distinct and mutually exclusive parts

1.2 复杂面域分解与正则表达式

2 带洞面域的拓扑关系描述模型

2.1 主要模型

2.1.1 经典9交模型

Egenhofer 9交模型[7-8](本文称为经典9交模型，简称9I)采用对象的内部(o)、边界()和外部(+)三个子集间的交集描述拓扑关系，其定义为

2.1.2 宽边界扩展9交模型[4]

2.1.3 关系矩阵表

2.1.4 扩展9交集模型[14-15]

2.1.5 4元组模型[18, 27]

2.1.6 25交模型[5, 16]

25交模型是通过两个面域AB的5个拓扑子集的交集来描述拓扑关系，表示为一个5×5的0/1型25交矩阵R25(A, B)

2.2 对比分析

 模型 模型构建方式 对洞的表达 二进制存储位数 拓扑关系推理 分辨能力 经典9交模型(9I) 基于点集拓扑 不区分洞，洞是外部一部分，洞的边界是边界一部分，构成3个拓扑子集 9 简单对象之间的推理组合表[29] 低，33种[3, 28] 宽边界9交模型(E9I) 基于点集拓扑 区分洞和外部，将内边界、内部和外边界合并为宽边界，构成3个拓扑子集 9 简单宽边界对象之间的推理组合表[4, 18] 一般 25交模型(25I) 基于点集拓扑 区分洞的内部和边界，构成5个拓扑子集 25 无 中等，不可分析构成对象间的拓扑关系 4元组模型(4-Tuple) 对象分解 区分洞和广义面域的整体情况，可区分内外边界和内外部的交集情况，但无法直接给出整体面域间内部的交集情况 36 简单带洞对象之间的推理组合表[18] 中等，不可分析构成对象间的拓扑关系 关系矩阵表 对象分解 区分构成洞和广义面域的每一个简单面域间的交集情况，但无法直接给出整体面域间的交集情况 3mn 推理过程简单，适用于任意复杂面域[6] 精细，可分析构成对象间的拓扑关系 扩展9交模型(D9I) 基于点集拓扑 区分构成洞和广义面域的每一个简单面域间的交集以及整体面域间的交集情况 9(mn+1) 无 精细，可分析构成对象间的拓扑关系

2.3 不同模型之间的转换

 图 2 不同模型之间的转换 Fig. 2 Conversion of different models

3 不同拓扑关系模型间的转换推导

3.1 基于25交模型的拓扑关系分解计算

Ma={A-1∂A-1Ao∂A+1A+1}，∀aMa可得

R25(A, B)是0/1布尔型矩阵，需要将上述集合的并和交操作直接转化为逻辑或和逻辑与。显然，集合的并和逻辑或对应，且运算不会产生歧义，故

a∂B+1ri4AB1ri4AB2，其中，iR25(A, B)矩阵的行号。

B的外外部是B1B2外外部的交集，由于B1B2相离且均不为空，则B+1=B1+1B2+1B1+1B1+1B2+1B2+1。对于集合运算，当a∩[B1+1－(B1+1B2+1)]≠ϕa∩[B2+1－(B1+1B2+1)]≠ϕ可以存在a∩(B1+1B2+1)=ϕ而且(aB1+1)≠ϕ，(aB2+1)≠ϕ，但是(aB1+1)∧(aB2+1)≠ϕ，所以aB+1=(aB1+1)∩(aB2+1)↛ri5AB1ri5AB2，产生运算的歧义性。

Ma={A-1∂A-1Ao∂A+1A+1}，∀aMa可得：

aB+1ri5AB1ri1AB2，其中，iR25(A, B)矩阵的行号。

aBo=(aB1o)∩(aB2+1)→ri5AB1ri3AB2。该过程仍会产生歧义。如果(aB1o)≠ϕ，(aB2+1)≠ϕ，当存在(aB1o)∧(aB2+1)≠ϕa∩(B1oB2+1)=ϕ的情况，则公式产生歧义问题，此时a∩[B1o－(B1oB2+1)]≠ϕa∩[B2+1－(B1oB2+1)]≠ϕaBo=(aB1o)∩(aB2+1)↛ri5AB1ri3AB2

3.2 不同模型的转换证明

4元组模型由整体广义面域和洞构成，表示为A=AEAHB=BEBH。与5个拓扑子集的关系为

T2=R9(AE, BH)为例

4 基于25交模型的拓扑关系分析实例 4.1 具有特定结构的带洞面域拓扑关系推导

R25(Ai, Cj)∈M(Ai, Cj)=∩BkWBR25(Ai, BkR25(Bk, Cj)，其中，R25取值为基本拓扑关系, CjWC, AiWA。根据复杂面域的定义，25交模型推理中剔除不合理拓扑关系的条件为[26]

 图 3 4个面域对象：A, B, C和D Fig. 3 Four regions:A, B, C and D

 模型 R(A, B) R(A, C) R(B, C) R(A, D) 关系矩阵表 950 950 11 066 152 25交模型 244 244 504 152 经典9交模型 16 16 21 14

ABBC的具体拓扑关系如图 4所示，则采用关系矩阵表推理得到AC的可能拓扑关系为15种，如表 3所示，将这些关系转换为25交模型，可得到5种拓扑关系，如图 5所示。其中8种基本拓扑关系disjoint，meet，contain，cover，inside，coverby，equal和overlap的缩写为d, m, cn, cv, i, cb, e, o。

 图 4 A, B与B, C的拓扑关系 Fig. 4 Topological relations of A and B, and B and C

 对象 C1 C2 C3 A1 {d, m, cn, cb, o} {d, m, o} {d} A2 {d} {d} {d}

 图 5 A、C推理结果：5种25交拓扑关系 Fig. 5 Reasoning results:5 relations based on 25I

4.2 实例分析

 图 6 带洞区域对象的拓扑关系描述实例 Fig. 6 An example of the topological relations between regions with holes

5 结论

﻿

 [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. DOI:10.1080/02693799408901990 [3] SCHNEIDER M, BEHR T. Topological Relationships between Complex Spatial Objects[J]. ACM Transactions on Database Systems, 2006, 31(1): 39–81. DOI:10.1145/1132863 [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. DOI:10.1016/j.isprsjprs.2008.02.004 [7] EGENHOFER M J, FRANZOSA R D. Point-set Topological Spatial Relations[J]. International Journal of Geographical Information Systems, 1991, 5(2): 161–174. DOI:10.1080/02693799108927841 [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. DOI:10.1080/13658810151072831 [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. DOI:10.1080/13658816.2013.781607 [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. 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. 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. DOI:10.1080/13658816.2015.1004333 [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. DOI:10.1016/j.ijar.2007.05.002 [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. DOI:10.3969/j.issn.1003-6059.2013.03.003 [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. DOI:10.3321/j.issn:1001-1595.2005.01.015 [23] TRYFONA N, EGENHOFER MJ. Consistency Among Parts and Aggregates:A Computational Model[J]. Transactions in GIS, 1996, 1(3): 189–206. DOI:10.1111/tgis.1996.1.issue-3 [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. 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. DOI:10.1080/13658810600661383 [29] EGENHOFER M J. Deriving the Composition of Binary Topological Relations[J]. Journal of Visual Languages & Computing, 1994, 5(2): 133–149.
http://dx.doi.org/10.11947/j.AGCS.2018.20160589

0

#### 文章信息

WANG Zhangang, QU Honggang, WANG Xianghong

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

Acta Geodaetica et Cartographica Sinica, 2018, 47(9): 1270-1279
http://dx.doi.org/10.11947/j.AGCS.2018.20160589