A Generalized 9-Intersection Model for Topological Relations between Regions with Holes

Abstract

Current models cannot distinguish detailed topological relations between regions with holes. In order to solve this problem, a new detailed representation model for topological relations is proposed in this study. In this model, the key is to describe topological relations caused by multi-holes. Definitions of regions with holes and real objects expressed by elements of regions with holes are comprehensively analyzed, and then a practical definition of regions with holes is presented. Based on the 9-intersection model, a generalized 9-intersection model is proposed, which can completely describe detailed topological relations between regions with holes. For showing the description ability, the model is applied to describe detailed topological relations between regions with holes and detailed topological relations between objects of different complexities with the same major categories of topological relations, and a case study is designed to show the practicality of the model. The results show that the model is valid.

1. Introduction

Topological relations are used to describe topological invariants of spatial objects with topological transformation, which play important roles in data organization, spatial query, spatial analysis, spatial reasoning, and cartographic generalization [1,2]. Most objects described by topological relations are simple points, simple lines, and simple regions. Representation models for topological relations between simple regions are being perfected, and researchers have proposed classical models, such as the 4-intersection model [1], the 9-intersection model [3], the Voronoi-based 9-intersection model [4,5], the intersection and difference model [6], E-WID [7], RCC model [8,9,10,11], etc., which all distinguish eight types of topological relations between simple regions. However, in practical applications, some planar objects are not suitable to be expressed as simple regions. For instance, in order to describe the topological relations of planform changes in lakes with sandbanks, it is more suitable to express them as regions with holes, providing a comprehensive cognition of the overall changes and also recognizing the various changes in the constituent elements. Moreover, with the continuous improvement of data complexity, the demand related to describing topological relation between regions with holes, especially between regions with multi-holes, is increasing, and studies such as this one are important regarding topological relation description.

Topological relations between regions with holes are described by distinguishing intersections between elements of different ones, and different definitions of regions with holes will cause them to contain different types of elements. Therefore, definitions of regions with holes are of great significance to describing topological relations between regions with holes. Some researchers have defined a region with holes as a simple region subtracting regions surrounded by its internal holes, presenting possible topological relations between elements of regions with holes [12,13], but they have failed to propose a specific description model for topological relations between regions with holes. Egenhofer and Vasardani defined a region with holes as an internally connected region that is closed and surrounded by its outer exterior and its inner exterior; they discussed 23 types of topological relations in detail and the constraint relations between a simple region and a region with a hole [14] but failed to establish a description model for topological relations between regions with holes. Subsequent researchers have developed a variety of definitions of the region with holes based on the above two classical definitions and have described topological relations between regions with holes [15,16,17,18]. However, the complexity of topological relations between regions with holes has been limited to topological relations between a simple region and a region with two holes. In order to describe more complex topological relations between regions with holes, representation models for topological relations need to be perfected. Based on the 9(+)-intersection matrix [19], Ouyang et al. developed the 9-intersection model into the D9-intersection model, which used coding and transcoding to represent intersections between parts of regions [20]. Compared with the 9-intersection model, the D9-intersection model can effectively distinguish the topological relations between a region with one hole and another region with one hole. Chen et al. decomposed a composite object into several simple regions or point sets according to the decomposition idea, and proposed two extended 9-intersection models, which can only describe topological relations between a region with one hole and another region with one hole [21]. Shen et al. proposed the 25-intersection model by taking the interior, the outer boundary, the inner boundary, the exterior of the outer boundary, and the exterior of the inner boundary as the intersecting components [22], but this model is still limited to topological relations between a region with one hole and another region with one hole. Shen et al. proposed the 16-intersection model to describe topological relations between spherical spatial regions with holes [23], but this model is still limited to topological relations between regions with two holes, and a few topological relations between regions with two holes cannot be described. Wang et al. decomposed a complex region into some simple regions and used the formal expression to describe the composition of the decomposed object, which combined the 9-intersection model and the formal expression; with this, most topological relations between regions with holes can be comprehensively described [24], but a few topological relations between regions with holes cannot be described. Although subsequent studies improved the models above, they remain unable to achieve a detailed description of the topological relations between regions with multi-holes [25,26]. Some researchers have proposed logical and algebraic methods that can distinguish topological relations between regions with holes, but they are yet to present a specific model with mathematical matrices [27,28,29,30,31,32]. For instance, MapTree representations and the o-notation representations are widely applicable, not only suitable for regions with holes. However, they are not relation-based and cannot be calculated as a result of mathematical matrices, which is not suitable for engineering [28,29,30,31,32].

In short, the existing models cannot describe detailed topological relations between regions with multi-holes, which is mainly manifested in the weak description ability of detailed topological relations generated by multi-holes. Therefore, this study uses the description of detailed topological relations generated by multi-holes as a breakthrough to describe topological relations between regions with holes. First, we analyze the existing definitions of regions with holes and put forward a practical definition of regions with holes according to practical applications. Then, by analyzing the description elements of topological relation between regions with holes, we construct a generalized 9-intersection model based on the 9-intersection model and use the generalized 9-intersection model to describe detailed topological relations between regions with holes, and then apply binary coding and transcoding to simplify the topological relation matrices. Finally, we verify the correctness and effectiveness of our model and method by describing detailed topological relations between regions with holes of different complexity.

The remainder of the paper is structured as follows: In Section 2, the practical definition of regions with holes is outlined. In Section 3, a generalized 9-intersection model (G9IM) for topological relations is proposed based on the 9-intersection model, and we analyze the properties of G9IM. In Section 4, the description ability of G9IM, the D9-intersection model, and the 25-intersection model are compared, showing the advantages of G9IM for describing topological relations between regions with holes. Section 5 provides instances of topological relations between regions with holes. The conclusions are presented in Section 6.

2. Definitions of Regions with Holes

2.1. Existing Definitions of Regions with Holes

Definitions of regions with holes have a fundamental impact on the element selection and description ability of representation models for topological relations. Therefore, definitions of regions with holes are important to solve the detailed description of topological relations between regions with holes. Existing definitions of regions with holes can be divided into two types. In the first type, a region with holes is defined as follows: a region with holes, denoted by $A$, is composed of a simple region formed by an outer boundary, denoted by $A_w$, and several separated simple regions ($H_1$, $H_2$, ⋯), contained in $A_w$, as shown in Figure 1a. Some studies express a region with holes as a simple region $A_w$ surrounded by the outer boundary subtracted from some simple regions contained in $A_w$ [14,15,33], and some studies express a region with holes as the combination of a simple region $A_w$ surrounded by the outer boundary and some simple regions contained in $A_w$, such as $H_1$, $H_2$, ⋯ [20,21]. In general, this type of definition shows the idea of decomposing a region with holes into several complete simple regions. On this basis, representation models for the topological relations between regions with holes focus on descriptions of topological relations between each relatively independent simple region, and consider constraint topological relations between the simple region enclosed by the outer boundary and other simple regions contained in the interior, and then combine the relevant description results to indirectly describe the topological relations between regions with holes. Therefore, this type of definition can be considered an indirect expression definition of regions with holes (the indirect expression definition).

The second type of definition is as follows: a region with holes, denoted by $A$, is a closure of an inner connected region ($A^o$) enclosed by an outer boundary ($\partial A_E$) and one or more inner boundaries ($\partial A_{I1}$, $\partial A_{I2}$, ⋯), which contains two or more complement sets consisting of a generalized exterior ($\partial A_E^{-}$) and one or more inner exteriors ($\partial A_{I1}^{-}$, $\partial A_{I2}^{-}$, ⋯), [14,15,16,20,21,22,25,33], as shown in Figure 1b. This type of definition considers a region with holes as a whole and expresses it directly by defining constituent elements of the region with holes. It can be considered the direct expression definition of a region with holes (the direct expression definition). To describe the topological relations between regions with holes based on this type of definition, it is necessary to describe topological relations between elements of regions with holes, combine these topological relations in an orderly way, and finally realize the description of topological relations between regions with holes.

2.2. The Practical Definition of Regions with Holes

