A Refined Lines/Regions and Lines/Lines Topological Relations Model Based on Whole-Whole Objects Intersection Components

Abstract

Refined topological relations play an important role in spatial database quality control. Currently, there is no unified and reasonable method to represent refined line/region and line/line topological relations in two-dimensional (2D) space. In addition, the existing independent line/region and line/line models have some drawbacks such as incomplete type discrimination and too many topological invariants. In this paper, a refined line/region and line/line topological relations are represented uniformly by the sequence, dimension, and topological type of the intersection components. To make the relevant definitions conform to the traditional cognitions in 2D Euclidean space, the (simple) spatial object is defined based on manifold topology, and the spatial intersection components are defined based on the whole-whole object intersection set. Then the topological invariant of node degree is introduced, and the adjacent point kinds (e.g., “Null”, “On”, “In”, and “Out”) are defined to distinguish the intersection component types. Excluding impossible and symmetrical types, 29 types of intersection-lines (including 21 between lines/regions and 8 between lines/lines), and 6 types of intersection-points (including 2 between lines/regions and 4 between lines/lines) are classified. On this basis, a node degree-based whole-whole object intersection sets (N-WWIS) model for refined line/region and line/line topological relations is presented, and it can be combined with the Euler number-based whole object intersection and difference (E-WID) model (coarse level) to form a hierarchical representation method of topological relations. Furthermore, a prototype system based on the N-WWIS model for automatic topological integrity checking is developed and some evaluation experiments are conducted with OpenStreetMap (OSM) data is presented based on the classification of intersection components. The experimental results show that the N-WWIS model will enable the geographic information systems (GIS) community to develop automated topological conflict checking and dealing tools for spatial data updates and quality control.

1. Introduction

Lines and regions are very important spatial objects in two-dimensional (2D) geographic information systems (GIS). The topological relations of lines/regions and lines/lines also play an important role in spatial data organization, queries, updates, and quality control. For nearly thirty years, some formal models that are suitable for representing the topological relations about lines/regions and lines/lines in 2D space have been explored or developed. The best-known models are the four-intersection (4I) model [1] and the nine-intersection (9I) model [2], which aim to describe the basic topological relations, such as disjoint, meet, overlap, cover, equal, and inside. However, both the 4I and 9I models distinguish only the content of the intersections, which leads to their weak ability to distinguish the topological relations of line/region and line/line. For example, only the 11, 19 line/region and the 12, 33 line/line topological relations can be distinguished by the 4I and 9I models, respectively [3].

Subsequently, a number of extended models based on the 4I and 9I models have been proposed to distinguish more topological details, such as the dimension extended 9-intersection model (DE+9IM) [4], the Voronoi-based 9-intersection model [5], and the 27-intersection model [6]. Furthermore, some improved models that can distinguish only line/region topological relations have been proposed to identify more topological details, such as the modeling conceptual neighborhoods of topological line-region relations [7], the 9+-intersection model for directed line segments and regions [8], the directed polyline–polygon model [9], and the directed line–directed region model [10]. In addition to these above decomposition-based models [11], some scholars have developed different topological relation models from the perspective of the spatial object as a whole, such as the RCC (region connection calculus) model [12,13], the Voronoi-based spatial algebra model [14], and the Euler number-based whole object intersection and difference (E-WID) model [15]. Among them, the best performance is the E-WID model, which has a strict theory, few set operations and strong distinguishing ability.

However, although the distinguishing ability of some of the above models has improved compared with the abilities of 4I and 9I, these models are also coarse, i.e., they represent only coarse relations. These models describe only the overall topological properties of the intersections (or differences), such as content, dimension, Euler number, etc., and thus, some of their description results are ambiguous. In other words, some different relations, especially the refined relations that have multiple intersection components, have the same description results. In some practical GIS applications, the representation and calculation of refined topological relations, especially the sequence, dimension, and topological type of each intersection (or difference) component, are very important. For example, in line/region and line/line topological conflict detection and processing for OpenStreetMap (OSM) data, the involved objects are those with non-disjoint relations, e.g., cross, meet, inside, etc. These non-disjoint relations may have two or more intersection components. As shown in Figure 1a, the volunteer’s trajectory (line) L₁ has three one-dimensional intersections (i₁, i₂, and i₃) with the same lake (region) R₁. Similarly, in Figure 1b, trajectory line L₂ has three intersection components with trajectory line L₃, including two one-dimensional intersections (i₄ and i₆) and one zero-dimensional intersection (i₅). These relations with multiple intersection components must be addressed one-by-one according to their refined topological types. Therefore, it is necessary to study the representation and calculation of the line/region and line/line refined topological relations, especially the complete classification of the topological types of each intersection component.

For the line/region at a refined level, the LRBIS (intersections set between line and region boundary) method proposed by Deng [16] is representative at present. In this method, the line-region relations are classified into 16 types of basic relations (including 1 disjoint and 15 non-disjoint relations) based on the invariants of dimension and local order, and the compound relations are decomposed into and described by a combination of a finite number of basic intersection relations. However, the definition of the intersection component in this method is not based on the whole line and whole region intersection but is based on the intersection between the whole line and the boundary of the region. Therefore, its intersection components do not follow people’s cognitive habits well, and some actual types of one-dimensional intersections between the line and region interior are omitted. For example, this method defines only three cross types (see Figure 2a–c), while the other cross types that exist (Figure 2d,e) are not defined. In other words, the LRBIS method is incomplete.

For the refined relations between lines/lines, the existing representative method was proposed by Clementini and Felice [17]. In the method, the dimension, intersection type, collinearity sense, and link orientation of the intersection components and their sequence are used to describe the refined relations. Although it also describes the type of intersection component, it focuses more on the overall topological details of lines/lines, leading to the introduction of more topological invariants that are parallel to the type of intersection component, and the description becomes complicated.

