﻿ 复杂面实体拓扑关系的精细化模型
 文章快速检索 高级检索

The precise model of complex planar objects' topological relations
CHEN Zhanlong, YE Wen
Faculty of Information Engineering, China University of Geosciences, Wuhan 430074, China
Abstract: For complex planar objects, which are composed of simple spatial objects, the existent models of topological relations may not be able to describe some topological attributes of complex objects well. Taking the topological content between complex objects into account, this paper presents a model of basic topological relations between line/planar objects, and then in which the basic topological relations and the concept of overlapping area are leveraged to describe the topological relations of simple planar objects. The definition of traversing of hole's boundary and planar with a hole are used to describe the topological relations between complex planar objects. Finally, the five basic topological relationship description modes of complex planar objects are summarized to realize description of the details of topological relations between partitions of complex planar objects.
Key words: spatial combination    topological relation    boundary intersection    precise representation

 图 1 复杂空间对象的拓扑关系 Fig. 1 Topological relations of complex spatial object

1 复杂面实体及其拓扑关系

 图 2 带洞面的定性模型 Fig. 2 Qualitative model of the surface with hole

 图 3 复杂空间对象的构成 Fig. 3 Component of complex spatial object

 图 4 复杂面拓扑关系 Fig. 4 Topological relation of complex planar

2 复杂面实体的元拓扑边界交集描述 2.1 线面实体间拓扑关系

 图 5 拓扑关系示意图 Fig. 5 Schematic diagram of topological relations

2.2 元拓扑关系

“基本”不可分性。“基本”不可分性，是指一般情况下，元拓扑关系就是组成复合拓扑关系的最小单元，不可再分。但元拓扑关系又不可过于具体，否则会导致过多的繁琐工作。元拓扑关系必须在保证概括性的前提下，保证其不可分性。

2.3 元拓扑关系的方位描述

 图 6 元拓扑关系 Fig. 6 Basic topological relations

R(L, A)＜=＞R(L, ∂A)=(Orie, MetaR)

Orie={in, out}，MetaR={M1, T1, C1, M0, T0, C0}

2.4 元关系的连接

2.4.1 元关系的连接顺序

 图 7 连接顺序 Fig. 7 Connecting order

Order(L, A)=(k1, k2, k3, …, kn), n≥2

R(L, A)＜=＞R(L, ∂A)=(Order, Orie, MetaR)

Order={1, 2, 3, …, n}，Orie={in, out}，MetaR={M1, T1, C1, M0, T0, C0}

2.4.2 元关系的连接方向

 图 8 连接方向 Fig. 8 Connecting direction

R(L, A)＜=＞R(L, ∂A)=(Order, Orie1, Orie2, MetaR)

Order={1, 2, 3, …, n}, Orie1={in, out}, Orie2={c, a}, MetaR={M1, T1, C1, M0, T0, C0}

2.5 线面空间关系集成表达模型的约束性

 图 9 拓扑关系示例 Fig. 9 Example of topological relations

2.6 复杂面边界间拓扑关系描述

2.6.1 简单面边界拓扑关系描述

InterR={Intersection1, Intersection2, …, Intersectionn}

 图 10 拓扑关系示例 Fig. 10 Example of topological relations

InterM:{N(1, out, c, C0), N(2, in, -, C0)}

 图 11 拓扑关系示例 Fig. 11 Example of topological relations

InterA={B(1, out, c, C0), B(2, in, -, C0), C(3, out, c, T0), C(4, out, -, T0)}

InterB={C(1, out, c, T0), C(2, out, -, T0), A(3, out, a, C0), A(4, in, -, C0)}

InterC={A(1, out, a, T0), A(2, out, -, T0), B(3, out, c, T0), B(4, out, -, T0)}

InterA={C(1, in, c, C0), C(2, out, -, C1), B(3, out, -, T0)}

InterB={C(1, out, -, T0), A(2, out, -, T0)}

InterC={B(1, out, -, T0), A(2, in, c, C1), A(3, out, -, C0)}

2.6.2 重叠面积描述

 图 12 拓扑关系事例 Fig. 12 Example of topological relations

InterM1={M2(1, out, c, T1)M2(2, out, -, T1)M3(3, out, c, C0)M3(4, in, -, C0)}

InterM2={M1(1, out, a, T1)M1(2, out, -, T1)M3(3, out, a, C0)M3(4, in, -, C0)}

InterM3={M1(1, out, a, C0)M1(2, in, -, C0)M2(3, out, a, C0)M2(4, in, -, C0)}