By analyzing the above two types of definitions of regions with holes, it is evident that they can both fully express regions with holes and their components, and there is no missing division. In addition, the two definitions have the same efficiency for the expression of regions with holes. Assuming that the number of holes in a region with holes is $m$, both types of definition require $3+2m$ elements to represent a region with holes. Taking a region with two holes as an example, both types of definition require seven elements to express a region with holes. When using the indirect expression definition, elements of the region with holes are $A_w^{-}$, $\partial A_w$, $A_w^o$, $H_1^o$, $\partial H_1$, $H_2^o$ and $\partial H_2$. When using the direct expression definition, elements of the region with holes are $A_E^{-}$, $\partial A_E$, $A^o$, $\partial A_{I1}$, $\partial A_{I2}$, $A_{I1}^{-}$, and $A_{I2}^{-}$. However, from the perspective of applications, the performance of holes in geographic information data is mostly composed of actual substances, rather than being empty. For example, in terms of land cover, holes may be sandbanks in lakes or woodlands in grasslands. The application of topological relations to describe changes in land cover if holes are considered substances different from the exterior region can give a more detailed analysis of changes in land cover. However, if the direct expression definition is adopted, a region with holes represents a geographical entity that appears partially empty inside. Even if each hole is expressed as the exterior of the inner boundary of this geographical entity, it is still inconsistent with the practical significance of the realistic objects represented by the hole. Therefore, in order for the description of topological relations between regions with holes to be more practical, this study defined a region with holes as a closure of a set formed by an outer boundary and more than one inner boundary, based on the indirect expression definition mentioned above. Holes surrounded by each inner boundary are not empty but are closures of other types of sets. A region with holes can be expressed as a closure of a set formed by a simple exterior region $A_w$ subtracting multi-holes ($H_1$, $H_2$, ⋯, $H_i$); that is,

(1)$A=\overline{A_w-H_1-H_2-\cdots -H_i}$

The exterior region $A_w$ consists of its interior $A_w^o$, its boundary $\partial A_w$, and its exterior $A_w^{-}$. $A_w$ contains holes $H_1$, $H_2$, ⋯, $H_i$, and hole $H_i$ consists of its interior $H_i^o$, its boundary $\partial H_i$, and its exterior $H_i^{-}$. The holes are separated (their boundaries cannot meet), and overlapping parts are intersection sets between the exterior region and holes that are regarded as regions, as shown in Figure 2.

3. A Generalized 9-Intersection Model for Topological Relations

3.1. Existing Representation Models for Topological Relations between Regions with Holes

In view of the fact that representation models for topological relations between simple regions cannot completely describe topological relations between regions with holes, researchers have proposed the D9-intersection model (described in Appendix A), the extended 9-intersection model, the 25-intersection model, the 9-intersection model combined with a formal expression, and the 25-intersection model combined with a formal expression. Among them, the latter two models cannot completely describe topological relations between regions with holes, while the first three models can only describe topological relations between a region with one hole and a region with one hole. The extended 9-intersection model is almost equivalent to the D9-intersection model in describing topological relations between regions with holes, except for describing topological relations between composite objects. The two different topological relations shown in Figure 3 cannot be distinguished by applying the D9-intersection model, the extended 9-intersection model, and the 25-intersection model, as shown in Table 1.

3.2. A Generalized 9-Intersection Model (G9IM) for Topological Relations and Its Properties

The existing representation models for topological relations cannot completely distinguish topological relations between regions with multi-holes. The key problem is that they do not effectively distinguish multi-holes, so they cannot completely describe detailed topological relations generated by multi-holes. In order to solve this problem, it is necessary to describe region–region, region–hole, and hole–hole topological relations in regions with holes, on the basis of distinguishing multi-holes, and these topological relations are between simple regions. In this study, a generalized 9-intersection model for topological relations (G9IM) is proposed based on the 9-intersection model. G9IM combines topological relations between different simple regions to describe the detailed topological relations between regions with holes, as expressed in Equation (2).

(2)$R_{G9IM}=\left(\begin{array}{ccc}{A}^o\cap B^o& A^o\cap \partial B& A^o\cap B^{-}\\ \partial A\cap B^o& \partial A\cap \partial B& \partial A\cap B^{-}\\ A^{-}\cap B^o& A^{-}\cap \partial B& A^{-}\cap B^{-}\end{array}\right)=\left(\begin{array}{ccc}{R}_{11}& R_{12}& R_{13}\\ R_{21}& R_{22}& R_{23}\\ R_{31}& R_{32}& R_{33}\end{array}\right)$

$A$ consists of an exterior region $A_w$, and its $m$ holes $H_{A1}$, $H_{A2}$, ⋯, $H_{Am}$, as shown in Equation (3), and $B$ consists of an exterior region $B_w$, and its $n$ holes $H_{B1}$, $H_{B2}$, ⋯, $H_{Bn}$, as shown in Equation (4).

(3)$A=\overline{A_w-H_{A1}-H_{A2}-\cdots -H_{Am}}$

(4)$B=\overline{B_w-H_{B1}-H_{B2}-\cdots -H_{Bn}}$

$A^o$ is composed of $A_w^o$, $H_{A1}^o$, $H_{A2}^o$, …, $H_{Am}^o$; $\partial A$ is composed of $\partial A_w$, $\partial H_{A1}$, $\partial H_{A2}$, …, $\partial H_{Am}$; $A^{-}$ only consists of $A_w^{-}$; $B^o$ is composed of $B_w^o$, $H_{B1}^o$, $H_{B2}^o$, …, $H_{Bn}^o$; $\partial B$ is composed of $\partial B_w$, $\partial H_{B1}$, $\partial H_{B2}$, …, $\partial H_{Bn}$; $B^{-}$ only consists of $B_w^{-}$. The intersection order among intersecting components in elements of $R_{G9IM}$ is shown in Figure 4. Take the element $A^o\cap B^o$ as an example: $A_w^o$ intersects with $B_w^o$, $H_{B1}^o$, $H_{B2}^o$, …, $H_{Bn}^o$ in turn, and $H_{A1}^o$ intersects with $B_w^o$, $H_{B1}^o$, $H_{B2}^o$, …, $H_{Bn}^o$ in turn, again, other holes intersect with $B_w^o$, $H_{B1}^o$, $H_{B2}^o$, …, $H_{Bn}^o$ in turn, until $H_{Am}^o$ intersects with $B_w^o$, $H_{B1}^o$, $H_{B2}^o$, …, $H_{Bn}^o$ in turn. The intersection order among intersecting components in other elements of $R_{G9IM}$ is determined by reference to the intersection order among intersecting components in $A^o\cap B^o$. $A^{-}$ and $B^{-}$ are all composed of one component, so there is only one intersecting component in $A^{-}\cap B^{-}$.

Therefore, $R_{11}$, $R_{12}$, $R_{21}$, and $R_{22}$ of $R_{G9IM}$ are composed of $(m+1)(n+1)$ intersecting components; $R_{13}$ and $R_{23}$ are composed of $(m+1)$ intersecting components; $R_{31}$ and $R_{32}$ are composed of $(n+1)$ intersecting components; $R_{33}$ is composed of one intersecting component. For the purpose of expressing the elements in $R_{G9IM}$ and their unity of forms, we extended the five-bit binary code proposed by OUYANG et al. (2009) [20] to the (m + 1)(n + 1)-bit binary code to represent the value of each element $R_{ij}$$(1\le i,j\le 3)$ in $R_{G9IM}$. Values of each element in $R_{G9IM}$ are shown in Table 2. $X_0$ corresponds to the first intersecting component, that is, the corresponding intersecting component of $A_w$ and $B_w$. $X_1$ corresponds to the second intersecting component, that is, the corresponding intersecting component of $A_w$ and $H_{B1}$. $X_2$ corresponds to the third intersecting component, that is, the corresponding intersecting component of $A_w$ and $H_{B2}$. In turn, $X_{mn+m+n}$ corresponds to the (m + 1) (n + 1)th intersecting component, that is, the corresponding intersecting component of $H_{Am}$ and $H_{Bn}$.

Where the values of binary codes in $R_{11}$ are as follows:

$$\begin{gathered} X_0=\{\begin{array}{c}1,A_w^o\cap B_w^o\ne \varnothing \\ 0,A_w^o\cap B_w^o=\varnothing \end{array},X_1=\{\begin{array}{c}1,A_w^o\cap B_{H1}^o\ne \varnothing \\ 0,A_w^o\cap B_{H1}^o=\varnothing \end{array},\dots ,X_n=\{\begin{array}{c}1,A_w^o\cap B_{Hn}^o\ne \varnothing \\ 0,A_w^o\cap B_{Hn}^o=\varnothing \end{array} \\ {X}_{n+1}=\{\begin{array}{c}1,H_{A1}^o\cap B_w^o\ne \varnothing \\ 0,H_{A1}^o\cap B_w^o=\varnothing \end{array},\dots ,X_{mn+m+n}=\{\begin{array}{c}1,H_{Am}^o\cap H_{Bn}^o\ne \varnothing \\ 0,H_{Am}^o\cap H_{Bn}^o=\varnothing \end{array} \end{gathered}$$

Similarly, values of binary codes in $R_{12}$, $R_{13}$, $R_{21}$, $R_{22}$, $R_{23}$, $R_{31}$, $R_{32}$, and $R_{33}$ depend on intersections of corresponding intersecting components. If intersecting components intersect, values of corresponding binary codes are 1; otherwise, values are 0.

In order to simplify values in $R_{G9IM}$, binary codes can be converted to decimal values. Then, the binary code (B) and decimal value (D) of each element in $R_{G9IM}$ corresponding to Figure 3a are as follows:

$$\begin{gathered} R_{11}=101001111\left(\mathrm{B}\right)=335\left(\mathrm{D}\right),R_{12}=101001011\left(\mathrm{B}\right)=331\left(\mathrm{D}\right),R_{13}=001001001\left(\mathrm{B}\right)=49\left(\mathrm{D}\right) \\ {R}_{21}=101001011\left(\mathrm{B}\right)=331\left(\mathrm{D}\right),R_{22}=101001111\left(\mathrm{B}\right)=335\left(\mathrm{D}\right),R_{23}=001001001\left(\mathrm{B}\right)=49\left(\mathrm{D}\right) \\ {R}_{31}=000000011\left(\mathrm{B}\right)=3\left(\mathrm{D}\right),R_{32}=000000011\left(\mathrm{B}\right)=3\left(\mathrm{D}\right),R_{33}=000000001\left(\mathrm{B}\right)=1\left(\mathrm{D}\right) \end{gathered}$$

That is, $R_{G9IM}$ corresponding to Figure 3a can be expressed as

$R_{\mathrm{a}}=\left(\begin{array}{ccc}335& 331& 49\\ 331& 335& 49\\ 3& 3& 1\end{array}\right)$

The binary codes and the decimal value of each element in $R_{G9IM}$ corresponding to Figure 3b are, respectively,

$$\begin{gathered} R_{11}=101011111\left(\mathrm{B}\right)=351\left(\mathrm{D}\right),R_{12}=101011011\left(\mathrm{B}\right)=347\left(\mathrm{D}\right),R_{13}=001001001\left(\mathrm{B}\right)=49\left(\mathrm{D}\right) \\ {R}_{21}=101011011\left(\mathrm{B}\right)=347\left(\mathrm{D}\right),R_{22}=101011111\left(\mathrm{B}\right)=351\left(\mathrm{D}\right),R_{23}=001001001\left(\mathrm{B}\right)=49\left(\mathrm{D}\right) \\ {R}_{31}=000000011\left(\mathrm{B}\right)=3\left(\mathrm{D}\right),R_{32}=000000011\left(\mathrm{B}\right)=3\left(\mathrm{D}\right),R_{33}=000000001\left(\mathrm{B}\right)=1\left(\mathrm{D}\right) \end{gathered}$$

That is, $R_{G9IM}$ corresponding to Figure 3b can be expressed as

$R_b=\left(\begin{array}{ccc}351& 347& 49\\ 347& 351& 49\\ 3& 3& 1\end{array}\right)$

It can be seen that $R_{\mathrm{a}}\ne R_b$, indicating topological relations corresponding to Figure 3a,b are different, which proves that G9IM can distinguish the complex intersection between regions with multi-holes.

Although G9IM can distinguish topological relations between regions with multi-holes, not all corresponding topological relations are of practical significance, which is manifested in logical conflicts of results of G9IM. These logical conflicts result from two aspects. One is the conflict between topological relations between regions with holes and topological relations between elements of regions with holes. The other is the conflict between topological relations between regions with holes and the definition of regions with holes. Therefore, it is necessary to eliminate non-logical description results so that G9IM can serve topological relation descriptions more efficiently. To judge whether the results of G9IM are logical, we must judge whether the results of G9IM have these above two conflicts. For instance, the exterior region of a region with holes must contain its own holes. If another object contains the exterior region but does not contain its holes, the first conflict occurs. Moreover, the exterior of a region with holes is infinite, and the second conflict arises if exteriors of different regions with holes do not intersect. Based on the above analysis, the specific properties of G9IM are as follows:

Property 1.If$A_w^o\cap B_w^o=\varnothing$, then the intersecting components in$R_{11}$,$R_{12}$and$R_{21}$are$\varnothing$, and the corresponding binary codes are 0—namely,$R_{11}$= 0,$R_{12}$= 0, and$R_{21}$= 0.

Proof 1.As $A_w^o\cap B_w^o=\varnothing$, $A_w$ must either be disjointed from or meet $B_w$. Therefore, any one of holes $H_{A1}$, $H_{A2}$, …, $H_{Am}$ and $A_w$ must be disjointed from any one of the holes $H_{B1}$, $H_{B2}$, …, $H_{Bn}$ and $B_w$, viz. the intersecting components in $R_{11}$, $R_{12}$ and $R_{21}$ are $\varnothing$. □

Property 2.If$A_w$covers or contains$B_w$, then$A_w$contains multi-holes$H_{B1}$,$H_{B2}$,…,$H_{Bn}$, and vice versa.

Proof 2.Since $B_w$ contains holes $H_{B1}$, $H_{B2}$, …, $H_{Bn}$, if $A_w$ covers or contains $B_w$, then $A_w$ contains holes $H_{B1}$, $H_{B2}$, …, $H_{Bn}$. Proof of the same, if $B_w$ covers or contains $A_w$, $B_w$ contains holes $H_{A1}$, $H_{A2}$, …, $H_{Am}$. □

Property 3.If$A_w$intersects with$B_w$, then the holes$H_{A1}$,$H_{A2}$,…,$H_{Am}$may not contain or cover$B_w$, and$H_{B1}$,$H_{B2}$,…,$H_{Bn}$may not contain or cover$A_w$.

Proof 3.Since $A_w$ contains holes $H_{A1}$, $H_{A2}$, …, $H_{Am}$, if any one of holes $H_{A1}$, $H_{A2}$, …, $H_{Am}$ contains or covers $B_w$, then $A_w$ contains $B_w$. Therefore, any one of the holes $H_{A1}$, $H_{A2}$, …, $H_{Am}$ cannot contain or cover $B_w$. Proof of the same, if $A_w$ intersects with $B_w$, any one of holes $H_{B1}$, $H_{B2}$, …, $H_{Bn}$ cannot contain or cover $A_w$. □

Property 4.If any one of the holes$H_{A1}$,$H_{A2}$,…,$H_{Am}$covers or contains$B_w$, it must contain holes$H_{B1}$,$H_{B2}$,…,$H_{Bn}$, and vice versa.

Proof 4.Since $B_w$ contains holes $H_{B1}$, $H_{B2}$, …, $H_{Bn}$, if any one of the holes $H_{A1}$, $H_{A2}$, …, $H_{Am}$ contains or covers $B_w$, then that one must contain holes $H_{B1}$, $H_{B2}$, …, $H_{Bn}$, and vice versa. □

Property 5.If any one of the holes$H_{A1}$,$H_{A2}$,…,$H_{Am}$covers or contains$B_w$or one or more of the holes$H_{B1}$,$H_{B2}$,…,$H_{Bn}$, they must be contained by$A_w$at the same time.

Proof 5.Since $A_w$ contains holes $H_{A1}$, $H_{A2}$, …, $H_{Am}$, if any one of the holes $H_{A1}$, $H_{A2}$, …, $H_{Am}$ contains or covers an object, then that object must be contained by $A_w$, and vice versa. □

Property 6.If any one of the holes$H_{A1}$,$H_{A2}$,…,$H_{Am}$intersects or meets with$B_w$, then$A_w$must contain, cover or intersect with$B_w$.

Proof 6.As $A_w$ contains holes $H_{A1}$, $H_{A2}$, …, $H_{Am}$, when any one of the holes $H_{A1}$, $H_{A2}$, …, $H_{Am}$ meets or overlaps $B_w$: 1. $A_w$ cannot equal $B_w$; otherwise, that one must meet or overlap $A_w$; 2. $A_w$ cannot meet or disjoint $B_w$; otherwise, any one of holes $H_{A1}$, $H_{A2}$, …, $H_{Am}$ must disjoint $B_w$; 3. $A_w$ cannot be contained by or covered by $B_w$; otherwise, any one of the holes $H_{A1}$, $H_{A2}$, …, $H_{Am}$ must be contained by $B_w$. □

Property 7.If$A_w$=$B_w$, then$A_w$contains the holes$H_{B1}$,$H_{B2}$,…,$H_{Bn}$, and$B_w$contains the holes$H_{A1}$,$H_{A2}$,…,$H_{Am}$.

Proof 7.As $A_w$ contains holes $H_{A1}$, $H_{A2}$, …, $H_{Am}$, If $A_w$=$B_w$, then $B_w$ contains holes $H_{A1}$, $H_{A2}$, …, $H_{Am}$. Proof of the same, $A_w$ contains holes $H_{B1}$, $H_{B2}$, …, $H_{Bn}$. □

Property 8.If any one of$H_{A1}$,$H_{A2}$,…,$H_{Am}$covers or contains$B_w$or one of$H_{B1}$,$H_{B2}$,…,$H_{Bn}$, then other holes must not contain the same one of$B_w$or$H_{B1}$,$H_{B2}$,…,$H_{Bn}$, and vice versa.

Proof 8.As holes $H_{A1}$, $H_{A2}$, …, $H_{Am}$ are separated from each other, if any one of holes $H_{A1}$, $H_{A2}$, …, $H_{Am}$ covers or contains an object, then the other holes cannot contain the same object. □

Property 9.For any$R_{G9IM}$, there must be$A_w^{-}\cap B_w^{-}\ne \varnothing$.

Proof 9.As G9IM is modeled based on 9IM, the exterior of each element intersects each other. Therefore, $A_w^{-}$ must intersect $B_w^{-}$, viz. $A_w^{-}\cap B_w^{-}\ne \varnothing$. □

4. Discussion

As mentioned above, compared with the D9-intersection model and the 25-intersection model, G9IM can describe complex intersections between regions with multi-holes. In order to further understand the difference in description ability between G9IM, the D9-intersection model, and the 25-intersection model, we compared the description ability of the above three models for different complexity objects with the same semantics and regions with multi-holes. First, we used the above three models to describe disjoints between objects with different complexities—namely, a simple region–a simple region, a simple region–a region with one hole, a simple region–a region with multi-holes, a region with one hole–a region with one hole, a region with one hole–a region with multi-holes, and a region with multi-holes–a region with multi-holes. In this study, the simple region, the region with one hole, and the region with multi-holes were all called the generalized region with holes. With the increase in the number of holes in the region with holes, the difference between the description ability of G9IM, the D9-intersection model, and the 25-intersection model for the topological relations between the generalized regions with holes becomes evident. G9IM can distinguish these different topological relations, while the D9-intersection model and the 25-intersection model cannot completely distinguish them, as shown in Table 3. After that, we used the above three models to describe the most complex topological relations between regions with multi-holes. To facilitate the description and analysis of topological relations between regions with multi-holes, the region with multi-holes was represented by the region with two holes in this example. Considering that the topological relations between regions with holes are mainly manifested as topological relations between an exterior region and another exterior region, we divided the topological relations between regions with holes into the major categories according to topological relations between the exterior regions (such as contain, overlap, disjoint, etc.), and on this basis, we divided different topological relations generated by holes into minor categories. As shown in Table 4, the D9-intersection model and the 25-intersection model can distinguish the major categories of topological relations between regions with multi-holes, while the minor categories of topological relations cannot be distinguished. However, G9IM can completely distinguish the major categories and the minor categories of topological relations.

5. Instances of Topological Relations between Regions with Holes

In the real world, there are many lakes containing sandbanks. In the geospatial world, these lakes can be represented as regions with holes, and changes in lake planforms can be expressed by topological relations between regions with holes. For example, Lake Gyaring is a large freshwater lake in the upper reaches of the Yellow River, located in the western tectonic depression of Maduro County on the Qinghai Plateau, with an area of 526 square kilometers and multiple sandbars inside it. In GLOBELAND30 (http://www.globeland30.org (26 December 2021)), water bodies of Lake Gyaring in 2000 (Figure 5a) and 2020 (Figure 5b) can be regarded as regions with holes, and the change between Lake Gyaring water bodies expressed by overlaying two water bodies (Figure 6) can be expressed by topological relations between regions with holes.

In order to show the ability of G9IM to describe topological relations between regions with holes, the 9IM, D9-intersection model, 25-intersection model, and G9IM were used to describe the topological relations of changes in the water body of Lake Gyaring from 2000 to 2020 in GLOBELAND30. Sandbars in Lake Gyaring were reduced from 3 to 0 (Figure 7) for distinguishing abilities of the four different models. The description results of the topological relation are shown in Table 5. It can be seen that G9IM could fully identify the changes in sandbars in Lake Gyaring, while the other three models could not fully distinguish them.

6. Conclusions

The previous models cannot describe the topological relations between regions with holes in detail, which is mainly manifested in the inability to describe the detailed topological relations generated by multi-holes. In this study, by analyzing the correlation between the definition of a region with holes and its topological relation description, and taking the actual representation of a region with holes into account, a practical definition of a region with holes was proposed. On this basis, G9IM was proposed by extending the 9-intersection model. By analyzing the example, we proved that G9IM can describe the refined topological relations between regions with holes and can also distinguish the topological relations between different complexity objects with the same semantics.

Although G9IM can better describe the refined topological relations between regions with holes than previous models, in practical applications, the described objects are extremely complex real objects, and the performance in GIS may involve multi-dimensional complex (composite) objects composed of multi-elements such as points, lines, regions, and volumes. Therefore, the expansion of G9IM will be the focus of our future research, as this is necessary to study the detailed description of topological relation between multi-dimensional and multi-element objects, and to provide theoretical support for the application of spatial relation theory to spatial relation description, spatial analysis, and spatial reasoning between real objects.

Author Contributions

Conceptualization, Liang Leng; methodology, Liang Leng and Xuqing Zhang; validation, Xuqing Zhang; formal analysis, Mingchang Wang and Xuefeng Niu; writing—original draft preparation, Liang Leng, Xuqing Zhang, and Fengyan Wang; writing—review and editing, Liang Leng, Xuqing Zhang, and Guodong Yang. All authors have read and agreed to the published version of the manuscript.

Funding

This research was funded by the National Natural Science Foundation of China (Project No. 42077242 and 42171407); the Open Fund of Key Laboratory of Urban Land Resources Monitoring and Simulation, MNR (Project No. KF-2019-04-080 and KF-2020-05-024); the Scientific Research Project of the 13th Five-Year Plan of Jilin province’s education department (Project No. JJKH20200999KJ).

Institutional Review Board Statement

The study did not require ethical approval.

Informed Consent Statement

Not applicable.

Data Availability Statement

The data presented in this study are available on request from the corresponding author.

Acknowledgments

The authors would like to thank the anonymous reviewers for their constructive and valuable comments that significantly contributed to improving this paper.

Conflicts of Interest

The authors declare no conflict of interest.

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Figures and Tables

Figure 1. Components in different kinds of definitions of regions with holes: (a) components in the indirect expression definition; (b) components in the direct expression definition.

Figure 2. Components in the practical definition of regions with holes.

Figure 3. Two types of overlaps between regions with holes. (a) [Forumla omitted. See PDF.] overlaps [Forumla omitted. See PDF.], and [Forumla omitted. See PDF.] is disjointed from [Forumla omitted. See PDF.]; (b) [Forumla omitted. See PDF.] overlaps [Forumla omitted. See PDF.], and [Forumla omitted. See PDF.] overlaps [Forumla omitted. See PDF.].

Figure 4. Intersection orders of intersecting components in elements of [Forumla omitted. See PDF.].

Figure 5. Water bodies of Lake Gyaring in 2000 and 2020 in GLOBELAND30: (a) water bodies of Lake Gyaring in 2000 in GLOBELAND30; (b) water bodies of Lake Gyaring in 2000 in GLOBELAND30.

Figure 6. The change between water bodies of Lake Gyaring from 2000 to 2020 in GLOBELAND30.

Figure 7. Four types of changes in the water body of Lake Gyaring from 2000 to 2020 in GLOBELAND30: (a) changes in the water body of Lake Gyaring with three sandbars; (b) changes in the water body of Lake Gyaring with two sandbars; (c) changes in the water body of Lake Gyaring with one sandbar; (d) changes in the water body of Lake Gyaring with no sandbars.

Table 1

Results of two types of overlaps between regions with holes using three kinds of topological representation models.

Objects	D9-Intersection Model	Extended 9-Intersection Model	25-Intersection Model
Topological relations in Figure 3a	$$\left(\begin{array}{ccc}0& 6& 6\\ 6& 20& 20\\ 6& 20& 20\end{array}\right)$$	$$\left(\begin{array}{ccc}0& 6& 6\\ 6& 20& 20\\ 6& 20& 20\end{array}\right)$$	$$\left(\begin{array}{ccccc}1& 1& 1& 1& 1\\ 1& 1& 1& 1& 1\\ 1& 1& 1& 1& 1\\ 1& 1& 1& 1& 1\\ 1& 1& 1& 1& 1\end{array}\right)$$
Topological relations in Figure 3b	$$\left(\begin{array}{ccc}0& 6& 6\\ 6& 20& 20\\ 6& 20& 20\end{array}\right)$$	$$\left(\begin{array}{ccc}0& 6& 6\\ 6& 20& 20\\ 6& 20& 20\end{array}\right)$$	$$\left(\begin{array}{ccccc}1& 1& 1& 1& 1\\ 1& 1& 1& 1& 1\\ 1& 1& 1& 1& 1\\ 1& 1& 1& 1& 1\\ 1& 1& 1& 1& 1\end{array}\right)$$

Table 2

Intersecting components in elements of $$R_{G9IM}$$.

	$$X_{mn+m+n}$$	…	$$X_{mn+m}$$	…	$$X_{n+1}$$	$$X_n$$	…	$$X_1$$	$$X_0$$
$$R_{11}$$	$$H_{Am}^o\cap H_{Bn}^o$$	…	$$H_{Am}^o\cap B_w^o$$	…	$$H_{A1}^o\cap B_w^o$$	$$A_w^o\cap H_{Bn}^o$$	…	$$A_w^o\cap H_{B1}^o$$	$$A_w^o\cap B_w^o$$
$$R_{12}$$	$$H_{Am}^o\cap \partial H_{Bn}$$	…	$$H_{Am}^o\cap \partial B_w$$	…	$$H_{A1}^o\cap \partial B_w$$	$$A_w^o\cap \partial H_{Bn}$$	…	$$A_w^o\cap \partial H_{B1}$$	$$A_w^o\cap \partial B_w$$
$$R_{13}$$	0	…	$$H_{Am}^o\cap B_w^{-}$$	…	$$H_{A1}^o\cap B_w^{-}$$	0	…	0	$$A_w^o\cap B_w^{-}$$
$$R_{21}$$	$$\partial H_{Am}\cap H_{Bn}^o$$	…	$$\partial H_{Am}\cap B_w^o$$	…	$$\partial H_{A1}\cap B_w^o$$	$$\partial A_w\cap H_{Bn}^o$$	…	$$\partial A_w\cap H_{B1}^o$$	$$\partial A_w\cap B_w^o$$
$$R_{22}$$	$$\partial H_{Am}\cap \partial H_{Bn}$$	…	$$\partial H_{Am}\cap \partial B_w$$	…	$$\partial H_{A1}\cap \partial B_w$$	$$\partial A_w\cap \partial H_{Bn}$$	…	$$\partial A_w\cap \partial H_{B1}$$	$$\partial A_w\cap \partial B_w$$
$$R_{23}$$	0	…	$$\partial H_{Am}\cap B_w^{-}$$	…	$$\partial H_{A1}\cap B_w^{-}$$	0	…	0	$$\partial A_w\cap B_w^{-}$$
$$R_{31}$$	0	…	0	…	0	$$A_w^{-}\cap H_{Bn}^o$$	…	$$A_w^{-}\cap H_{B1}^o$$	$$A_w^{-}\cap B_w^o$$
$$R_{32}$$	0	…	0	…	0	$$A_w^{-}\cap \partial H_{Bn}$$	…	$$A_w^{-}\cap \partial H_{B1}$$	$$A_w^{-}\cap \partial B_w$$
$$R_{33}$$	0	…	0	…	0	0	…	0	$$A_w^{-}\cap B_w^{-}$$

Table 3

Describing results of disjoints between different complexity objects by using three types of topological representation models.

Types of Objects	Topological Relation Graph	G9IM	D9-Intersection Model	25-Intersection Model
A simple region–a simple region	[Image omitted. Please see PDF.]	$$\left(\begin{array}{ccc}0& 0& 1\\ 0& 0& 1\\ 1& 1& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}1& 1& 2\\ 1& 1& 2\\ 2& 2& 2\end{array}\right)$$	$$\left(\begin{array}{ccccc}0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0\\ 1& 1& 0& 1& 0\\ 0& 0& 0& 0& 0\end{array}\right)$$
A simple region–a region with one hole	[Image omitted. Please see PDF.]	$$\left(\begin{array}{ccc}0& 0& 1\\ 0& 0& 1\\ 3& 3& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}1& 1& 2\\ 1& 1& 2\\ 2& 6& 6\end{array}\right)$$	$$\left(\begin{array}{ccccc}0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0\\ 1& 1& 1& 1& 1\\ 0& 0& 0& 0& 0\end{array}\right)$$
A simple region–a region with two holes	[Image omitted. Please see PDF.]	$$\left(\begin{array}{ccc}0& 0& 1\\ 0& 0& 1\\ 7& 7& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}1& 1& 2\\ 1& 1& 2\\ 2& 6& 6\end{array}\right)$$	$$\left(\begin{array}{ccccc}0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0\\ 1& 1& 1& 1& 1\\ 0& 0& 0& 0& 0\end{array}\right)$$
A region with one hole–a region with one hole	[Image omitted. Please see PDF.]	$$\left(\begin{array}{ccc}0& 0& 5\\ 0& 0& 5\\ 3& 3& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}1& 1& 2\\ 1& 1& 10\\ 2& 6& 14\end{array}\right)$$	$$\left(\begin{array}{ccccc}0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0\\ 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 0\end{array}\right)$$
A region with one hole–a region with two holes	[Image omitted. Please see PDF.]	$$\left(\begin{array}{ccc}0& 0& 9\\ 0& 0& 9\\ 7& 7& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}1& 1& 2\\ 1& 1& 10\\ 2& 6& 14\end{array}\right)$$	$$\left(\begin{array}{ccccc}0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0\\ 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 0\end{array}\right)$$
A region with two holes–a region with two holes	[Image omitted. Please see PDF.]	$$\left(\begin{array}{ccc}0& 0& 73\\ 0& 0& 73\\ 7& 7& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}1& 1& 2\\ 1& 1& 10\\ 2& 6& 14\end{array}\right)$$	$$\left(\begin{array}{ccccc}0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0\\ 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 0\end{array}\right)$$