At present, there are a few other studies on the refined relations of line/region and line/line, such as the detailed model of topological and metric relations between line and region [18] and the line/line compound relation model by using the basic relations [19]. However, these methods are either still incomplete or have very complex descriptions. For example, only seven types of detailed line segments are used to describe the refined topological relations between lines/region in Reference [18], and multi-level and multi-description factors are used to describe the refined line/line relations in Reference [19]. Furthermore, although the line/region and the line/line both have and only have one-dimensional and zero-dimensional intersection components, there is currently no unified method to represent their refined relations. Therefore, the reasonable (complete and concise) and unified representation of the line/region and line/line intersection components is still an open issue in the GIS community. It is necessary to introduce an effective, concise, and unified framework for describing the line/region and line/line refined relations.

In Reference [2], Zhou et al. proposed a hierarchical description and calculation method of topological relations between two regions in 2D space. In this method, the coarse relations are represented by the E-WID model, and the refined relations are mainly represented by the Euler number-based whole-whole intersection sets (E-WWIS) model. Although some extremely complex refined relations need to be distinguished in combination with the E-WWIS and boundary-boundary intersection sets (BBIS) [20] models, the E-WWIS model has performed well in practical applications. Furthermore, the E-WWIS model is based on the whole object intersection and has a reasonable description framework. The model uses the sequence, dimension, and topological type of the intersection component to represent the refined relations, which is concise and consistent with cognitive habits. Therefore, this paper will also use the original framework of the E-WWIS model to represent the refined relations of the line/region. However, although the Euler number performs well in the discrimination of 2D intersections, it does not work well in the one-dimensional and zero-dimensional intersections. Therefore, new topological invariants should be introduced instead of Euler numbers in the E-WWIS model for the discrimination of the types of one-dimensional and zero-dimensional intersection components between lines/regions (and lines/lines). After analyzing the characteristics of the intersection components, the topological invariants of node degree and adjacent point kinds are introduced and defined, and they are used to identify the types of intersection-lines and intersection-points; thus, a node degree-based whole-whole intersection sets (N-WWIS) model is produced for the refined topology between lines/regions (and lines/lines).

The remainder of the paper is structured as follows. In Section 2, the simple spatial objects in 2D space and the line/region (and line/line) intersection components are defined, and the node degree is introduced. In Section 3, the types of intersection components are classified using node degree and adjacent point kinds. The hierarchical representation of line/region and line/line topological relations based on the E-WID (coarse level) and N-WWIS (refined level) models are discussed in Section 4. Application and experimental tests in automatic topological integrity checking are presented in Section 5. The conclusions and discussion are presented in Section 6.

2. Definition of the Intersection Component and Introduction of the Node Degree

2.1. The Definition of a Simple Spatial Object

A good definition of spatial objects is an important basis for the effective description and discrimination of topological relations. In the GIS community, spatial objects are generally considered to be subsets of Euclidean space, and their topological definitions of “interior” and “boundary” are usually based on point-set topology. According to the point-set topology in Euclidean space, lines and points have boundaries but no interior in 2D space [21,22]. However, according to the traditional definition and cognition, both lines and points have interiors in 2D space [4,5,6,7,23]. Therefore, to avoid the conflict between the theoretical basis and traditional definition, spatial objects are regarded as manifolds embedded in 2D space, and their topological definitions are based on manifold topology. Manifolds and their boundary and interior are defined as follows [24,25].

“Definition 2.1” (Manifold): Let Rⁿ be an n-dimensional Euclidean space, X is a locally Euclidean space of dimension n, and Hⁿ = {(x₁, x₂, …, x_n) ∈ Rⁿ, n ≥ 0} (half space). If each point in X has a neighborhood homeomorphic to Rⁿ, then X is an n-manifold (without boundary); if each point in X has a neighborhood either homeomorphic to Rⁿ or homeomorphic to Hⁿ, then X is an n-manifold with boundary. If a neighborhood of point p in X is homeomorphic to Rⁿ, then p is called an interior point of X, and the set of all interior points of X is called the interior (X°) of X. If any neighborhood of point p in X is homeomorphic to Hⁿ, then p is called a boundary point of X, and the set of all boundary points of X is called the boundary (∂A) of X.

Notably, a manifold itself is a topological space (local Euclidean space), so its neighborhood is only related to itself and is independent of the Euclidean space in which it is embedded, meaning that the definitions of the interior and boundary points in a manifold are also independent of the space in which the manifold is embedded (see Definition 2.1), which is different from the definitions using the point-set topology in Euclidean space. As shown in Figure 3, the region (Figure 3a), the line (Figure 3b), and the point (Figure 3c) all have interior points in R², which is consistent with traditional definitions and cognitive habits. In addition, because a manifold is a special topological space, it also has some of its topological properties, such as whether it is compact, connected, orientable, etc. Further, manifolds are not self-intersecting or touching and homogeneous (same dimension). According to the geometric characteristics of common objects in the spatial database, the (simple) spatial objects in 2D space are defined as follows in this paper.

“Definition 2.2” (Spatial objects): A spatial object is a connected, compact and orientable n-manifold (0 ≤ n ≤ 2), which can be embedded in 2D space. A simple region is a two-manifold with one connected interior and one connected boundary. A simple line is a one-manifold with one connected interior and two separate boundaries. A simple point is a zero-manifold with a connected interior but no boundary.

As shown in Figure 3, the geometry of a simple region corresponds to a polygon, and its boundary is a closed curve (Figure 3a). The geometry of a simple line corresponds to a polyline, and its boundaries are two separate endpoints (Figure 3b). The geometry of a simple point corresponds to an isolated point and has no boundary (Figure 3c).

2.2. The Definition of Intersection Components

