The Precise Representation Model of Topological Relations of Complex Planar Objects

doi:10.11947/j.JGGS.2019.0303

Abstract

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 the overlapping area are leveraged to describe the topological relations of simple planar objects. The definition of traversing of the hole’s boundary and planar with a hole is 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

Zhanlong CHEN,Wen YE. The Precise Representation Model of Topological Relations of Complex Planar Objects[J]. Journal of Geodesy and Geoinformation Science, 2019, 2(3): 18-30.

Figures/Tables 19

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Fig.9

Fig.10

Fig.11

Fig.12

Fig.13

Fig.14

Fig.15

Fig.16

Tab.1

Precise combined expression algorithm"

Precise combined expression algorithm
//INOUT:R->{r₁,r₂,…,r_n} (Complex planar object collection); n(Number of complex face entities); OUTPUT: M->{m₁,m₂,m₃…}( Relation matrix set);
COMBINED-EXPRESSION(R,N,M):
foreach r∈R do //Traversing each complex region entity
foreach b∈r do //Traverse inner and outer boundaries of complex objects
If b==out then //If b is the outer boundary
foreach p∈b do //Traverse the intersection on the outer boundary in a clockwise direction
assert p==out/in //Judge the “entry” or “exit” of the point
assert p==c/a //Determine the direction between the point and the next point
assert p==C₀/C₁/T₀/T₁ //Determine how the point intersects
If p==last one then //If p is the last intersection of the current boundary
assert r∩r'==? or r∩r'!=? //Determine whether the entity r where b is located intersects with other entities
assert r∈r' or r ?r' //Determine if the entity where b is located is included in other entities
If b==in then //If b is the outer boundary
foreach p∈b do //Traverse the intersection on the inner boundary in a counterclockwise direction
assert p==out/in //Judge the entry and exit of the point
assert p==c/a //Determine the direction between the point and the next point
assert p==C₀/C₁/T₀/T₁ //Determine how the point intersects
If p==last one then //If p is the last intersection of the current boundary
assert r∩r'==? or r∩r'!=? //Determine whether the entity r where b is located intersects with other entities
assert r'∈r or r'?r //Determine if the entity in which b is located is included in other entities
produce m=R_b= $12 … - out / in out / in … - c / a c / a … - C 0 / C 1 / T 0 / T 1 C 0 / C 1 / T 0 / T … - 0 / are a r / - r' 0 / are a r / - r' … = / ?$ //Generating a combined relational matrix expression for the boundary
produce M={m₁,m₂,m₃…} //Generating a relational matrix expression
return M

Tab.1

Fig.17

Tab.2

Five basic intersections and their meta-topology matrix"

TYPES		Relationship diagram of complex planar topological			Extended meta-topology matrix
Simple region intersection					R_A= $12 out in c - C 0 C 0 0 are a B$ R_B= $12 out in c - C 0 C 0 0 are a A$
Simple region intersection					R_A= $1234 out in out in c a c - C 0 C 0 C 0 C 0 000 are a B$ R_B= $1234 out in out in c c c - C 0 C 0 C 0 C 0 000 are a A$
Intersection of region with holes (with holes only)					R_A= $1234 out in out in c - c - C 0 C 0 C 0 C 0 0 are a B 0 - B'$ R_B= $12 out in c - C 0 C 0 0 are a A$ R_B'= $12 out in a - C 0 C 0 0 - A$
Intersection of region with holes (with holes only)					R_A= $123456 out in out in out in c - c a c - C 0 C 0 C 0 C 0 C 0 C 0 0 are a B 000 - B'$ R_B= $12 out in c - C 0 C 0 0 are a A$ R_B'= $1234 out in out in a c a - C 0 C 0 C 0 C 0 000 - A$
Intersection of region with holes(The hole contains a region that coinciding with the hole)					R_A= $123456 out in out in out in c - c - c - C 0 C 0 C 0 C 0 C 0 C 0 0 are a B 0 - B' 0 are a C$ R_B= $12 out in c - C 0 C 0 0 are a A$ R_B'= $123 - out in out - a - - - C 0 C 0 T 1 - 0 - A - C = C$ R_C= $123 - out in in - c - - - C 0 C 0 T 1 - 0 are a A - B' = B'$
					R_A= $12345678910 out in out in out in out in out in c - c a c - c a c - C 0 C 0 C 0 C 0 C 0 C 0 C 0 C 0 C 0 C 0 0 are a B 000 - B' 000 are a C$ R_B= $12 out in c - C 0 C 0 0 are a A$ R_B'= $12345 - out in out in out - a a a - - - C 0 C 0 C 0 C 0 T 1 - 000 - A - B' = C$ R_C= $12345 - out in out in in - c c c - - - C 0 C 0 C 0 - T 1 - 000 are a A - B' = B'$
Intersection of region with holes(The region in the hole is tangent to the hole)					R_A= $123456 out in out in out in c - c - c - C 0 C 0 C 0 C 0 C 0 C 0 0 are a B 0 - B' 0 are a C$ R_B= $12 out in c - C 0 C 0 0 are a A$ R_B'= $123 - out in out - a - - - C 0 C 0 T 1 - 0 - A - C ? C$ R_C= $123 - out in in - c - - - C 0 C 0 T 1 - 0 are a A - B' ? B'$
Intersection of region with holes(The region in the hole is tangent to the hole)					R_A= $12345678 out in out in out in out in c - c - c a c - C 0 C 0 C 0 C 0 C 0 C 0 C 0 C 0 0 are a B 0 - B' 000 are a C$ R_B= $12 out in c - C 0 C 0 0 are a A$ R_B'= $123 - out in out - a - - - C 0 C 0 T 1 - 0 - A - C ? C$ R_C= $12345 - out in out in in - c c c - - - C 0 C 0 C 0 C 0 T 1 - 000 are a A - B' ? B'$
Intersection of region with holes(The region in the hole is tangent to the hole)					R_A= $123456 out in out in out in c - c - c - C 0 C 0 C 0 C 0 C 0 C 0 0 are a B 0 - B' 0 are a C$ R_B= $12 out in c - C 0 C 0 0 are a A$ R_B'= $12 - out in - a - - C 0 C 0 - 0 - A ? C$ R_C= $12 - out in - c - - C 0 C 0 - 0 are a A ? B'$
					R_A= $12345678 out in out in out in out in c - c - c a c - C 0 C 0 C 0 C 0 C 0 C 0 C 0 C 0 0 are a B 0 - B' 000 are a C$ R_B= $12 out in c - C 0 C 0 0 are a A$ R_B'= $12 - out in - a - - C 0 C 0 - 0 - A ? C$ R_C= $1234 - out in out in - c c c - - C 0 C 0 C 0 C 0 - 000 are a A ? B'$

Tab.2

References 25

[1]	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]	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]	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]	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]	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]	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]	TANG Xuehua, QIN kung, MENG Lingkui . A Qualitative Matrix Model of Direction-relation Based on Topological Reference[J]. Acta Geodaetica et Cartographica Sinica, 2014,43(4):396-403.DOI: 10.13485/j.cnki.11-2089.2014.0059.
[14]	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]	WU Changbin, LÜ Guonian . Spatial Topological Relationships:an Overview and Analysis[J]. Geo-Information Science, 2010,12(4):524-531.
[17]	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]	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]	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.