Table 4

Describing results of topological relations between regions with holes using three types of topological representation models.

Types of Topological Relations	Topological Relation Graph	G9IM	D9-Intersection Model	25-Intersection Model
Disjoint	[Image omitted. Please see PDF.]	$$\left(\begin{array}{ccc}0& 0& 73\\ 0& 0& 73\\ 7& 7& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}1& 1& 2\\ 1& 1& 10\\ 2& 6& 14\end{array}\right)$$	$$\left(\begin{array}{ccccc}0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0\\ 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 0\end{array}\right)$$
Meet	[Image omitted. Please see PDF.]	$$\left(\begin{array}{ccc}0& 0& 73\\ 0& 1& 73\\ 7& 7& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}1& 1& 2\\ 1& 2& 10\\ 2& 6& 14\end{array}\right)$$	$$\left(\begin{array}{ccccc}0& 0& 0& 1& 0\\ 0& 1& 0& 1& 0\\ 0& 0& 0& 1& 0\\ 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 0\end{array}\right)$$
Overlap$$(A_w$$$$\mathrm{meets}{H}_a$$, $$A_w$$$$\mathrm{is}\mathrm{disjointed}\mathrm{from}{H}_b$$)	[Image omitted. Please see PDF.]	$$\left(\begin{array}{ccc}1& 1& 73\\ 1& 3& 73\\ 7& 7& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}0& 2& 2\\ 2& 6& 10\\ 2& 6& 14\end{array}\right)$$	$$\left(\begin{array}{ccccc}1& 1& 0& 1& 0\\ 1& 1& 1& 1& 0\\ 0& 0& 0& 1& 0\\ 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 0\end{array}\right)$$
Overlap$$(A_w$$$$\mathrm{meets}{H}_a$$, $$A_w$$$$\mathrm{meets}{H}_b$$)	[Image omitted. Please see PDF.]	$$\left(\begin{array}{ccc}1& 1& 73\\ 1& 7& 73\\ 7& 7& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}0& 2& 2\\ 2& 6& 10\\ 2& 6& 14\end{array}\right)$$	$$\left(\begin{array}{ccccc}1& 1& 0& 1& 0\\ 1& 1& 1& 1& 0\\ 0& 0& 0& 1& 0\\ 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 0\end{array}\right)$$
Overlap…	…	…	…	…
Equal$$(H_1$$$$\mathrm{meets}{H}_a$$, $$H_2$$$$\mathrm{meets}{H}_b$$)	[Image omitted. Please see PDF.]	$$\left(\begin{array}{ccc}79& 78& 0\\ 72& 273& 0\\ 0& 0& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}0& 4& 4\\ 4& 18& 1\\ 4& 1& 2\end{array}\right)$$	$$\left(\begin{array}{ccccc}1& 0& 1& 0& 1\\ 0& 1& 0& 0& 0\\ 1& 0& 1& 0& 0\\ 0& 0& 0& 1& 0\\ 1& 0& 0& 0& 0\end{array}\right)$$
Equal$$(H_1$$$$\mathrm{meets}{H}_a$$, $$H_2$$$$\mathrm{overlaps}{H}_b$$)	[Image omitted. Please see PDF.]	$$\left(\begin{array}{ccc}335& 262& 0\\ 72& 273& 0\\ 0& 0& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}0& 4& 4\\ 4& 18& 1\\ 4& 1& 18\end{array}\right)$$	$$\left(\begin{array}{ccccc}1& 0& 1& 0& 1\\ 0& 1& 0& 0& 0\\ 1& 0& 1& 0& 1\\ 0& 0& 0& 1& 0\\ 1& 0& 1& 0& 0\end{array}\right)$$
Equal …	…	…	…	…
Cover$$(H_1$$$$\mathrm{overlaps}{H}_a$$, $$H_2$$$$\mathrm{is}\mathrm{disjointed}\mathrm{from}{H}_b$$)	[Image omitted. Please see PDF.]	$$\left(\begin{array}{ccc}95& 95& 73\\ 88& 89& 73\\ 0& 0& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}0& 6& 6\\ 4& 26& 26\\ 4& 24& 26\end{array}\right)$$	$$\left(\begin{array}{ccccc}1& 1& 1& 1& 1\\ 0& 1& 0& 1& 0\\ 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 0\\ 1& 1& 1& 1& 1\end{array}\right)$$
Cover$$(H_1$$$$\mathrm{overlaps}{H}_a$$, $$H_2$$$$\mathrm{overlaps}{H}_b$$)	[Image omitted. Please see PDF.]	$$\left(\begin{array}{ccc}351& 351& 73\\ 344& 345& 73\\ 0& 0& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}0& 6& 6\\ 4& 26& 26\\ 4& 24& 26\end{array}\right)$$	$$\left(\begin{array}{ccccc}1& 1& 1& 1& 1\\ 0& 1& 0& 1& 0\\ 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 0\\ 1& 1& 1& 1& 1\end{array}\right)$$
Cover…	…	…	…	…
Covered by$$(H_1$$$$\mathrm{meets}{H}_a$$, $$H_2$$$$\mathrm{meets}{H}_b$$)	[Image omitted. Please see PDF.]	$$\left(\begin{array}{ccc}79& 6& 0\\ 79& 279& 0\\ 7& 7& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}0& 4& 4\\ 6& 22& 4\\ 6& 6& 6\end{array}\right)$$	$$\left(\begin{array}{ccccc}1& 0& 1& 0& 1\\ 1& 1& 1& 0& 1\\ 1& 0& 1& 0& 0\\ 1& 1& 1& 1& 1\\ 1& 0& 0& 0& 0\end{array}\right)$$
Covered by$$(H_1$$$$\mathrm{overlaps}{H}_a$$, $$H_2$$$$\mathrm{meets}{H}_b$$)	[Image omitted. Please see PDF.]	$$\left(\begin{array}{ccc}95& 22& 0\\ 95& 279& 0\\ 7& 7& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}0& 4& 4\\ 6& 22& 4\\ 6& 6& 22\end{array}\right)$$	$$\left(\begin{array}{ccccc}1& 0& 1& 0& 1\\ 1& 1& 1& 0& 1\\ 1& 0& 1& 0& 1\\ 1& 1& 1& 1& 1\\ 1& 0& 1& 0& 1\end{array}\right)$$
Covered by…	…	…	…	…
Contain$$(H_1$$$$\mathrm{overlaps}{H}_a$$, $$H_2$$$$\mathrm{is}\mathrm{disjointed}\mathrm{from}{H}_b$$)	[Image omitted. Please see PDF.]	$$\left(\begin{array}{ccc}95& 95& 73\\ 88& 88& 73\\ 0& 0& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}0& 6& 6\\ 4& 24& 26\\ 4& 24& 26\end{array}\right)$$	$$\left(\begin{array}{ccccc}1& 1& 1& 1& 1\\ 0& 0& 0& 1& 0\\ 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 0\\ 1& 1& 1& 1& 1\end{array}\right)$$
Contain$$(H_1$$$$\mathrm{overlaps}{H}_a$$, $$H_2$$$$\mathrm{overlaps}{H}_b$$)	[Image omitted. Please see PDF.]	$$\left(\begin{array}{ccc}351& 351& 73\\ 344& 344& 73\\ 0& 0& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}0& 6& 6\\ 4& 24& 26\\ 4& 24& 26\end{array}\right)$$	$$\left(\begin{array}{ccccc}1& 1& 1& 1& 1\\ 0& 0& 0& 1& 0\\ 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 0\\ 1& 1& 1& 1& 1\end{array}\right)$$
Contain …	…	…	…	…
Contained by$$(H_1$$$$\mathrm{meets}{H}_a$$, $$H_2$$$$\mathrm{meets}{H}_b$$)	[Image omitted. Please see PDF.]	$$\left(\begin{array}{ccc}79& 6& 0\\ 79& 278& 0\\ 7& 7& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}0& 4& 4\\ 6& 20& 4\\ 6& 6& 6\end{array}\right)$$	$$\left(\begin{array}{ccccc}1& 0& 1& 0& 1\\ 1& 0& 1& 0& 1\\ 1& 0& 1& 0& 0\\ 1& 1& 1& 1& 1\\ 1& 0& 0& 0& 0\end{array}\right)$$
Contained by$$(H_1$$$$\mathrm{overlaps}{H}_a$$, $$H_2$$$$\mathrm{meets}{H}_b$$)	[Image omitted. Please see PDF.]	$$\left(\begin{array}{ccc}95& 22& 0\\ 95& 278& 0\\ 7& 7& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}0& 4& 4\\ 6& 20& 4\\ 6& 6& 22\end{array}\right)$$	$$\left(\begin{array}{ccccc}1& 0& 1& 0& 1\\ 1& 0& 1& 0& 1\\ 1& 0& 1& 0& 1\\ 1& 1& 1& 1& 1\\ 1& 0& 1& 0& 1\end{array}\right)$$
Contained by …	…	…	…	…