For the description of the refined relations, the existing models are mainly based on the sequence, dimension, and topological properties (topological type) of the intersection components. In refined models, such as E-WWIS, the components are obtained based on the whole-whole object intersection. Therefore, to represent and calculate the refined line/region and line/line relations, their intersection components first need to be well defined.

The concept of components is derived from topology. The topological components of any set X form a maximal connected subset (path-connected) of X: these components are disjoint and nonempty, and their union is the whole set X [24,26]. In the GIS community, the properties of topological components are usually directly used to define the intersection or difference components between spatial objects [20,27]. However, there are still some differences between spatial components and topological components. For example, in the spatial database, a spatial component must contain its proper boundaries [2,28], whereas a topological component may not (similar to an open disk). Furthermore, even if a topological component is appropriate in itself, some of them must be further subdivided to meet the actual needs of the applications and people’s cognitive habits.

As shown in Figure 4b, the intersection set of region A and line B has four maximal connected subsets (topological components), namely, L₁ (p₁p₂p₃p₄), L₂ (p₆p₇), P₁ (p₅), and P₂ (p₈). Among them, P₁ and P₂ are zero-dimensional intersections because they are both simply isolated points, so they do not need to be subdivided. L₁ and L₂ are one-dimensional intersections, where L₂ does not need to be subdivided because its interior points are all in the interior of region A, whereas L₁ is relatively complex, and its interior points do not have the same topological property in region A. For example, points between line segments l₁ (p₁p₂) and l₃(p₃p₃) are inside A, while points between line segments l₂(p₂p₃) are on the boundary of region A. Therefore, even though intersection-line L₁ is connected, it is more reasonable to break at points p₁ and p₂, which is also more in line with people’s cognitive habits. Furthermore, if we assume that region A is a lake, line B is a road shaped by the volunteer’s trajectory. Then, l₁ (p₁p₂) may be a trail extending in the lake or a wrong trajectory segment, l₂ (p₂p₃) maybe a road along the lake, and l₃ (p₃p₃) may be a bridge across the lake. Therefore, in practical applications, the intersection-line L₁ also needs to be subdivided.

According to the definition of topological components and the characteristics of GIS spatial data, the spatial intersection components of line/region and line/line are defined as follows:

“Definition 2.3” (Spatial intersection component): Let A be a region or a line and B be a line; let I be a maximal connected subset of A∩B. If I is zero-dimensional, then I is an intersection-point of A∩B; if I is one-dimensional, assume that the interior of segment l is a maximal connected subset of A°∩I or ∂A∩I, and l is an intersection-line of A∩B and I = $U_{i=1}^n$l_i (i > 1).

Based on Definition 2.3, there are six spatial intersection components between region A and line B in Figure 4, including four intersection-lines (l₁, l₂, l₃, and l₄) and two intersection-points (P₁ and P₂), as shown in Figure 4c. Among them, the intersection-lines l₁, l₂, and l₃ are subdivided by the one-dimensional topological component L₁ (Figure 4b). In addition, it should be noted that the intersection-line in Definition 2.3 contains boundaries; that is, their topologies are equal to a polyline with two endpoints shown in Figure 3. It should be noted that to simplify the expression, the term “intersection component” (e.g., “intersection-line” and “intersection-point”) used in this article refers specifically to the spatial intersection component (e.g., “spatial intersection-line” and “spatial intersection-point”) if there is no “topological” modifier.

2.3. Introduction of the Node Degree

The basic framework of the E-WWIS model [2] can also be used to represent the refined relations of regions/regions with multiple intersections (including single intersections), as shown in Equation (1), where ‘Ni (1 ≤ i ≤ m)’, ‘di’ and ‘ti’ denote the topological sequence, dimension and type of the corresponding intersection sets (components), respectively.

R (A, B) = <N₁ (d₁, t₁), N₂ (d₂, t₂),…, N_m (d_m, t_m)>

(1)

Among the three topological invariants of sequence, dimension, and type in the E-WWIS model, the most critical is the topological type, which represents the comprehensive configuration of the topological invariants of the intersection component except for the dimension and sequence. Therefore, the classification of intersection component (set) types is the key issue in the E-WWIS model. For the 2D intersection, their types are distinguished by the Euler numbers [29] of the difference between the two regions and the intersection component, i.e., let “IR” denote the intersection component, and the 2D intersection type is distinguished by f_E (A\IR) and f_E (B\IR) [2].

Although the framework of the E-WWIS model is also suitable for describing line/region and line/line refined relations with multi-intersections, some refined one-dimensional intersection (intersection-line) types of line/region and line/line cannot be distinguished by relying solely on the “Euler number”. For example, let “IL” denote intersection-line l; in Figure 5, region (or line) A intersects line B at segment l (p₁p₂). In Figure 5a,b, the values of f_E (A\IL) and f_E (B\IL) are the same. However, the topological types of the two intersecting lines are different, in Figure 5a, the intersection-line l is completely on the boundary of region A, and in Figure 5b intersection-line l is inside region A. Similarly, the intersection-line types between two lines in Figure 5c,d are different, but their values of f_E (A\IL) and f_E (B\IL) are the same.

Figure 5a–d differ in the number of edges incident to the endpoints of the intersection-lines. In topology and graph theory, a criterion that was used to settle the Königsberg Bridge Problem by Euler in the 18th century [30], is known as the “degree of point” [31,32]. The degree of a point is the number of edges incident to the vertex. It is assumed that the degree of a vertex p in a graph is denoted deg (p); then, point p is isolated if deg (p) = 0 or is an endpoint if deg (p) = 1 (Frank, 1969). Because the topological relation is based on the binary spatial objects, the node degree calculated in this paper is the node degree of a certain point in the union of two spatial objects, and when the object is a region, it is treated as its boundary only (excluding its interior). For example, when two lines are equal, then the degree of nodes at their endpoints is one (Figure 6a); when two lines meet at their endpoints, the degree of their intersection-point is two (Figure 6b); when one of a line’s endpoints meets at the interior of the other line, the degree of their intersection-point is three (Figure 6c); when two lines intersect at their interior, the degree of their intersection-point is four (Figure 6d). For a line and a region, if the endpoint of the line is inside of the region, then its degree is one (Figure 6e); if the endpoint of the line is on the boundary of the region, then its degree is two (Figure 6f); if one part of the line is on the boundary of the region and the other part is not, then the degree of the point where the topological properties change is three (Figure 6g); If a point is an intersection-point of the line and the boundary of the region, then its degree is four (Figure 6h).