InterN1={N2(1, out, c, T1)N2(2, out, c, T0)N2(3, out, -, T1)N3(4, out, c, C0)N3(5, in, -, C0)}

InterN2={N1(1, out, c, T1)N1(2, out, c, T0)N1(3, out, -, T1)N3(4, out, a, C0)N3(5, in, -, C0)}

InterN3={N1(1, out, a, C0)N1(2, in, -, C0)N2(3, out, a, C0)N2(4, in, -, C0)}

 图 13 重叠面积示例 Fig. 13 Example of topological area

InterR={Intersection1, Intersection2, …, Intersectionn, Area1, Area2, …, Aream}

InterM1={M2(1, out, c, T1)M2(2, out, -, T1)M3(3, out, c, C0)M3(4, in, -, C0), area(M1M3)}

InterM2={M1(1, out, a, T1)M1(2, out, -, T1)M3(3, out, a, C0)M3(4, in, -, C0), area(M2M3)}

InterM3={M1(1, out, a, C0)M1(2, in, -, C0)M2(3, out, a, C0)M2(4, in, -, C0), area(M3M1), area(M3M2)}

InterN1={N2(1, out, c, T1)N2(2, out, c, T0)N2(3, out, -, T1)N3(4, out, c, C0)N3(5, in, -, C0), area(N1N3)}

InterN2={N1(1, out, c, T1)N1(2, out, c, T0)N1(3, out, -, T1)N3(4, out, a, C0)N3(5, in, -, C0), area(N2N3)}

InterN3={N1(1, out, a, C0)N1(2, in, -, C0)N2(3, out, a, C0)N2(4, in, -, C0), area(N3N1), area(N3N2)}

2.6.3 带洞面边界拓扑关系描述

InterR={Intersection1, Intersection2, …, Intersectionn, -R′}

InterR={Intersection1, Intersection2, …, Intersectionn, -R′, R′⊇/=I}

 图 14 面实体组合 Fig. 14 Combination of plane entities

 图 15 面实体组合 Fig. 15 Combination of plane entities

InterA={D(1, out, c, C0)D(2, in, -, C0)area(AD)}

InterA={D(1, out, a, C0)D(2, in, -, C0)B(3, out, -, T1), -, -, A′⊇B, A′⊇C}

InterB={D(1, out, a, C0)D(2, in, -, C0)A′(3, in, -, T1)area(BD, -, BA′)}

InterD={A(1, out, a, C0)A(2, in, -, C0)A′(3, out, a, C0)A′(4, in, -, C0)B(5, out, a, C0)B(6, in, -, C0)C(7, out, c, C0)C(8, in, -, C0)area(DA), -, area(DB)area(DC)}

InterA={D(1, out, c, C0)D(2, in, a, C0)D(3, out, c, C0)D(4, in, -, C0)area(AD)}

InterA={D(1, out, c, C0)D(2, in, a, C0)D(3, out, c, C0)D(4, in, -, C0)B(5, out, -, T1)-, -, A′⊇B, A′⊇C}

InterB={D(1, out, a, C0)D(2, in, c, C0)D(3, out, a, C0)D(4, in, -, C0)A′(5, in, -, T1)area(BD), -, BA′}

InterC={D(1, out, c, C0)D(2, in, a, C0)D(3, out, c, C0)D(4, in, -, C0)area(CD), CA′}

InterD={A(1, out, c, C0)A(2, in, c, C0)A(3, out, a, C0)A(4, in, -, C0)B(5, out, a, C0)B(6, in, a, C0)B(7, out, a, C0)B(8, in, -, C0)C(9, out, c, C0)C(10, in, c, C0)C(11, out, c, C0)C(12, in, -, C0)A′(13, out, a, C0)A′(14, in, c, C0)A′(15, out, a, C0)A′(16, in, -, C0)area(DA)area(DB)area(DC)-}

3 复杂面实体的拓扑关系精细化表达

 图 16 概念流程图 Fig. 16 Flow diagram of concept

3.1 基础程序算法

//初始调用INOUT: R->{r1, r2, …, rn}(复杂面实体集合);

n(复杂面实体个数)；

OUTPUT:M->{m1, m2, m3…}(关系矩阵集合)；

COMBINED-EXPRESSION(R, N, M):

foreach rR do  //遍历每个复杂面实体

foreach br do  //遍历复杂面实体中的内外边界

If b==out then  //如果b是外边界