Table 5

The description results of topological relation using four types of models for four types of changes in the water body of Lake Gyaring from 2000 to 2020 in GLOBELAND30.

Objects	9IM	D9-Intersection Model	25-Intersection Model	G9IM
Figure 7a	$$\left(\begin{array}{ccc}1& 1& 1\\ 1& 1& 1\\ 1& 1& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}0& 6& 6\\ 6& 18& 18\\ 6& 18& 18\end{array}\right)$$	$$\left(\begin{array}{ccccc}1& 1& 0& 1& 0\\ 1& 1& 0& 1& 0\\ 1& 0& 1& 0& 1\\ 1& 1& 0& 1& 0\\ 1& 0& 1& 0& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}38,207& 33,839& 1\\ 38,257& 33,825& 33,825\\ 1& 1& 1\end{array}\right)$$
Figure 7b	$$\left(\begin{array}{ccc}1& 1& 1\\ 1& 1& 1\\ 1& 1& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}0& 6& 6\\ 6& 18& 18\\ 6& 18& 18\end{array}\right)$$	$$\left(\begin{array}{ccccc}1& 1& 0& 1& 0\\ 1& 1& 0& 1& 0\\ 1& 0& 1& 0& 1\\ 1& 1& 0& 1& 0\\ 1& 0& 1& 0& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}351& 279& 1\\ 345& 273& 1\\ 1& 1& 1\end{array}\right)$$
Figure 7c	$$\left(\begin{array}{ccc}1& 1& 1\\ 1& 1& 1\\ 1& 1& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}0& 6& 6\\ 6& 18& 18\\ 6& 18& 18\end{array}\right)$$	$$\left(\begin{array}{ccccc}1& 1& 0& 1& 0\\ 1& 1& 0& 1& 0\\ 1& 0& 1& 0& 1\\ 1& 1& 0& 1& 0\\ 1& 0& 1& 0& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}15& 11& 1\\ 13& 9& 1\\ 1& 1& 1\end{array}\right)$$
Figure 7d	$$\left(\begin{array}{ccc}1& 1& 1\\ 1& 1& 1\\ 1& 1& 1\end{array}\right)$$	$$\left(\begin{array}{ccc}0& 2& 2\\ 2& 2& 2\\ 2& 2& 2\end{array}\right)$$	$$\left(\begin{array}{ccccc}1& 1& 0& 1& 0\\ 1& 1& 0& 1& 0\\ 0& 0& 0& 0& 0\\ 1& 1& 0& 1& 0\\ 0& 0& 0& 0& 0\end{array}\right)$$	$$\left(\begin{array}{ccc}1& 1& 1\\ 1& 1& 1\\ 1& 1& 1\end{array}\right)$$