For the intersection-lines of line/region and line/line, even though the degree of their interior points are all two, there are four different cases of the degree of their endpoints, including four possible values, i.e., {1,2,3,4}. In Figure 5a, the degree of p₁ is two and the degree of p₂ is three, while in Figure 5b, the degree of p₁ is one, and the degree of p₂ is four; in Figure 5c, the degrees of p₁ and p₂ are both two, while in Figure 5d, the degree of p₁ is one and the degree of p₂ is three. The node degree, i.e., “degree of point”, can be used to distinguish different types of intersection-lines in Figure 5.

It is clear that the node degree is a topological invariant, and its ability to distinguish intersecting lines is better than that of the Euler number. In addition, because the degree of the intersection-point can also work well in the discrimination of intersection-points, the node degree is used to distinguish both types of intersection-points and intersection-lines between lines/regions and lines/lines. Therefore, a N-WWIS model can be proposed for representing the refined line/region and line/line relations.

3. Classification of Intersection-Lines and Intersection-Points Based on Node Degrees

3.1. Classification of the Intersection-Line between the Line and Region

As mentioned above, the intersection-line of the line/region can be distinguished using the degrees of the two endpoints of the intersection-line (i.e., p₁ and p₂ in Figure 7). Since there are four possible values for the degree of each endpoint, there are theoretically 16 (4 × 4) possible combinations. Excluding the impossible and symmetric values, we can obtain 8 types of possible intersection component types (i.e., the types actually exist in R²), whose node degrees are (1,1), (1,3), (1,4), (2,2), (2,3), (3,3), (3,4), and (4,4), as shown in Figure 7.

This method can fully distinguish the types of intersection-lines whose degree values of endpoints are all one or two. However, other types of intersection-lines cannot be distinguished by only degree values. For example, two pairs of different intersection-lines with degree values of three or four are shown in Figure 8. The degree values of the endpoints of the intersection-line in Figure 8a,b are both equal (1,3), and the degrees in Figure 8c,d equal (1,4).

By analyzing the two couple relations in Figure 8, we found that the main difference between them lies in the topological properties of endpoint p₂ of the intersection-lines. Endpoint p₂ in Figure 8a is the boundary point of line B, while in Figure 8b, line B has one segment following endpoint p₂ and is on the boundary of region B. In Figure 8c, the following segment of endpoint p₂ in line B is inside region A, while in Figure 8d, it is outside region A. The topological properties of the endpoints of the intersection-line are not only their node degrees; they are also related to the kinds of their adjacent points. The definition of adjacent points is described as follows.

“Definition 3.1” (Adjacent point): Let L be an intersection component between region (or line) A and line B. If L is an intersection-point, let point p be L; if L is an intersection-line, let point p be an endpoint of L. Given an arbitrarily small real number r, and let point A(p) be a point belonging to line B but not to L; if the distance between point A(p) and p is r, then the point A(p) is the adjacent point of p. If the adjacent point of p does not exist, it is named as Null. If the point is on the boundary of A, it is named as On. If the point is inside A, it is named as In. If the point is outside A, it is named as Out.

The Definition 3.1 applies not only to intersection-lines but also to intersection-points of lines/regions and lines/lines. The endpoint of the intersection-line contains one adjacent point at most, of which there are four possible kinds: Null, On, In, and Out, as shown in Figure 8. By combining the node degrees and adjacent point kinds of the endpoints, the four types of intersection-lines in Figure 8 can be distinguished.

By combining the degree of nodes (1,2,3,4) and the adjacent point kinds (Null, On, In, and Out), our model can distinguish the different 256 (4 × 4 × 4 × 4) types of intersection-lines between line/regions in theory. However, only a few of them (possible types) actually exist in R². Since the node degree values of the intersection-line endpoints only exist a total of 16 combined values (only 10 asymmetric), the possible types can be searched one by one based on these combined values and their corresponding possible adjacent point kinds. In fact, 21 types of possible and asymmetric intersection-lines are classified and found by using this method, as shown in Figure 9. It should be noted that the node degree has a higher priority than the adjacent point kinds, so the description of adjacent point kinds is sometimes ignored when it is not necessary.

The corresponding proofs of 21 types of intersection-lines between lines and regions are as follows.

