﻿ 复杂区域对象拓扑关系分解与计算
 文章快速检索 高级检索

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

Dividing and Computing Topological Relations between Complex Regions
WANG Zhangang1, DU Qunle1, 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. 1212011120446);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 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

1 相关定义 1.1 复杂区域

 图 1 复杂区域对象定义 Fig. 1 Definition of complex region

1.2 复杂区域的正则表达式

 实例 A B C 结构构成 正则表达式 A1-(A2-(A3-A4)) (B1-B2-B3)+(B4-B5) C1-(C2-C4)-C3 语法树

1.3 9交模型

9交模型[5-6]是通过两个复杂区域A、B的内部(°)、边界()和外部(+)的交集来描述拓扑关系。由一个3×3的0/1型9交矩阵R9(AB)表示

R9(AB)是所能表达的拓扑关系总数为33种[13]。若AB均为简单区域，如图 2，仅可推导出8种拓扑关系，依次定义为：disjoint、meet、contain、cover、inside、coverby、equal和overlap。

 图 2 简单区域间的基本拓扑关系[5](括号内为缩写) Fig. 2 Eight basic topological relations between simple regions[5](abbreviations in brackets)

2 基于9交矩阵的拓扑关系计算

 图 3 拓扑关系的分层计算 Fig. 3 Hierarchical computation of 9-instesection

2.1 多部分区域对象分解和加布尔操作

Ma={Ao∂AA+}，∀aMa可得

 图 4 集合运算和逻辑运算的差异 Fig. 4 Differences of set and logical Boolean operators

B的内部(边界)是B1B2内部(边界)的并集，不会出现AB1B2的内部(边界)相交，而与B的内部(边界)不相交的情况，也不会出现AB1B2的内部(边界)都不相交，而与B的内部(边界)相交的情况，故第1列和第2列为逻辑或操作恒成立。

B的外部是B1B2外部的交集，由于B1B2相离且均不为空，则B1+=B+B2+B1+B1+B2+B2+，交集运算转为逻辑与运算会出现a∩(B1+B2+)≠(aB1+)∧(aB2+)的情况。由于A+B+φ，只需考虑加布尔操作公式AoB+∂AB+的计算正确性。

(1) 若AoB1+=φA2oB+=φ，则∂AB1+=φ∂AB2+=φ。由AoB1+=φ∂AB1+=φ可得A=Ao∂A2-B1+，即AB1，同理可得AB2，则与B1B2=φ矛盾。此种情况不存在。

(2) 若AoB1+=φAoB2+φ，则∂AB1+=φ，可得AB1B，加布尔操作公式恒成立。同理，若AoB2+=φAoB1+φ，加布尔操作公式恒成立。

(3) 若AoB1+φAoB2+φ，分3种情况。

∂AB1+=φ∂AB2+=φ。由∂AB1+=φ可得∂AB1，同理可得∂AB2，与B1B2=φ矛盾，此情况不存在。

∂AB1+=φ∂AB2+φ。由∂AB1+=φ可得∂AB1B，公式恒成立。同理，当∂AB1+φ∂AB2+=φ，公式恒成立。

∂AB1+φ∂AB2+φ时，假设加布尔操作公式不成立，可穷举出两种情况：① AoB+=φ∂AB+=φ，说明AoB1+B2oAoB2+B1o，此时AoBo，如表 2实例1、2此种情况存在，加布尔操作公式不成立；② AoB+φ∂AB+=φ，说明∂AB1+B2∂AB2+B1，此时∂AB，如表 2实例3、4此种情况存在，加布尔操作公式不成立。综上分析，加布尔操作公式当∂AB1+φ∂AB2+φ∧(∂ABAoBo)时不成立。

 序号 A，B 实例 R9(A，B) R9(A，B1) R9(A，B2) 1 A=A1+A2B=B1+B2 2 A=A1+A2B=B1+B2 3 A=A1+A2B=B5-B3+B2B1=B5-B3 4 A=A1-A3+A2B=B1+B6-B4B2=B6-B4

2.2 带洞区域对象分解和差布尔操作

Ma={Ao∂AA+}，∀aMa可得

R9(AB1-B2)的第2列和第3列为R9(AB1)和R9(AB2)两个分解关系矩阵的逻辑或，第1列为两个分解关系矩阵的逻辑与。

B的外部(边界)是B1B2补集的外部(边界)的并集，不会出现AB1B2补集的外部(边界)相交，而与B的外部(边界)不相交的情况，也不会出现AB1B2补集的外部(边界)都不相交，而与B的外部(边界)相交的情况，故第2列和第3列逻辑或操作恒成立。