Appendix A

According to Egenhofer and Vasardani (2007), a region with holes $$A$$ consists of an interior $$A^o$$, an inner boundary $${\partial }_{in}A$$, an outer boundary $${\partial }_{out}A$$, an outer exterior $$A^{-}$$, and an inner exterior $$A^h$$, as shown in Figure A1 [14].

Figure A1. A’s five topologically distinct and mutually exclusive parts.

The D9-intersection model is presented by Ouyang et al. (2009) in Chinese [20] and is expressed as $$R_{D9IM}=\left(\begin{array}{ccc}{A}^o\cap B^o& A^o\cap \partial B& A^o\cap \overline{B}\\ \partial A\cap B^o& \partial A\cap \partial B& \partial A\cap \overline{B}\\ \overline{A}\cap B^o& \overline{A}\cap \partial B& \overline{A}\cap \overline{B}\end{array}\right)=\left(\begin{array}{ccc}{m}_{11}& m_{12}& m_{13}\\ m_{21}& m_{22}& m_{23}\\ m_{31}& m_{32}& m_{33}\end{array}\right)$$ where $$\partial A$$ consists of $${\partial }_{in}A$$ and $${\partial }_{out}A$$, $$\overline{A}$$ consists of $$A^{-}$$ and $$A^h$$, $$m_{ij}=X_4{X}_3{X}_2{X}_1{X}_0$$ (five-bit binary code), $$1\le i,j\le 3$$, and intersecting components in elements of $$R_{D9IM}$$ are shown in Table A1.