• Case of degree-pairs (1,1), (1,2), (1,3) and (1,4). If the node degrees of the intersection-line endpoints are both one, the endpoints must be located inside the region and their adjacent point kinds must be Null; otherwise, at least one intersection-line endpoint will be connected with more than one edge. Therefore, there is only one type of degree-pair (1,1), as shown in Figure 9a. If one endpoint is inside the region and the other intersection-line endpoint is not inside, the other endpoint has at least three or more edges connected with it, so there is no degree-pair (1,2). If the node degree of the other endpoint is three, its adjacent point kind must be On (Figure 9b) or Null (Figure 9c), otherwise this endpoint will have 1 adjacent edge or four adjacent edges. Therefore, there are only two types of degree-pair (1,3). If the node degree of the other endpoint is four, its adjacent point kind must be Out (Figure 9d) or In (Figure 9f); otherwise, there will be less than 4 edges meeting at the endpoint.
• Case of degree-pairs (2,2), (2,3), and (2,4). If the node degrees of the intersection-line endpoints are both two, they must be on the boundary of the region and their adjacent point kinds must be Null; otherwise, the number of edges meeting at the endpoint will not be equal to two. Therefore, there is only one type of degree-pair (2,2), as shown in Figure 9h. If one endpoint is on the boundary of the region and the node degree of the other endpoint is three, its adjacent point kind must be Out (Figure 9f) or In (Figure 9g); otherwise, its endpoint will meet at two edges. Therefore, there are only two types of degree-pair (2,3) and no type of degree-pair (2,4).
• Case of degree-pairs (3,3) and (3,4). If the node degrees of the intersection-line endpoints are both three, their adjacent point kinds can be Out, In, On, or Null. Therefore, there are six (${\mathrm{C}}_4^2$) possible types of degree-pair (3,3), and they are shown in Figure 9i–n, respectively. If the node degree of one endpoint is three and the other is four, the adjacent point kind of the endpoints with node degree 3 must be Null or On, and the adjacent point kind of the endpoints with node degree 4 must be Out or In. Therefore, there are four (${\mathrm{C}}_2^1$* ${\mathrm{C}}_2^1$) types of degree-pair (3,4), as shown in Figure 9o–r.
• Case of degree-pairs (4,4). If the node degrees of the intersection-line endpoints are both 4, their adjacent point kinds must be Out or In; otherwise, there will be less than 4 edges meeting at the endpoints. Therefore, there are three asymmetric types of degree-pair (4,4), as shown in Figure 9s–u.

In contrast to the existing methods, our method is complete and can classify more types. For example, the LRBIS method can distinguish only 16 refined types (including two types of intersection-points and one type of disjoint relation). In the LRBIS method, the head-meet and tail-meet relations, HM-cover-by and TM-cover-by relations, and in-cross and out-cross relations are pairwise symmetric, corresponding to the types in Figure 9d,f,j in our method, respectively. The contained-by, EM-cover-by, point-cross, MT-cover-by, on-boundary, belly meet, BM-cover-by, and relation corresponds to the types in Figure 9a,b,d,e,h,i,u, respectively. Therefore, the LRBIS method can only distinguish 10 types of asymmetrical intersection-lines between lines and regions. This method cannot identify the remaining 11 types in Figure 9, such as those shown in Figure 9l,s, and so on. Another matter to note is that the topological intersection component in the LRBIS method is not further subdivided, which makes it insufficient in applications, such as automatic handling of topological conflicts.

3.2. Classification of the Intersection-Line between Line and Line

Compared with lines/regions, there are fewer actual types of intersection-lines between lines. Figure 10 shows the eight types of possible and asymmetric intersection-lines between lines.

Most of the intersection-lines in Figure 10 can be distinguished by the node degrees of the two endpoints of the intersection-lines, except for the (2,2) and (3,3) types. Similarly, the (2,2) type in Figure 10c,d can be distinguished by the kinds of adjacent points, i.e., “Null” and “Out”, as defined in Definition 3.1. However, they cannot be directly used to distinguish the (3,3) type, as shown in Figure 10g,h. Through analysis, although the adjacent point kinds of these two intersection-lines are all Out, the adjacent points are located on the same side of line A in Figure 10g and located on the opposite side of line A in Figure 10h. Therefore, their topological types are different, and the relevant definition is described as follows:

“Definition 3.2” (Same and opposite sides): Let I be an intersection component between lines A and B, points A(p₁) and A(p₂) be the two adjacent points of L, and c be a circle made with straight-line L(A(p₁) A(p₂)) as the diameter. Circle c can be divided into two different arcs c₁ and c₂ by line A. If points A(p₁) and A(p₂) are on the same arc, then they are on the same side as line A, and the comprehensive type of these two adjacent points is named the same side (SS). If points A(p₁) and A(p₂) are on different arcs, then they are on the opposite side of line A, and the comprehensive type of these two adjacent points is named the opposite side (OS).

The corresponding proofs of eight types of intersection-line between line and line are as follows. It should be noted that the node degree of their intersection-line endpoints cannot be 4.

• Case of degree-pairs (1,1), (1,2), and (1,3). If the node degrees of the intersection-line endpoints are both one, they must be the boundary points of the lines and their adjacent point kinds must be Null (Figure 10a). If one endpoint is on the boundary of a line and the node degree of the other endpoint is two, its adjacent point kind must be Null (Figure 10b). If the node degree of the other endpoint is three, its adjacent point kind must be Out (Figure 10e); otherwise, there will be less than three edges meeting at the endpoint. Therefore, there is only one type of degree-pairs (1,1), (1,2), and (1,3), respectively.
• Case of degree-pairs (2,2) and (2,3). If the node degrees of the intersection-line endpoints are both two, the adjacent point kind of one endpoint must be Null, and the other one’s adjacent point kind can be Null or Out. Therefore, there are two types of degree-pair (2,2), as shown in Figure 10c,d. If the node degree of one endpoint is three, its adjacent point kind must be Out (Figure 10f); otherwise, there will be less than three edges meeting at the endpoint. Therefore, there is only one type of degree-pair (2,3).
• Case of degree-pairs (3,3). If the node degree of the intersection-line endpoints is both three, their adjacent point kinds both must be Out, and their comprehensive kinds could be SS or OS. Therefore, there are two asymmetric types of degree-pair (3,3), as shown in Figure 10g,h.

Figure 11a,b show the difference in the comprehensive kinds of adjacent points for the two intersection-lines. This difference can be used to distinguish the two intersection-line node degrees of (3,3), as shown in Figure 10g,h. If the intersection-points between the line and line have two adjacent points, then the comprehensive kinds also apply, as shown in Figure 11c,d.

3.3. Classification of the Intersection-Point