foreach pb do  //顺时针遍历改边界上的交点

assert p==out/in  //判断该点的进出

assert p==c/a  //判断该点与下一点之间的方向

assert p==C0/C1/T0/T1  //判断该点的相交方式

If p==lastone then  //如果p是当前边界的最后一个交点

assert rr′==∅ or rr′!=∅   //判断b所在的实体r是否与其他实体是否有面积相交

assert rr′ or rr′   //判断b所在的实体是否被包含在其他实体内

If b==in then  //如果b是外边界

foreach pb do  //逆时针遍历改边界上的交点

assert p==out/in  //判断该点的进出

assert p==c/a  //判断该点与下一点之间的方向

assert p==C0/C1/T0/T1  //判断该点的相交方式

If p==lastone then  //如果p是当前边界的最后一个交点

assert rr′==∅ or rr′!=∅ //判断b所在的实体r是否与其他

//实体是否有面积相交

assert r′∈r or r′ ∉r  //判断b所在的实体是否包含在其他实体

//生成该边界的组合关系矩阵表达式

produce M={m1, m2, m3…}  //生成关系矩阵表达式

return M

3.2 数据类型分析与归纳

 图 17 复杂面相交情况分解图 Fig. 17 Decomposition diagram of complex planar objects

3.3 模拟数据验证

 类型 复杂面拓扑关系图 扩展元拓扑关系矩阵 带洞面相交(洞中含面且与洞重合) 带洞面相交(洞中面与洞相切) 带洞面相交(洞中面与洞相离) 带洞面相交(洞中面与洞相离)

4 总结与展望