Table A1

Intersecting components in elements of $$R_{D9IM}$$.

	$$X_4$$	$$X_3$$	$$X_2$$	$$X_1$$	$$X_0$$
$$m_{11}$$	0	0	0	0	$$\neg (A^o\cap B^o)$$
$$m_{12}$$	0	0	$$A^o\cap {\partial }_{in}B$$	$$A^o\cap {\partial }_{out}B$$	$$\neg (A^o\cap \partial B)$$
$$m_{13}$$	0	0	$$A^o\cap B^h$$	$$A^o\cap B^{-}$$	$$\neg (A^o\cap \overline{B})$$
$$m_{21}$$	0	0	$${\partial }_{in}A\cap B^o$$	$${\partial }_{out}A\cap B^o$$	$$\neg (\partial A\cap B^o)$$
$$m_{22}$$	$${\partial }_{in}A\cap {\partial }_{in}B$$	$${\partial }_{in}A\cap {\partial }_{out}B$$	$${\partial }_{out}A\cap {\partial }_{in}B$$	$${\partial }_{out}A\cap {\partial }_{out}B$$	$$\neg (\partial A\cap \partial B)$$
$$m_{23}$$	$${\partial }_{in}A\cap B^h$$	$${\partial }_{in}A\cap B^{-}$$	$${\partial }_{out}A\cap B^h$$	$${\partial }_{out}A\cap B^{-}$$	$$\neg (\partial A\cap \overline{B})$$
$$m_{31}$$	0	0	$$A_{}^h\cap B^o$$	$$A_{}^{-}\cap B^o$$	$$\neg (\overline{A}\cap B^o)$$
$$m_{32}$$	$$A_{}^h\cap {\partial }_{in}B$$	$$A_{}^h\cap {\partial }_{out}B$$	$$A_{}^{-}\cap {\partial }_{in}B$$	$$A_{}^{-}\cap {\partial }_{out}B$$	$$\neg (\overline{A}\cap \partial B)$$
$$m_{33}$$	$$A_{}^h\cap B_{}^h$$	$$A_{}^h\cap B_{}^{-}$$	$$A_{}^{-}\cap B_{}^h$$	$$A_{}^{-}\cap B_{}^{-}$$	$$\neg (\overline{A}\cap \overline{B})$$