Because the node degree of the intersection-point of line/region can be only three or four in R², there are only two possible types, which can be distinguished by using only node degrees. They are shown in Figure 12a,b. The node degree of the intersection-point of line/line can be two, three, or four in R². For the node degree of two or three, there is only one possible type of the line/line intersection-point, as shown in Figure 12c,d. For the node degree of four, its possible types of the line/line intersection-point need the comprehensive kinds of adjacent points to distinguish them. As shown in Figure 12e,f, the comprehensive kinds of the two adjacent points of the intersection-point are SS and OS, respectively. Finally, by combining the node degrees and adjacent point kinds, six types of possible and asymmetric intersection-points of line/region and line/line are classified, as shown in Figure 12.

4. Hierarchical Representation of the Topological Relations of Line/Region and Line/Line

Although the refined relations can accurately represent the topological relations between two objects, they require more topological details to be described and calculated, so they are usually used in fields like topological conflict detection and processing [1]. However, fields like spatial data organization and query only need coarse relations. Therefore, to meet different application requirements, it is necessary to study the hierarchical representation of topological relations between spatial objects [1,2,16,20]. In this paper, referring to the strategy in Reference [2], the E-WID model is used to represent the coarse line/region (and line/line) relations, while the N-WWIS model is used to represent the refined line/region (and line/line) relations.

4.1. Using the E-WID Model to Represent Coarse Relations

The description framework of the E-WID mode is shown in Equation (2). Where the value of f_Di denotes the content and dimension, f_E denotes the Euler number, the set operations intersection (∩), and the difference (\) are based on whole objects A and B, and their spatial components are topologically complete. The value of f_Di can be one element of {−1, 0, 1, 2, 3, 4, 5, 6} in 2D space.

$$R(A,B)=\left[\begin{array}{cc}{f}_{Di}(A\cap B)& f_E(A\cap B)\\ \begin{array}{l}{f}_{Di}(A\backslash B)\\ f_{Di}(B\backslash A)\end{array}& \begin{array}{l}{f}_E(A\backslash B)\\ f_E(B\backslash A)\end{array}\end{array}\right]$$

(2)

The E-WID model can describe the topological relations between any two spatial objects in 2D space, so it can also be used to distinguish the coarse topological relations of line/region and line/line. For line/region and line/line, there are only five cases (value of f_Di) of the intersection or difference components, i.e., empty (−1), pure zero-dimensional point (0), pure one-dimensional line (1), pure 2D region (2) and a mixture of point and line (3). The value of f_E can be any natural number, and its expression is ignored when the spatial component is empty.

For the line/region relations, although the E-WID model is coarse, it can discriminate an infinite number of coarse relations because a line and a region can have an infinite number of intersection components (or difference components), and the value of f_E can reflect the differences between them. In this paper, only the relations with a single intersection (or disjoint relation) that can be distinguished by the E-WID model are illustrated, as shown in Figure 13. Among them, Figure 13a is disjoint, and Figure 13b,c both have only one zero-dimensional intersection, but one is inside of line B and the other is on the boundary of line B; Figure 13d–j all have only one one-dimensional intersection. The topological configurations in Figure 13d–j are as follows: Line B is contained by region A (Figure 13d), B is covered by A but only one endpoint is on the boundary of A (Figure 13e), B overlaps with A but has no endpoint on the boundary of A (Figure 13f), the one-dimensional intersection is on the boundary of A (Figure 13g), B is covered by A and its endpoints are both on the boundary of A (Figure 13h), B overlaps with A and has one endpoint on the boundary of A (Figure 13i), and B crosses A (Figure 13j). It is worth noting that some elements of the matrix in Figure 13 are ignored when they are empty (there are no corresponding spatial components), and this expression follows that of Zhou et al. (2013). The specific reason is that it can show the difference between them and elements whose intersection is not empty but whose Euler number is zero.

Similarly, the E-WID model can also discriminate an infinite number of line/line coarse relations. Figure 14 shows the line/line coarse relations with a single intersection distinguished by the E-WID model. Among them, Figure 14a is disjoint, Figure 14b–d all have only one 0-dimensional intersection, and Figure 13e–j all have only one one-dimensional intersection.

4.2. Using the N-WWIS Model to Represent Refined Relations

As mentioned earlier, the coarse relations do not directly describe the dimensions and topological types of each intersection component. However, in some applications, such as conflict detection and processing, we need to deal with each intersection component according to the topological type; therefore, it is necessary to represent and calculate the relations with multiple intersection components at a refined level. Since Section 3 fully classified the intersection component types of line/region and line/line based on the node degree (and adjacent point kinds), the N-WWIS model is effectively established and can be used to represent the refined line/region and line/line relations.

Figure 15 shows two line/region relations with multiple intersection components. Although they both contain four intersection-lines and one intersection-point in Figure 5a,b, the dimension, sequence, and topological types of each component are not all the same. These two refined relations with different topological configurations are indistinguishable by the coarse model (E-WID), and the refined model (N-WWIS) must be used. The result of the N-WWIS description in Figure 15 reflects the difference between them. For example, the description result of the intersection component with sequence 2 is 2 (1, <4Out, 3On>) in Figure 15a. Where the number outside the bracket indicates its sequence number (i.e., two), the first number in the bracket indicates the dimension (i.e., 1-dimensional), and the expression <4Out, 3On> in the rest bracket indicates its topological type, which corresponds to the symmetrical type in Figure 9p. The description result of the intersection component with sequence 2 is 2 (1, 4Out, 4In) in Figure 15b, where the dimension is 1 (intersection-line) and the topological type is <4Out, 4In> (i.e., the symmetrical type in Figure 9t).