B的内部是B1B2补集内部的交集，由于B1包含B2Bo=B1o-B2o，则BoB1oBoB2+，交集运算转为逻辑与运算会出现a∩(B1oB2+)≠(aB1o)∧(aB2+)的情况。下面逐一分析差布尔操作公式不成立的条件。

(1) 当AoB1o=φ，由BoB1o可知不存在AoBoφ的情况，公式中AoBo=φ计算成立。

(2) 当AoB1oφ，若AoB2+=φ，说明AB2，由于BoB2+，公式中AoBo=φ计算恒成立；若AoB2+φ，假设公式不成立，即AoBo=φ，由于Bo=B1o-B2o，说明AoB1oB2oAoB1+φ，如表 3第4种实例，公式不成立。

 序号 A，B 实例 R9(A，B) R9(A，B1) R9(A，B2) 1 A=A1-A2B=B1-B2 2 A=A1-A2B=B1-B2 3 A=A1-A2B=B1-B2 4 A=A1+A2B=B1-B2

(3) 当A+B1o=φ，且A+B2+φ，由BoB1o可知公式中A+Bo=φ计算恒成立，此时B1A

(4) 当A+B1oφ，假设公式不成立，即A+Bo=φ，由于Bo=B1o-B2o，说明A+B1oB2oAoB1oφ，如表 3第1、第2和第3种实例，公式不成立。

(5) 当∂AB1o=φ，由BoB1o可知∂ABo=φ计算恒成立。

(6) 当∂AB1oφ，若∂AB2+=φ，由于BoB2+，公式中∂AB2o=φ计算恒成立；若∂AB+φ，假设公式不成立，即∂AB1o=φ，说明∂AB1oB2∂A∩∂B1φ或者∂AB+φ，如表 3第1和第4种实例，此时上述公式不成立。

2.3 消除不成立条件的方法

2.4 计算实例

 图 5 计算实例 Fig. 5 An example for complex regions with holes

 A1-B1-B2 A1-B1 B1+(B2-C1) R9≠[R9]T R9=[R9]T B2-C1 R9=[R9]T R9=[R9]T

 R9(A1-B1-B2，B1+(B2-C1))修正结果 R9(A1-B1-B2，B1+(B2-C1))计算结果 R9(B1+(B2-C1)，A1-B1-B2)计算结果

3 推导已知结构区域对象间的9交拓扑关系

 B1 B2 … Bj … Bn A1 A2  Ai  Am

 A B C A 14/152 16/950 16/950 B 16/950 21/11 066 21/11 066 C 16/950 21/11 066 21/11 066

ABBC的拓扑关系已知，如图 6所示，可推理出A, C的可能拓扑关系为15种，如表 8所示，进而可得到9交拓扑关系为5种，如图 7。注意的是，这里不是基于9交矩阵的推理，利用图 6中的9交矩阵得到的关系会更多，此处推理计算出的5种关系，仅是在已知ABBC的具体拓扑关系下得到的。

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

 C1 C2 C3 A1 {d，m，ct，cb，o} {d，m，o} {d} A2 {d} {d} {d}

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

4 局限性

(1) 公式不是完全成立的，其本质原因是集合操作和逻辑操作的差异性。应用此公式一方面需要小心仔细地消除不成立条件，另一方面消除过程也使得计算过程变得复杂，这在计算实例(2.4节)中有所体现。

(2) 公式与复杂区域的定义有关。本文对复杂区域的限定条件是比较严格的。比如B=B1+B2要求B1B2相离，保证了B1B2不能出现1-meet的拓扑关系，故对于一些由相邻区域的组合比如被断层切断的地层或者多尺度分析中的区域合并，无法直接使用加布尔操作公式，如图 8(a)所示。同理B=B1-B2，当广义区域与洞存在公共边界，差布尔操作公式无法使用，如图 8(b)所示。

 图 8 存在公共边界的复杂区域 Fig. 8 Complex regions with common boundaries

5 结论

﻿

 [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. DOI:10.1080/02693799408901990 [5] 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 [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. DOI:10.1145/1132863 [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. DOI:10.1080/13658810600661383 [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. DOI:10.1080/13658810151072831 [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. DOI:10.1080/13658816.2013.781607 [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. 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. 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. DOI:10.1016/j.isprsjprs.2008.02.004 [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. DOI:10.1111/tgis.1996.1.issue-3 [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. DOI:10.1080/13658816.2015.1004333
http://dx.doi.org/10.11947/j.AGCS.2017.20160209

0

#### 文章信息

WANG Zhangang, DU Qunle, WANG Xianghong

Dividing and Computing Topological Relations between Complex Regions

Acta Geodaetica et Cartographica Sinica, 2017, 46(8): 1047-1057
http://dx.doi.org/10.11947/j.AGCS.2017.20160209