Where values of binary codes in $$m_{11}$$ are as follows:$$X_0=\{\begin{array}{c}1,A^o\cap B^o\ne \varnothing \\ 0,A^o\cap B^o=\varnothing \end{array},X_1=X_2=X_3=X_4=0,$$

Similarly, values of binary codes in $$m_{12}$$, $$m_{13}$$, $$m_{21}$$, $$m_{22}$$, $$m_{23}$$, $$m_{31}$$, $$m_{32}$$, and $$m_{33}$$ depend on intersections of corresponding intersecting components. If intersecting components intersect, the values of corresponding binary codes are 1; otherwise, the values are 0.

In order to simplify values in $$R_{D9IM}$$, binary codes can be converted to decimal values. Then, the binary code (B) and decimal value (D) of each element in $$R_{D9IM}$$ corresponding to Figure 3a are as follows:$$\begin{gathered} m_{11}=00000\left(\mathrm{B}\right)=0\left(\mathrm{D}\right),m_{12}=00110\left(\mathrm{B}\right)=6\left(\mathrm{D}\right),m_{13}=00110\left(\mathrm{B}\right)=6\left(\mathrm{D}\right) \\ {m}_{21}=00110\left(\mathrm{B}\right)=6\left(\mathrm{D}\right),m_{22}=10100\left(\mathrm{B}\right)=20\left(\mathrm{D}\right),m_{23}=10100\left(\mathrm{B}\right)=20\left(\mathrm{D}\right) \\ {m}_{31}=00110\left(\mathrm{B}\right)=6\left(\mathrm{D}\right),m_{32}=10100\left(\mathrm{B}\right)=20\left(\mathrm{D}\right),m_{33}=10100\left(\mathrm{B}\right)=20\left(\mathrm{D}\right). \end{gathered}$$

References

1. Egenhofer, M.J.; Franzosa, R.D. Point-set topological spatial relations. Int. J. Geogr. Inf. Sci.; 1991; 5, pp. 161-174. [DOI: https://dx.doi.org/10.1080/02693799108927841]

2. Egenhofer, M.J.; Sharma, J.; Mark, D.M. A Critical Comparison of the 4-Intersection and 9-Intersection Models for Spatial Relations: Formal Analysis. Autocarto 11; McMaster, R.; Armstrong, M. American Society for Photogrammetry and Remote Sensing: Bethesda, MD, USA, 1993.

3. Egenhofer, M.J.; Herring, J.R. Categorizing binary topological relations between regions, lines and points in geographic databases. A Framework for the Definitions of Topological Relationships and an Algebraic Approach to Spatial Reasoning within This Framework; NCGIA Technical Reports; National Center for Geographic Information and Analysis: Santa Barbara, CA, USA, 1991.

4. Chen, J.; Li, C.M.; Li, Z.L.; Gold, C. A Voronoi-based 9-intersection model for spatial relations. Int. J. Geogr. Inf. Sci.; 2001; 15, pp. 201-220. [DOI: https://dx.doi.org/10.1080/13658810151072831]

5. Li, Z.L.; Zhao, R.L.; Chen, J. A voronoi-based spatial algebra for spatial relations. Prog. Nat. Sci.; 2002; 12, pp. 528-536.

6. Deng, M.; Cheng, T.; Chen, X.Y.; Li, Z.L. Multi-level Topological Relations between Spatial Regions Based Upon Topological Invariants. Geoinformatica; 2007; 11, pp. 239-267. [DOI: https://dx.doi.org/10.1007/s10707-006-0004-x]

7. Zhou, X.G.; Chen, J.; Zhan, F.B.; Li, Z.L.; Madden, M.; Zhao, R.L.; Liu, W.Z. A Euler-Number-based Topological Computation Model for Land Parcel Database Updating. Int. J. Geogr. Inf. Sci.; 2013; 10, pp. 1983-2005. [DOI: https://dx.doi.org/10.1080/13658816.2013.780607]

8. Randell, D.; Cui, Z.; Cohn, A. A spatial logical based on regions and connection. Proceedings of the 3rd International Conference on Knowledge Representation and Reasoning; Cambridge, MA, USA, 25–29 October 1992; Kaufmann, M.; San, M. Springer: Berlin/Heidelberg, Germany, New York, NY, USA, 1992.

9. Clark, B.L. Individuals and Points. Notre Dame J. Form. L.; 1985; 26, pp. 61-75. [DOI: https://dx.doi.org/10.1305/ndjfl/1093870761]

10. Clark, B.L. A Calculus of Individuals Based on ‘Connection’. Notre Dame J. Form. L.; 1981; 22, pp. 204-218. [DOI: https://dx.doi.org/10.1305/ndjfl/1093883455]

11. Li, S.J.; Ying, M.S. Extensionality of the RCC8 Composition Table. Fund. Inform.; 2003; 55, pp. 363-385.

12. Egenhofer, M.J.; Clementini, E.; Di Felice, P. Topological Relations between Regions with Holes. Int. J. Geogr. Inf. Sci.; 1994; 8, pp. 29-142.

13. Schneider, M.; Behr, T. Topological Relationships between Complex Spatial Objects. ACM Trans. Database Syst.; 2006; 31, pp. 39-81. [DOI: https://dx.doi.org/10.1145/1132863.1132865]

14. Egenhofer, M.J.; Vasardani, M. Spatial Reasoning with A Hole. Proceedings of the 8th International Conference on Spatial Information Theory: Lecture Notes in Computer Science; Winter, S.; Duckham, M.; Kulik, L. Springer: Melbourne, Australia, 2007.

15. Li, S.J. A complete classification of topological relations using the 9-intersection method. Int. J. Geogr. Inf. Sci.; 2006; 37, pp. 589-610. [DOI: https://dx.doi.org/10.1080/13658810600661383]

16. Zou, S.L.; Liu, B.; Li, D.J.; Ruan, J.; Guo, X.C. Formal description of topological relations between spatial objects with a hole. Geoinformatics 2008 and Joint Conference on GIS and Built Environment: Geo-Simulation and Virtual GIS Environments, Guangzhou, China, 28–29 June 2008; Liu, L.; Liu, X. SPIE-INT SOC OPTICAL ENGINEERING: Bellingham, WA, USA, 2009.

17. Xia, Y.P.; Ruan, J. Description of topological relation between simple region and region with a hole. Proceedings of the International Conference on Intelligent Earth Observing and Applications; Guilin, China, 23–24 October 2015; Zhou, G.; Kang, C. SPIE-INT SOC OPTICAL ENGINEERING: Bellingham, WA, USA, 2015.

18. Li, J.; Wen, C.J.; Yao, R.J.; Wu, L. A Model for Representing and Reasoning of Topological Relations of Multiple Simple Regions. Chin. J. Electron.; 2017; 26, pp. 942-946. [DOI: https://dx.doi.org/10.1049/cje.2017.07.005]

19. Kurata, Y. The 9(+)-Intersection: A Universal Framework for Modeling Topological Relations. Geogr. Inf. Sci.; 2008; 5266, pp. 181-198.

20. Ouyang, J.H.; Huo, L.L.; Liu, D.Y.; Fu, Q. Extended 9-intersection model for description of topological relations between regions with holes. J. Jilin U. Eng. Technol.; 2009; 39, pp. 1595-1600. (In Chinese)

21. Chen, Z.L.; Feng, Q.Q.; Wu, X.C. Representation Model of Topological Relations between Complex Planar Objects. Acta Geod. Cart.; 2015; 44, pp. 438-444. (In Chinese)

22. Shen, J.W.; Zhou, T.G.; Zhu, X.B. Topological Relation Representation Model between Regions with Holes. Acta Geod. Cart.; 2016; 45, pp. 722-730. (In Chinese)

23. Shen, J.W.; Zhang, L.; Chen, M. Topological relations between spherical spatial regions with holes. Int. J. Digit. Earth; 2018; 13, pp. 429-456. [DOI: https://dx.doi.org/10.1080/17538947.2018.1523958]

24. Wang, Z.G.; Du, Q.L.; Wang, X.H. Dividing and Computing Topological Relations between Complex Regions. Acta Geod. Cart.; 2017; 46, pp. 1047-1057. (In Chinese)

25. Wang, Z.G.; Wu, Z.X.; Qu, H.G.; Wang, X.H. Boolean matrix operators for computing binary topological relations between complex regions. Int. J. Geogr. Inf. Sci.; 2019; 33, pp. 99-133. [DOI: https://dx.doi.org/10.1080/13658816.2018.1527917]

26. Chen, Z.L.; Ye, W. The precise model of complex planar objects’ topological relations. Acta Geod. Cart.; 2019; 48, pp. 630-642. (In Chinese)

27. Gotts, N.M.; Gooday, J.M.; Cohn, A.G. A Connection Based Approach to Common-Sense Topological Description and Reasoning. Monist; 1996; 79, pp. 51-75. [DOI: https://dx.doi.org/10.5840/monist19967913]

28. Worboys, M. Using maptrees to characterize topological change. Spatial Information Theory. Lecture Notes in Computer Science, Proceedings of the International Conference on Spatial Information Theory, Scarborough, UK, 2–6 September 2013; Tenbrink, T.; Stell, J.; Galton, A.; Wood, Z. Springer: Berlin/Heidelberg, Germany, 2013; Volume 8116, pp. 74-90.

29. Dube, M.P.; Egenhofer, M.J. Surrounds in Partitions. Proceedings of the 22nd ACM SIGSPATIAL Advances in Geographic Information Systems; Dallas/Fort Worth, TX, USA, 4–7 November 2014; ACM: New York, NY, USA, 2014.

30. Dube, M.P.; Egenhofer, M.J.; Lewis, J.A.; Stephen, S.; Plummer, M.A. Swiss Canton Regions: A Model for Complex Objects in Geographic Partitions. Proceedings of the 12th International Conference on Spatial Information Theory (COSIT); Santa Fe, NM, USA, 12–16 October 2015; Fabrikant, S.I.; Raubal, M. Springer: Berlin/Heidelberg, Germany, 2015.

31. Lewis, J.A. A Qualitative Representation of Spatial Scenes in R2 with Regions and Lines. Ph.D. Thesis; University of Maine: Orono, ME, USA, 2019.

32. Worboys, M.; Duckham, M. Qualitative-geometric ‘surrounds’ relations between disjoint regions. Int. J. Geogr. Inf. Sci.; 2021; 35, pp. 1032-1063. [DOI: https://dx.doi.org/10.1080/13658816.2020.1859513]

33. Liu, B.; Li, D.J.; Ruan, J.; Xia, Y.P. Formal Description of Regions with Hole’s Topological Relations. Geomat. Inform. Sci.; 2009; 34, pp. 68-71. (In Chinese)