Figure 16 also shows two different line/line relations that cannot be distinguished by the E-WID model but can be distinguished by the N-WWIS model. These two models both have two intersection-lines and two intersection-points, but the types of intersection components with the same sequence are different, and the N-WWIS model can fully describe and differentiate them. For example, the intersection component with sequence number 2 is an intersection-line in Figure 16a, and its topological type is <4SS, 4SS>, i.e., the node degrees of the two endpoints are both four, and their adjacent points are on the same side of line A. In Figure 16a, the intersection component with sequence number 2 is an intersection-point, its topological type is <4SS>, i.e., its node degree is four, and the adjacent points are also on the same side of line A.

5. Experimental Application

To evaluate our refined model (N-WWIS) and its application, a prototype system based on the N-WWIS model is developed in Microsoft Visual C# 2010 environment along with Oracle database. Its user interface is shown in Figure 17.

The prototype system was intensively tested using the OpenStreetMap (OSM) data of Changsha city, Hunan Province, China, as experimental data (July 2019, as shown in Figure 17). The area of the test region is 1938 km², including 8688 traffic lines and 277 water regions, which correspond to the TRAFFIC LINE layer and WATER-AREA layer in Figure 17, respectively. Since the number of real conflicts in OSM data is unknown, 19 additional traffic lines, which have conflicting relations with water-area, are simulated to evaluate the N-WWIS model. In addition, to highlight the results of topological conflict detection, we place the relevant intersection components on the temporary work layers. For example, the intersection-lines and intersection-points between the traffic line and water region are placed in the TWINSECTLINE layer and the TWINSECTPOINT layer, respectively.

In these experiments, the traffic line is used as an example of the line, and the water region is used as an example of the region. An object-oriented (or object-relational) spatiotemporal data model [2,32] and a rule-based model transformation method [33,34] are adopted for data transformation. In addition, to deal with potential topological conflicts, a set of rules (336 for line/regions and 165 lines/lines) is developed based mainly on the N-WWIS refined relations and the attributes of spatial objects.

Taking lines/regions as an example, the strategies for topological checking and dealing are described as follows:

• Download OSM data (XML format), and convert them to the Chinese national fundamental geographic information data model using the transformation method and the object-oriented spatiotemporal data model.
• Set the tolerance (i.e., 1 m) based on experience for the computation of refined lines/regions topological relations.
• Select one line Li (1 ≤ i ≤ n) from the line data set and use the Minimal Bounding Rectangle of Li as the regions to filter out the data. This can reduce the number of regions that have no intersection with the line Li.
• Calculate the refined N-WWIS topological relations between the line Li and the filtered regions automatically, and store the non-disjoint regions and the refined descriptions of their relations to form the intersection components (include intersection-line and intersection-point) types set {A, B,…, W}.
• Return to Steps 3 and 4, start the calculation of refined relations between another line and the filtered regions and store relevant data until all objects in the line data set have been calculated.
• For each intersection component in the types set, match it to the rules set for automatically (or semi-automatically) dealing with each potential topological conflict.

The topological conflict detection results of the test data and example explanations will be expanded below.

5.1. Examples of Intersection Components between Lines and Regions

After detecting the topological conflicts between traffic lines and water regions in the test data, a total of 221 intersection components were found, including 210 intersection-lines and 11 intersection-points. For easy identification, the intersection-line types in Figure 9 and the intersection-point types in Figure 12 are named as class A (corresponding to Figure 9a), class B (Figure 9b), class C (Figure 9c), …, class V (Figure 12a), and class W (Figure 12b) in our system.

Table 1. Detection results of the intersection components types between traffic lines and water regions.

Class	Type	Number	Class	Type	Number
A	<1, 1> (Figure 9a)	5	M	<3Null, 3On> (Figure 9m)	1
B	<1, 3Null> (Figure 9b)	3	N	<3On, 3On> (Figure 9n)	1
C	<1, 3On> (Figure 9c)	15	O	<3Null, 3Out> (Figure 9o)	7
D	<1, 4Out> (Figure 9d)	17	P	<3On, 3Out> (Figure 9p)	2
E	<1, 4In> (Figure 9e)	9	Q	<3Null, 4In> (Figure 9q)	1
F	<2, 3Out> (Figure 9f)	2	R	<3On, 4In> (Figure 9r)	1
G	<2, 3In> (Figure 9g)	8	S	<4Out, 4Out> (Figure 9s)	121
H	<2, 2> (Figure 9h)	1	T	<4In, 4Out> (Figure 9t)	7
I	<3Out, 3Out> (Figure 9i)	3	U	<4In, 4In> (Figure 9u)	1
J	<3In, 3Out> (Figure 9j)	1	V	<3> (Figure 12a)	7
K	<3In, 3In> (Figure 9k)	1	W	<4> (Figure 12b)	4
L	<3Null, 3Null> (Figure 9l)	3

shows the detection results of the intersection components types between traffic lines and water regions. The number of each type of intersection components in the experimental results is shown in the third and sixth columns of Table 1. The classes H, K, M, N, Q, R, and U shown in red number are generated from simulated data. It can be seen that all the intersection components types between traffic lines and water regions can be detected by our model.

According to the attribute table of the INSECTLINE layer and INSECTPOINT layer, the types of each intersection component and the traffic and water region object involved can be queried. Figure 18a shows a partial amplification drawing of the test region, where water region R₁ has multiple intersecting-lines with traffic lines (L₁, L₂, and L₃), and Figure 18b shows the satellite image of the corresponding area. The class (type) of intersection-line between region R₁ and line L₁ is D (Figure 18c), which corresponds to type <1, 4Out> in Figure 9d; The class of intersection-line between region R₁ and line L₂ is S (Figure 18d), and its type corresponds to <4Out, 4Out> in Figure 9s. The classes of intersection-lines between region R₁ and line L₃ is I (Figure 18e), P (Figure 18f), and J (Figure 18g), and their corresponding types are <3Out, 3Out> (Figure 9k), <3On, 4Out> (Figure 9p), and <3In, 3Out > (Figure 9j), respectively.