﻿

 [1] 陈占龙, 冯齐奇, 吴信才. 复合面状对象拓扑关系的表达模型[J]. 测绘学报, 2015, 44(4): 438–444, 452. 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, 452. DOI:10.11947/j.AGCS.2015.20130708 [2] 曹亚妮, 吴芳华, 王立军, 等. 基于元拓扑关系的线面空间关系集成表达模型[J]. 武汉大学学报(信息科学版), 2016, 41(1): 123–130. CAO Yani, WU Fanghua, WANG Lijun, et al. The integrated representation model of line-region spatial relations based on meta-relations[J]. Geomatics And Information Science of WuHan University, 2016, 41(1): 123–130. [3] 周晓光, 陈斐, 陈军. 引入结点度的线/面拓扑关系细分方法与应用[J]. 测绘学报, 2015, 44(4): 445–452. ZHOU Xiaoguang, CHEN Fei, CHEN Jun. A node-degree based line/polygon topological relationship refinement model and its application[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(4): 445–452. DOI:10.11947/j.AGCS.2015.20140138 [4] FRANKLIN W R. Cartographic errors symptomatic of underlying algebra problems[C]//Proceedings of the International Symposium on Spatial Data Handling. Zurich, Switzerland: [s.n.], 1984: 190-208. [5] RANDELL D, CUI Z, COHN A. A spatial logic based on regions and connection[C]//Proceedings of the 3rd International Conference on Knowledge Representation and Reasoning. Cambridge, MA: [s.n.], 1992: 165-176. [6] EGENHOFER M J, CLEMENTINI E, DI FELICE P. Topological relations between regions with holes[J]. International Journal of Geographical Information Systems, 1994, 8(2): 128–142. [7] EGENHOFER M J, VASARDANI M. Spatial reasoning with a hole[C]//Proceedings of the 8th International Conference on Spatial Information Theory. Melbourne, Australia: Springer. 2007: 303-320. [8] KODRATOFF Y, LEMERLE-LOISEL R. Learning complex structural descriptions from examples[J]. Computer Vision, Graphics, and Image Processing, 1984, 27(3): 266–290. DOI:10.1016/0734-189X(84)90032-X [9] EGENHOFER M J. Deriving the composition of binary topological relations[J]. Journal of Visual Languages & Computing, 1994, 5(2): 133–149. [10] 刘波, 李大军, 邹时, 等. 带孔洞面域间的拓扑关系的组合推理[J]. 测绘学报, 2011, 40(2): 262–267. LIU Bo, LI Dajun, ZOU Shi, et al. Combinational reasoning of topological relations between regions with holes[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(2): 262–267. [11] 沈敬伟, 周廷刚, 朱晓波. 面向带洞面状对象间的拓扑关系描述模型[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 [12] 邓敏, 李志林, 李光强. 简单面目标与带孔洞面目标间拓扑关系的层次表达方法[J]. 测绘学报, 2008, 37(3): 330–337. DENG Min, LI Zhilin, LI Guangqiang. A hierarchical approach to topological relations between a simple area and an area with holes[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37(3): 330–337. DOI:10.3321/j.issn:1001-1595.2008.03.011 [13] 唐雪华, 秦昆, 孟令奎. 基于拓扑参考的定性方向关系矩阵描述模型[J]. 测绘学报, 2014, 43(4): 396–403. TANG Xuehua, QIN kung, MENG Lingkui. A qualitative matrix model of direction-relation based on topological refer-ence[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(4): 396–403. DOI:10.13485/j.cnki.11-2089.2014.0059 [14] 吴华意, 刘波, 李大军, 等. 空间对象拓扑关系研究综述[J]. 武汉大学学报(信息科学版), 2014, 39(11): 1269–1276. WU Huayi, LIU Bo, LI Dajun, et al. Topological relations of spatial objects:a review[J]. Geomatics And Information Science of Wuhan University, 2014, 39(11): 1269–1276. [15] RODRÍGUEZ M A, EGENHOFER M J, BLASER A D. Query pre-processing of topological constraints: comparing a composition-based with neighborhood-based approach[C]//Proceedings of the 8th International Symposium on Advances in Spatial and Temporal Databases. Santorini Island, Greece: Springer, 2003: 362-379. [16] 吴长彬, 闾国年. 空间拓扑关系若干问题研究现状的评析[J]. 地球信息科学学报, 2010, 12(4): 524–531. WU Changbin, LÜ Guonian. Spatial topological relationships:an overview and analysis[J]. Geo-Information Science, 2010, 12(4): 524–531. [17] 郭庆胜, 杜晓初, 刘浩. 空间拓扑关系定量描述与抽象方法研究[J]. 测绘学报, 2005, 34(2): 123–128. GUO Qingsheng, DU Xiaochu, LIU Hao. Research on quantitative representation and abstraction of spatial topological relation between two regions[J]. Acta Geodaetica et Cartographica Sinica, 2005, 34(2): 123–128. DOI:10.3321/j.issn:1001-1595.2005.02.006 [18] 郭庆胜, 刘小利, 陈宇箭. 线与线之间的空间拓扑关系组合推理[J]. 武汉大学学报(信息科学版), 2006, 31(1): 39–42. GUO Qingsheng, LIU Xiaoli, CHEN Yujian. Combinational reasoning of topological spatial relations between two lines[J]. Geomatics and Information Science of Wuhan University, 2006, 31(1): 39–42. [19] 吴长彬, 闾国年. 复杂线-线对象的拓扑关系描述与计算方法[J]. 地球信息科学学报, 2014, 16(6): 839–845. WU Changbin, LÜ Guonian. Representation and Calculation method of topological relationships for complex line objects[J]. Journal of Geo-Information Science, 2014, 16(6): 839–845. [20] GALTON A. Modes of overlap[J]. Journal of Visual Languages & Computing, 1998, 9(1): 61–79. [21] CLEMENTINI E, DI FELICE P. Topological invariants for lines[J]. IEEE Transactions on Knowledge and Data Engineering, 1998, 10(1): 38–54. DOI:10.1109/69.667085 [22] EGENHOFER M J, FRANZOSA R D. On the equivalence of topological relations[J]. International Journal of Geographical Information Systems, 1995, 9(2): 133–152. DOI:10.1080/02693799508902030 [23] AKTOUF Z, BERTRAND G, PERROTON L. A three-dimensional holes closing algorithm[J]. Pattern Recognition Letters, 2002, 23(5): 523–531. DOI:10.1016/S0167-8655(01)00152-0 [24] EGENHOFER M J. A reference system for topological relations between compound spatial objects[C]//Proceedings of the 28th International Conference on Conceptual Modeling. Gramado, Brazil: Springer, 2009: 307-316. [25] EGENHOFER M J, VASARDANI M. Spatial reasoning with a hole[C]//Proceedings of the 8th International Conference on Spatial Information Theory. Melbourne, Australia: Springer, 2007: 303-320.
http://dx.doi.org/10.11947/j.AGCS.2019.20170531

0

#### 文章信息

CHEN Zhanlong, YE Wen

The precise model of complex planar objects' topological relations

Acta Geodaetica et Cartographica Sinica, 2019, 48(5): 630-642
http://dx.doi.org/10.11947/j.AGCS.2019.20170531