Referring to the actual situation (satellite images), the potential topological conflicts of lines/regions in Figure 18 are addressed as follows: in Figure 18c, the part (intersection-line) of the traffic line L₁ that falls into the water region R₁ needs to be cut out; in Figure 18b, the involved data do not need to be modified because the intersection-line is usually a bridge; in Figure 18d, the position of line L₃ at the intersection needs to move to a certain position away from region R₁; in Figure 18e, the part of line L₃ at the intersection-line may need to be modified to keep it from falling into the lake; finally, in Figure 18f, the direction of line L₃ at the intersection-line needs to be adjusted so that it is not tangent to region R₁. Similarly, other types of topological conflict dealing rules are established in our system based on the topological types of intersection components and the actual situation. According to the rule set we established, the corresponding conflict addressing results in Figure 18a are shown in Figure 19.

5.2. Examples of Intersection Components between Lines

In our system, the intersection-line types in Figure 10a–h are named as class a to class h, and the intersection-point types between lines/lines in Figure 12c–f are named as class i to class l. By calculating the intersection components of traffic lines in the test data, 22 intersection-lines and 9694 intersection-points are obtained, and these components are placed in temporary layers TTINSECTLINE and TTINSECTPOINT, respectively.

Table 2. Detection result of the topological conflict between traffic lines.

Class	Corresponding Type	Number
a	<1, 1> (Figure 10a)	2
b	<1, 2> (Figure 10b)	1
c	<2Null, 2Null> (Figure 10c)	4
d	<2Out, 2Null> (Figure 10d)	1
e	<1, 3> (Figure 10e)	1
f	<2, 3> (Figure 10f)	6
g	<3SS, 3SS> (Figure 10g)	4
h	<3OS, 3OS> (Figure 10h)	3
i	<2> (Figure 12c)	3793
j	<3> (Figure 12d)	4162
k	<4SS> (Figure 12e)	25
l	<4OS> (Figure 12f)	1714

shows the detection results of the intersection components types between traffic lines. The specific numbers of the corresponding classes are shown in Table 2. It can be seen that the intersection components between traffic lines are mainly intersection-points, but there are also some intersection-lines with different types (classes).

Figure 20a shows the line/line intersection component of the local area in the test data, and Figure 20b shows the satellite image of the corresponding area. Among them, there are one intersection-line of class c (Figure 20c), one intersection-line of class f (Figure 20d), one intersection-point of class l (Figure 20e), one intersection-point of class i (Figure 20f), and three intersection-points of class j (Figure 20g–i).

In the ordinary case, when there is an intersection-line between two traffic lines, only one traffic line is reserved in the intersection part unless they are up and down. For intersecting-lines of class c (<2Null, 2Null>), it is usual to delete the covered line. However, the actual situation (satellite images) is sometimes complicated. For example, the line L₂ covered by L₁ in Figure 20c should be retained, while the overlapped parts of the intersecting line L₂ should be removed. The case of class f (<2, 3>) is similar; usually, the overlapping part of L₃ should be deleted, but according to the actual situation, the overlapping part of L₁ should be deleted (Figure 20d). For intersecting-points of class l (<4OS>), the two traffic lines of communication should be interrupted at the intersection unless they are up and down too, and the broken lines should be deleted if they are very short (Figure 20e). For intersecting-points of class i (<2>), they usually do not need to change (Figure 20f) or merge the two lines; For intersecting-points of class j (<3>), they usually do not need to change (Figure 20g–i) or one of the two lines need be interrupted at the intersection-point. According to the rule set and some manual assistance, the corresponding conflict dealing results in Figure 20a are shown in Figure 21.

6. Conclusions and Discussion

In this paper, we present a refined line/region and line/line topological relation model (N-WWIS). This model is a complement and development of the E-WID and E-WWIS hierarchical models for regions/regions. To conform to cognitive habit, the spatial objects are defined based on manifold topology rather than point set topology, and the intersection components are defined based on whole-whole (rather than decomposed) object intersection sets in this model. The topological invariant of node degree is introduced to distinguish the topological type of the intersection component between line/region and line/line. By combining node degree and adjacent point kinds (“Null”, “On”, “In”, “Out”, “SS”, and “OS”), 29 types of possible and asymmetric intersection-lines are distinguished, including 21 types of lines/regions and 8 types of lines/lines). By using this method, we also find two types of lines/regions and four types of line/line intersection-points. Therefore, a hierarchical topological relationship model has been formed for line/region and line/line, i.e., the E-WID model is used at the coarse level and the N-WWIS model is used at the refined level.

The corresponding algorithms for calculating the intersection component type of line/region and line/line are implemented, and application examples in automatic topological integrity checking are provided. The developed system was intensively tested using the OSM data of Changsha city, Hunan Province, China, as experimental data. The results of this study represent a new avenue for checking and handling automatic topological integrity.

The topological relations between regions/points, lines/points, and points/points can be completely discriminated by the E-WID model (Figure 22). Therefore, the topological relations between two simple objects in 2D space can be represented and discriminated by E-WID at a coarse level, and E-WWIS and BBIS (if necessary) are used for region/region, and N-WWIS is used for line/region and line/line at a refined level hierarchically.

As mentioned by the reference [35], applications of three-dimensional (3D) GIS have increased in scope and complexity, which in turn are driving an increasing demand for the creation and maintenance of reliable 3D GIS. However, the existing 3D data sets contain many topological inconsistencies [36], which restrict the sustainable development of related applications. On the other hand, manifold topology theory, the operand (i.e., the whole object), the set operations (i.e., intersection and difference), the topological invariants (i.e., content, dimension, Euler number, and degree of point), and some adjacent point kinds (“Null”, “On”, “In”, and “Out”) used in our hierarchical models can also be used in 3D space in theory. Therefore, the expansion of our models (including E-WID and E/N-WWIS) to 3D spatial objects based on manifold topology will be our future work.