Calculation for Multidimensional Topological Relations in 3D Cadastre Based on Geometric Algebra

Abstract

Maintaining topological consistency is a crucial issue for 3D cadastral modeling as this helps to represent the cadastral boundary clearly and accurately. As a result, 3D cadastral data models are mainly built on the basis of topological models that allow topology to be expressed clearly. However, topological models in Euclidean space cannot directly represent objects’ geometric information. As geometric information is important in 3D spatial analysis, 3D cadastral data models based on topological models cannot realize topological calculation and analysis. Previous research has proved that geometric and topological information for cadastral objects can be integrated and represented by conformal geometric algebra (CGA) expressions. This paper aims to realize 3D topological analysis in the cadastral field using CGA’s advantages in geometric relations computation. A calculation framework is designed on the basis of the outer product to achieve the purpose of multidimensional unity for 3D cadastral topological analysis in this paper. A calculation framework of topological relations between a boundary point (or a boundary line) and a cadastral parcel is developed. A total of 13 types of topological relations between a boundary point and a cadastral parcel and 48 types of topological relations between a boundary line and a cadastral parcel are obtained. The study indicates that the advantages of CGA in multidimensional unified representation and calculation can be used to solve problems encountered by topological models in Euclidean space.

1. Introduction

Three dimensional topological analysis plays an important role in verifying the topological consistency of 3D cadastral data, updating cadastral parcels, and ensuring the accuracy of cadastral data [1,2,3,4,5,6,7,8,9,10]. It is of great significance to the development and realization of 3D cadastral management. There are several advantages of topological models such as clear topological structure expression, accurate boundary expression, easiness of updating and visualizing, and ability to meet the requirements of cadastral management for accurate boundary representation. As a result, 3D cadastral data models are mainly built on topological models [11,12,13,14,15,16,17,18,19,20,21].

Topological relation research is always a research hotspot. Many methods and theories for topology analysis have been proposed that are helpful for cadastral topology analysis [22,23,24,25]. However, topological relation analysis for cadastre is rather different from topology in other fields [8,9]. Both topologies among different cadastral parcels [8] and topologies among constructive elements with different dimensions that compose the cadastral parcels [9] need to be considered. This means that 3D cadastral models must maintain both topological and geometric information of cadastral objects. However, topological models in Euclidean space cannot realize 3D spatial analysis because they do not directly represent objects’ geometric information [26]. Geometric information for cadastral elements (boundary lines and boundary faces) cannot be directly expressed by their geometric components with lower dimensions in Euclidean space. This leads to difficulties for topological models to realize topological analysis and calculation in 3D space. To solve these problems, Shi and Wang developed different kinds of hybrid 3D cadastral data models based on both topological models and solid models [27,28]. Topological models are used to express topology and boundaries of cadastral objects, while solid models are employed to express cadastral objects’ geometric information. Cadastral objects need to be represented in the form of topological models and solid models in these hybrids 3D models, respectively, which increases the complexity of 3D cadastral models.

To avoid hybrid cadastral models and solve the problem of topological models encountered in Euclidean space, Zhang introduced geometric algebra into the expression of 3D cadastral modeling to achieve a 3D cadastral data model based on conformal geometric algebra (CGA) [29]. Different from topological models in Euclidean space, the geometric information of objects with higher dimensions can be directly represented by their topological components with lower dimensions using the outer product in CGA space. This means that both topological and geometric information for cadastral objects can be integrated in topological models in CGA space. The 3D cadastral model based on CGA provides a new solution to realize spatial analysis in 3D space based on topological models. The advantages of CGA in geometric relations calculation will be helpful to realize 3D cadastral analysis.

Apparently, there is already clear evidence that CGA-based topological relations calculation has certain advantages for multidimensional unified topological relation computation [30,31,32,33,34,35,36,37]. Yuan first adopted the Meet operator to determine the topological relations, developed the multidimensional unified topological relations calculation between triangles, and revealed a more complete topological relations classification than point set topological relation models (e.g., intersection models) [30]. However, the complex computational structure of the Meet operator is not conducive to improve the efficiency of 3D cadastral topological relations. As the Meet operator is a typical borderless model operator, it needs to make further constraint judgment on various cadastral relations through the boundary operator when it judges the topological relations of specific geometric objects. Yu proposed a calculation framework of topological relations based on the inner product, in which a boundary operator is designed to constrain the boundary of the geometric object and a topological operator is realized to calculate multidimensional topological relations [31]. However, in CGA, the geometric meaning of the inner product is not completely consistent between different dimensional objects, which makes the topological relations between segments and polygons a little bit difficult. Since different dimensional constructive elements need to be considered in the process of 3D cadastral topological relations analysis, it is of urgent need to achieve a multidimensional unified calculation of topological relation framework according to the specialty of 3D cadastral data.

In this paper, we mainly focus on the problem that topological models cannot realize spatial analysis in Euclidean space. A multidimensional unified topological analysis framework for 3D cadastre is designed on the basis of topological models in CGA. This study is a further research contribution for applying CGA into 3D cadastre.

2. 3D Cadastral Object Expression in CGA

2.1. 3D Cadastral and Spatial Topological Features

A 3D cadastral parcel that is a combination of legal boundaries defined by relevant ownership laws and physical objects in reality is a basic management unit in 3D cadastre. It is enclosed by the ownership boundary recognized by relevant laws into a closed and independent property space [17]. In order to be compatible with the existing cadastral management data and registration mode, the concept of cadastral parcels in 3D cadastral space should include both traditional parcels in two-dimensional (2D) form and parcel volumes in 3D form, as shown in Figure 1. For the situation of the consistent ownership of aboveground, underground, and surface rights, the parcel is usually expressed and managed by 2D parcels, while the inconsistency of land ownership in the vertical direction is expressed by 3D parcels. In order to unify semantics, the term cadastral parcels in this paper refers to both traditional 2D parcels and 3D cadastral parcels in the 3D cadastral space.

The topological elements of cadastral parcels in 3D cadastral space include boundary points, boundary lines, boundary surfaces, and 3D entities. In the current cadastral management in China, a boundary line is defined in the form of a straight-line segment composed of two boundary points, and a boundary surface is a plane polygon enclosed by a series of boundary lines. Boundary surfaces can be used to represent either 2D parcel planes or the ownership boundary of 3D parcel volumes.

The above-mentioned characteristics of 3D cadastral spatial data make the 3D cadastral spatial topological relations significantly different from 3D topological relations in other areas. The 3D cadastral data do not allow hanging objects (topological elements that do not attach to any elements with higher dimensions), as shown in Figure 1 [9]. For example, a hanging point is an isolated point that does not belong to any boundary line, boundary surface, or a parcel volume. A hanging line refers to an isolated line that does not belong to any parcels or boundary surfaces, or the boundary of a parcel body. A hanging surface means that it neither belongs to any 3D parcel volume, nor is it an independent 2D cadastral parcel. Since the accurate description of the spatial boundary of cadastral parcels is the basic requirement of a cadastral data model, the 3D cadastral spatial topological analysis should not only consider the topological relationship among cadastral parcels. Meanwhile, the topological constructive structure of cadastral parcels should be taken into account to ensure the accurate expression of the boundary of cadastral ownership [4]. Each cadastral parcel’s constructive topology should be unambiguous. Specifically, it is better to divide a boundary line into several parts in accordance with adjacent conditions of cadastral parcels when it passes through different adjacent parcels or boundary elements, as shown in Figure 1. The boundary line P₁P₂ is divided into two parts named Seg1 and Seg2 by a boundary point P₃.

Combining the above characteristics of the 3D cadastral spatial topological relations, we classify the 3D cadastral topological space into three types (inner space, outer space, and boundary) according to the 9-Intersection model [22], as shown in Definition 1.

Definition 1: For a cadastral parcel A in a Euclidean space $C{l}_{3,0}$ (a symbol for a category system of algebra in which $C{l}_{3,0}$ denotes Euclidean space, $C{l}_{3,1}$ denotes Homogeneous space, and $C{l}_{4,1}$ denotes Conformal space) [38,39,40,41], the whole space can be divided into three parts: parcels’ inner space $\left(A^{+}\right)$, parcels’ boundary $\left(A\right)$, parcels’ outer space $\left(A^{-}\right)$, $C{l}_{3,0}=A^{+}{\displaystyle \cup }A{\displaystyle \cup }{A}^{-}$.

It should be noticed that the internal space of the 2D parcel includes both the inner space of the plane polygon enclosed by the boundary line and all the upper and lower space of the parcel. Based on the topology classification of cadastral parcels and judgment for linear correlation of cadastral objects, more detailed topology among 3D cadastral objects can be further distinguished. Figure 2 shows the hanging line L₁ in linear correlation with the 3D parcel boundary line, and the hanging point P₁ linearly related to the 2D land boundary line and the hanging line L₂, independent of the above-mentioned parcel linearity.

2.2. CGA Representation of 3D Cadastral Structural Objects

2.2.1. Outer Product

In the CGA space, blades (an n-dimensional simplex in conformal space, a vector is a 1-dimensional blade) with higher dimensions can be expressed directly by blades with lower dimensions via the outer product [42,43]. The outer product, different from the cross product that is only applied to vectors, is one of the basic operations in CGA, which can be applied to all the dimensional objects. The definition of the outer product is as follows:

Definition 2: If $A_{\langle s\rangle }$ and $B_{\langle t\rangle }$ are any two linear independent blades in $C{L}_{p,q}$ space, where $\langle s\rangle$ and $\langle t\rangle$ are their corresponding dimensions, then the outer product between them is defined as follows:

$$A_{\langle s\rangle }^B_{\langle t\rangle }=\left(\left|A\right|\left|B\right|\sin \theta \right)i_{\langle s+t\rangle }$$

(1)

where $\left|A\right|$ and $\left|B\right|$ are modulus operations, $\theta$ is an angle between two blades, $\left(\left|A\right|\left|B\right|\sin \theta \right)$ is used for determining the size of the outer product resulting object, $i_{\langle s+t\rangle }$ is the dimension space operation of the outer product, and $\langle s+t\rangle$ is the dimension of the outer product space. When $s+t>p+q$, the result of the outer product is zero.

From Formula (1), higher dimensional geometric objects can be directly constructed by lower dimensional geometric objects via the outer product. For instance, the outer product between two linear independent one-dimensional vectors results in a 2D vector. The outer product operation satisfies the inverse commutative law. The result of the outer product calculation has directivity reflected in the symbol of the calculation result. Geometric objects constructed in different outer product orders with the same vectors are equal in size but opposite in direction. The outer product operation also satisfies the linear correlation. The result of the outer product is equal to zero if the blades involved in the outer product have linear correlation.

2.2.2. Multivector

Multivector is a special mathematical structure for connecting and organizing different dimension geometric objects in CGA [44]. Taking a multidimensional vector M in $C{l}_{3,0}$ space as an example, its expression is as follows:

$$M={\mathrm{a}}_0+{\mathrm{a}}_1{e}_1+{\mathrm{a}}_2{e}_1^e_2+{\mathrm{a}}_3{e}_2^e_3+{\mathrm{a}}_4{e}_1^e_2^e_3$$

(2)

where ${\mathrm{a}}_i$ denote scalars, and $e_i$ denote vectors. In the multivector structure, different dimensional objects (points, lines, polygon, etc.) are integrated and connected by the operation of “+”, which is only used to connect different dimensional geometric objects and does not carry out any numerical calculation. The specified dimensional geometric objects in the multivector structure can be analytically obtained by the grade operation for special geometric analysis and calculation. The multivector can also participate in the geometric analysis and calculation as a whole.

2.2.3. Boundary Points’ CGA Expression

The boundary points in cadastral space can be expressed directly by points in CGA space (1-blade), and the transformation from points in 3D Euclidean space to CGA space can be realized by Definition 3.

Definition 3: If $P\left(x,y,z\right)$ is a point in Euclidean space $C{l}_{3,0}$ then the corresponding expression of point CP in CGA space $C{l}_{4,1}$ is:

$$CP=P+\frac{P^2}{2}{e}_{\infty }+e_0=x{e}_1+y{e}_2+z{e}_3+\frac{\left(x^2+y^2+z^2\right)}{2}{e}_{\infty }+e_0$$

(3)

where $e_1,e_2,e_3,e_0,$ and $e_{\infty }$ are the five orthogonal basis vectors in CGA, e₀ denotes the origin of reference coordinates with coefficients of 1, and $e_{\infty }$ denotes the infinity point.

Taking the boundary points $P_1\left(x=2,y=6,z=0\right)$ and $P_1\left(x=3,y=5,z=8\right)$ in the 2D and 3D cadastral space as examples, according to Formula (3), the corresponding conformal coordinate points expression of the above two boundary points in CGA space can be obtained:

$$GeoPoin{t}_{\langle 1\rangle }:C{P}_1=2e_1+6e_2+20e_{\infty }+e_0$$

(4)

$$GeoPoin{t}_{\langle 1\rangle }:C{P}_2=3e_1+5e_2+8e_3+49e_{\infty }+e_0$$

(5)

2.2.4. Boundary Lines’ CGA Expression

The boundary line in the 3D cadastral space is a straight line composed of two points. In the conformal space, boundary lines’ geometric information is represented by the outer product among its two boundary points and an infinity point. Boundary lines’ expression and their composing points are integrated in a multivector structure in which topological construction relations of boundary lines are recorded accordingly. The definition of boundary lines’ CGA expression is explained as follows.

Definition 4: If $C{P}_1$ and $C{P}_2$ are two boundary points in $C{L}_{4,1}$ space, $CL$ is a boundary line constructed by $C{P}_1$ and $C{P}_2$, and if the boundary line in the CGA space is represented by the $GeoSegmen{t}_{\langle 3\rangle }$, where <3> indicates that the boundary line corresponds to the 3D subspace in the conformal space, the conformal expression of the boundary line is defined as follows:

$$GeoSegmen{t}_{\langle 3\rangle }:CL=C{P}_1\wedge C{P}_2\wedge e_{\infty }+C{P}_1+C{P}_2$$

(6)

From Formula (4), we can see that $GeoSegmen{t}_{\langle 3\rangle }$ is a multivector containing a 3-blade and two 1-blades. The 3-blade expresses the geometric information of the boundary line, and the two 1-blades represent the boundary information of the boundary line. Since there is an inverse commutative law in the outer product representation of geometric algebra, the direction information of the boundary line is contained in the symbol of the outer product expression, such as $C{P}_1\wedge C{P}_2\wedge e_{\infty }$ and $C{P}_2\wedge C{P}_1\wedge e_{\infty }$, representing two lines of equal size and opposite direction, respectively, and $C{P}_1\wedge C{P}_2\wedge e_{\infty }=-C{P}_2\wedge C{P}_1\wedge e_{\infty }$.

2.2.5. Boundary Surfaces’ CGA Expression

The boundary surfaces in 3D cadastre have two kinds of functions. They are expressed by flat and closed polygons surrounded by a series of boundary lines, which can represent both the traditional 2D cadastral parcels and the ownership boundary interface of 3D parcel volumes. The geometric information of boundary surfaces can be represented by the outer product among three composing conformal points and an infinity point in CGA space, as shown in Definition 5.

Definition 5: If $CF$ is a boundary surface in $C{L}_{4,1}$ space, $C{P}_1,C{P}_2,C{P}_3$ are three boundary points of $CF$, and $\left\{GeoSegmen{t}_{\langle 3\rangle CL}\right\}$ is the set of boundary lines of $CF$. If $GeoPolygo{n}_{\langle 4\rangle }$ denotes the boundary surface’s CGA expression in conformal space, the $\langle 4\rangle$ represents the four-dimensional subspace in the corresponding CGA space, and then the conformal expression of the boundary surface is defined as follows:

$$GeoPolygo{n}_{\langle 4\rangle }:CF=C{P}_1\wedge C{P}_2\wedge C{P}_3\wedge e_{\infty }+\left\{GeoSegmen{t}_{\langle 3\rangle CL}\right\}$$

(7)

Similar to the conformal expression of boundary lines, the conformal expression $GeoPolygo{n}_{\langle 4\rangle }$ of the boundary surface is also a multivector composed of two parts. The first part is an expression of the outer product that represents the geometric information of the boundary surfaces. The second part is a set of boundary lines’ CGA expression that constructed the boundary surfaces. Obviously, topological constructive information of the boundary surface can be represented by the second part. It should be noticed that the order of the outer product in the first part is supposed to accord with the right manipulation principle.

2.3. Expression of Geometry and Topology of Cadastral Parcels in CGA

There are several advantages of topological models such as clear topological structure, ease of visualizing and representing boundaries, and ability to meet the requirement of the cadastral parcels’ representation and management exactly. As a result, topological models are employed to represent the cadastral objects in conformal space. Different from the topological models in Euclidean space, the geometric information of the boundary points, boundary lines, and boundary surfaces in CGA space can be directly expressed by the outer product expression. Meanwhile, the topological construction information of the cadastral parcels is still expressed by the hierarchical expression structure. The geometric and topological information of cadastral parcels is integrated and represented by the multivector structure. The GeoPoint, GeoSegment, and GeoPolygon in Figure 3 corresponds to the outer product expression of the cadastral boundary points, boundary lines, and boundary surfaces in CGA space, respectively, which directly expresses the geometric information of cadastral structural elements. All the lower dimensional cadastral constructive elements’ CGA expression is integrated hierarchically in the relatively higher dimensional cadastral elements’ CGA expression in the form of boundary representation. To be more specific, all the constructive lines’ CGA expression of boundary surfaces is recorded in their CGA expressions. The hierarchical topological structure relations among the four dimensional levels of the parcel volumes, boundary surfaces, boundary lines, and boundary points are clearly embodied in the multivector structure in the form of a dimensional constructive tree (Figure 3).

3. Methods

3.1. Overall Framework

The topological relation calculation lies in the construction and expression of the underlying data model. To solve the problem of lack of direct representation of objects’ geometric information in Euclidean space, the advantages of CGA in multidimensional unified representation and integrated expression of geometric and topological relations have been introduced into 3D cadastral modeling in previous studies. CGA expressions for cadastral basic elements are proposed in the form of a series of definitions in this paper. A unification of the expanded form and direct expression for cadastral elements’ geometric information via outer product operation is proposed. In the multivector structure, the topological and geometric information of cadastral constructive elements is recorded and organized hierarchically in the form of boundary expression. The hierarchical relationships of the dimensional structure of cadastral parcels are preserved in the corresponding multivector structure.

Since the outer product can be applied to all dimensional subspaces in conformal space, a recursive method can be adopted to iterate the calculation of the outer product among different dimensional cadastral constructive elements. By summarizing the topological information hiding in the results of the outer product among different dimensional elements, the topological relations between boundary points (boundary lines) and 3D cadastral parcels can be calculated. Based on the 9-Intersection model, a topological calculation framework for boundary points and cadastral parcels in 3D space is designed in accordance with cadastral elements’ CGA expression as shown in Figure 4. Since topological and geometric information of cadastral parcels is represented by a multivector structure, a grade operator is designed to extract the specific cadastral elements’ outer product expression at the first stage. Using a recursive method at the second stage, the outer product is applied into different dimensional cadastral elements hierarchically, because the meanings of the outer product in different dimensional spaces are consistent. Direction information contained in the results of the above outer product calculation is used for identifying different types of topological relations at the third stage. Since the boundary lines in the 3D cadastral space are straight lines and are composed of two boundary points, geometric union is introduced to calculate topological relations between boundary lines and cadastral parcels based on the results of topological relations between boundary points and cadastral parcels.

3.2. Topological Space Operators

3.2.1. Grade Operator

Different dimensional geometric objects’ conformal expression contained in a multivector structure can be extracted by a grade operator, which is defined in Definition 6.

Definition 6: If CV is a cadastral parcel represented in conformal space $C{l}_{4,1}$ and $\left\{GeoExpre{e}_{\langle i\rangle }\right\}$ are the sets of outer product expressions for all i-dimensional constructive elements of CV, then the grade operator is defined as follows:

$$Grade\left(CV,i\right)=\left\{GeoExpres{s}_{\langle i\rangle }\right\}$$

(8)

It should be pointed out that i denotes the specific dimensional elements’ dimension whose range of values includes (1, 3, and 4) according to the dimension of cadastral constructive elements. Results of the grade operator are sets of all the specific dimensional elements’ outer product expressions.

3.2.2. GeoSpaceOP Operator

In the definition of cadastral elements’ CGA expressions, the geometric information of cadastral elements is represented by outer product expressions. Therefore, using the geometric information of cadastral elements contained in the outer product expression, this paper designs a GeoSpaceOP operator for computing the topological space of a single dimensional cadastral element, as shown in Definition 7.

Definition 7: If CV is an n-dimensional cadastral element and $CP$ is an arbitrary boundary-point in $C{L}_{4,1}$ space, then the outer product among the conformal expressions of CP and all n − 1 dimensional constructive elements in CV can be carried out. The spatial relationship between CP and CV can be judged by the results of outer product, which is shown as follows:

$$GeoSpaceOP\left(CP,CV\right)=CP^{\left\{Grade\left(CV,n-1\right)\right\}}_m=$$

(9)

$$\{\begin{array}{ll}\left(1\right) same blades in result with identical signs\hfill & -1\hfill \\ \left(2\right) 0 occurs, otherwise condition \left(1\right) is fulfilled\hfill & 0\hfill \\ \left(3\right) the first two conditions do not apply\hfill & +1\hfill \end{array}$$

(10)

where ${\left\{Grade\left(CV,n-1\right)\right\}}_m$ is the set of outer product expressions of all constructive boundary elements of the cadastral parcel CV. The results are a set of multivectors, and m is the number of constructive boundary elements of the cadastral parcel. Using the topological information contained in the multivectors, the calculation results are abstracted and symbolized according to the following rules: (1) If there is a value of 0 in the result of outer product, the point is on the boundary of CV, otherwise the next rule is judged. (2) If the symbols of the same dimensional subspace are the same in all the results of the outer product, the boundary point CP is located in the inner space of the CV. (3) Otherwise, it is outside the CV. It should be noticed that −1 means that point CP is inside of parcel CV, 0 means that point CP is on the boundary of parcel CV, and +1 means that point CP is outside of parcel CV.

Take a boundary surface in 3D cadastral space in Figure 5 as an example to verify Definition 7. The Euclidean coordinates of the four boundary points that make up the parcel are as follows: P₁(−0.81, −0.63, 0.13), P₂(1.09, –0.74, 0.18), P₃(1.03, 0.67, –0.14), P₄(−1.01 0.66 −0.16); the coordinates of point P_in at the interior of the boundary are (−0.01 −0.01, 0), while the coordinates of point P_out at the exterior of the boundary are (0.14, −1.6, 0.36). The outer product results among point P_in and four boundary lines of the parcel in the figure are listed as follows:

$$\begin{array}{l}{P}_{\mathrm{in}}^L_{12}=1.27\ast e_1^e_2^e_0^e_{\infty }-0.29\ast e_1^e_3^e_0^e_{\infty }-0.02\ast e_2^e_3^e_0^e_{\infty }\\ P_{\mathrm{in}}^L_{23}=1.51\ast e_1^e_2^e_0^e_{\infty }-0.34\ast e_1^e_3^e_0^e_{\infty }-0.02\ast e_2^e_3^e_0^e_{\infty }\\ P_{\mathrm{in}}^L_{34}=1.38\ast e_1^e_2^e_0^e_{\infty }-0.31\ast e_1^e_3^e_0^e_{\infty }-0.01\ast e_2^e_3^e_0^e_{\infty }\\ P_{\mathrm{in}}^L_{41}=1.16\ast e_1^e_2^e_0^e_{\infty }-0.26\ast e_1^e_3^e_0^e_{\infty }-0.01\ast e_2^e_3^e_0^e_{\infty }\end{array}$$

(11)

Since all the corresponding dimensional subspaces’ symbols are consistent in the outer product results, it is possible to determine that the point P_in is located inside the parcel according to the first rule in Definition 7.

Then, the outer product results between point P_out and four boundary lines of the parcel in the figure are listed as follows:

$$\begin{array}{l}{P}_{\mathrm{out}}^L_{12}=-1.74\ast e_1^e_2^e_0^e_{\infty }+0.39\ast e_1^e_3^e_0^e_{\infty }+0.02\ast e_2^e_3^e_0^e_{\infty }\\ P_{\mathrm{out}}^L_{23}=1.39\ast e_1^e_2^e_0^e_{\infty }-0.31\ast e_1^e_3^e_0^e_{\infty }-0.02\ast e_2^e_3^e_0^e_{\infty }\\ P_{\mathrm{out}}^L_{34}=4.62\ast e_1^e_2^e_0^e_{\infty }-1.04\ast e_1^e_3^e_0^e_{\infty }-0.05\ast e_2^e_3^e_0^e_{\infty }\\ P_{\mathrm{out}}^L_{41}=1.03\ast e_1^e_2^e_0^e_{\infty }-0.23\ast e_1^e_3^e_0^e_{\infty }-0.02\ast e_2^e_3^e_0^e_{\infty }\end{array}$$

(12)

As all the corresponding dimensional subspaces’ symbols are inconsistent in the outer product results, it is possible to determine that the point P_out is located outside the parcel according to the third rule in Definition 7.

3.3. Calculation of Topological Relations between a Boundary Point and a Parcel

The GeoSpaceOP operator is designed to identify topological relations between boundary points and cadastral elements with a single dimension in 3D space. On the basis of Definition 7, we define the TopoOP operator to calculate more accurate topological relations between boundary points and cadastral parcels. Geometric intersection operation is conducted among GeoSpaceOP’s results between the boundary points and multidimensional constructive elements of cadastral parcels. The TopoOP operator is shown in Definition 8.

Definition 8: TopoOP is an operator for computing 3D cadastral spatial topological relations. The rules for calculating the topological relations between a cadastral parcel CV and a boundary point CP are as follows:

$$TopoOP\left(CP,CV\right)=GeoSpaceOP\left(CP,Grade\left(CV,n\right)\right){\displaystyle \cap }\dots {\displaystyle \cap }GeoSpaceOP\left(CP,Grade\left(CV,1\right)\right)$$

(13)

where ${\displaystyle \cap }$ is a geometric intersection operation.

In conformal space, the outer product can be extended to all dimensional subspace [39]. Accordingly, a framework for calculating the topological relationship between boundary points and cadastral parcels in 3D cadastral space is proposed on the basis of previous definitions and a recursive method (Figure 6). The calculation process consists of three main phases, as shown in

Table 1. Illustration of topological computation steps and results shown in Figure 7.

Calculation Process	Outer Product	Sign of End Note	Topological Relation	Example in Figure 7	Operation
First step	a boundary face and a point	+1	outside	Figure 7a, Figure 7h	finished
		−1	inside	Figure 7g	finished
		0	boundary		next step
Second step	a boundary line and a point	+1	outside	Figure 7c, Figure 7i	finished
		−1	inside	Figure 7b, Figure 7k	finished
		0	boundary		next step
Third step	two boundary points and a point	+1	outside	Figure 7d, Figure 7j	finished
		−1	inside	Figure 7e, Figure 7l	finished
		0	boundary	Figure 7f, Figure 7m	finished

: (1) The highest dimensional elements’ outer product expressions in the multivector structure of cadastral parcels are extracted by the grade operator, and the GeoSpaceOP operator is applied to the boundary point and the highest dimensional elements; (2) Results of GeoSpaceOP operation in the previous step need to analyze whether a zero exists. If there is a zero value existing in the results, the boundary point is in linear correlation with the corresponding constructive element (equal to zero) of the parcels. The previous step should be iterated with the boundary point and the corresponding lower dimensional constructive elements until the results of the outer product do not contain 0 or all relative dimensional boundary elements have participated in the outer product calculation; (3) The TopoOP operator is used to calculate the geometric intersection of topological relations between boundary points and cadastral constructive elements with different dimensions, and the topological relations between boundary points and cadastral parcels can be obtained at last.

The essence of topological relations calculation for 3D cadastre based on CGA is to iterate the GeoSpaceOP operator from high-dimensional constructive elements to low-dimensional constructive elements according to certain conditions. The geometric intersection for results of GeoSpaceOP operators is calculated with the TopoOP operator to obtain the topological relations.

Since cadastral parcels in 3D space can be classified into traditional 2D parcels and 3D parcel volumes, topological relations between a boundary point and a cadastral parcel are divided into two categories accordingly. Topological relations between a boundary point and a cadastral parcel calculated by the CGA method are shown in Figure 7. There are 13 kinds of topological relations being distinguished in total. These two cases mentioned above are deduced respectively in this paper, because there are some differences in topological relation types among the boundary point and the 2D parcel as well as the 3D parcel volume. The topological relations in the graph consist of two parts: geometric algebra calculation result display and topological relations graphic display. Taking the boundary point and a 2D parcel in the graph as an example, in the process of calculating topological relations, the outer product of the boundary point and the 2D parcel’s CGA expression (the highest dimensional elements’ CGA expression in the multivector) is calculated first. If the result of the outer product is equal to 0, the outer product will be applied to the lower dimensional elements of the current boundary object. Relations between the result of the outer product and the topologies of different types in Figure 7 are illustrated in Table 1.

3.4. Calculation of Topological Relations between Boundary Lines and Parcels

The 3D cadastral boundary line is a straight line composed of two boundary points. According to the topological relations between the two boundary points and the cadastral parcel, we can derive the spatial topological relations between the boundary line and the cadastral parcel. The algorithm flow of judging the topological relations between the boundary line and the cadastral parcel is shown in Figure 8 and consists of three phases: the first step is to carry out the operation of GeoSpaceOP between the two boundary points composing the boundary line and the different dimensional constructive elements of the cadastral parcel. The second step is to calculate the topological relations between the two boundary points composing the boundary line and the cadastral parcel, respectively. Thirdly, the operation of geometric union is employed to calculate the topological relations between the boundary line and the cadastral parcel according to the result of the topological relation between each boundary point and the cadastral parcel.

According to the topological relations and calculation framework between a boundary line and a cadastral parcel in 3D space, 21 types of topological relations between a boundary line and a traditional 2D parcel are obtained, and 27 types of topological relations between a boundary line and a 3D parcel are obtained, as displayed in Figure 9. The graph of topological relations between a boundary line and a cadastral parcel consists of symbolic processing of algebraic calculation results and geometric presentation of topological relation types. In the process of symbolic calculation of topological relation algebra, 0 indicates that the current boundary point is located at the boundary of the current constructive elements of the cadastral parcel; −1 means the current boundary point is in the interior of the current constructive elements of the cadastral parcel, while +1 indicates that the current boundary point lies outside the current constructive elements of the cadastral parcel. Yellow, blue, and green nodes correspond to three constructive elements in 3D cadastral space: surfaces, lines, and points, respectively. Throughout the symbolic processing part of the topological relation algebra calculation, only when the terminal node is non-zero or the GeoSpaceOP operator is applied to all relative dimensional elements in the hierarchical structure will it stop iteration of the topological relationship calculation. In the framework of topological relation calculation based on CGA, we can not only distinguish the inner, outer, and boundary topological relations, but we can also distinguish the external topological space according to whether or not there is linear correlation. For example, Figure 9g to Figure 9k and Figure 10g, Figure 10h, Figure 10i, Figure 10m, Figure 10o, Figure 10s, etc. are cases where the boundary line is located outside the parcel (both terminal nodes of the boundary line are equal to +1). Topological relationships at the cadastral parcel’s boundary can also be distinguished, such as partial overlap (Figure 9q and Figure 10n); encompassment in a boundary element (Figure 9s and Figure 10v) and adjacency to the boundary co-point or collinearity (Figure 9t, Figure 9u, Figure 10w, Figure 10x, Figure 10y, Figure 10z and Figure 10aa), etc.

The algebraic calculation results are organized according to the hierarchical structure of constructive topology of cadastral parcels. It can be seen from the schematic diagram of the topological relations between a boundary line and a cadastral parcel that the relation between algebraic calculation results and geometric topological relation is more intuitive. For example, if the terminal nodes are all 0, the entire boundary line can be directly determined, and it is located at the boundary of the parcel and coincident with one of the constructive boundary lines of the parcel (Figure 9u and Figure 10aa). When the end nodes are all −1, this means that the entire boundary line is completely inside the parcel (Figure 9s, Figure 10v, and Figure 10y).

4. Case Studies

Since many rights and benefits of land use are connected with the size and location of cadastral parcels, any errors contained in cadastral parcels can lead to expensive legal disputes [3]. As a result, one of the main tasks of cadastral management is to describe the scope of cadastral parcels accurately and clearly. All the topological consistency of cadastral parcels should be validated before being stored in the cadastral database, which is a key step to ensure the correctness of the cadastral database. According to the definition of cadastral parcels, topological consistency inside the cadastral parcels is a basic requirement for cadastral data validation. This means that each cadastral constructive element in the cadastral parcel should be a composing element belonging to a cadastral boundary element with a higher dimension. Hanging objects, as defined in this paper, are not allowed to exist in cadastral parcels.

A case study was designed with practical 3D cadastral data to verify the feasibility of calculation methods on the basis of CGA for topological consistency validation in 3D cadastral space. The original experimental data were selected from the cadastral database managed by the bureau of land and resources of Xuzhou. These real cadastral data were organized and represented in the form of CGA. The calculation methods for topological analysis in 3D cadastral space were implemented on the basis of GAViewer, a CGA operator package for geometric computation and visualization.

Different types of hanging lines, as shown in Figure 11, were detected as an example according to the topological calculation methods proposed in this paper. When the results of the outer product between both composing boundary points of the hanging line and the cadastral parcel were equal to −1 at the first level, the hanging line was located completely inside of the cadastral parcel (Figure 11a). The hanging line was located completely inside of the boundary face of the cadastral parcel when the results of the outer product between both composing boundary points of the hanging line and the cadastral parcel were equal to 0 at the first level and −1 at the second level (Figure 11b). Figure 11c shows the condition that the hanging line was partially contained in one of boundary lines of the cadastral parcel. Results of hanging object detection in 3D cadastral space indicated that the topological calculation methods proposed in this paper could be applied in 3D cadastral data topology validation. The advantages of CGA, including dimensionality independence and coordinate independence, will be helpful to realize more complex topology analysis with multidimensional cadastral elements.

5. Discussion

Boundary constructive topologies of cadastral parcels are important in 3D cadastral management. Accordingly, topological relations analysis among boundary points, boundary lines, boundary surfaces, and 2D parcels or 3D parcels needs to be realized to ensure the accuracy of cadastral data. A multidimensional topological calculation framework will be helpful to deal with the dimension-mixed topological analysis in 3D cadastral space. A 3D cadastral data model based on topological models constructed in Euclidean space cannot realize the unified calculation form for different dimensional objects. One of the possible reasons is that it lacks direct representation for geometric information of objects, and another reason might be the different geometric expression forms for different dimensional objects. Different from 3D cadastral data models constructed in Euclidean space, the 3D cadastral topological relation calculation framework presented in this paper deals with geometric problems by algebraic calculation, and the results are more intuitive. Not only can the topological relations between a boundary point (or a boundary line) and a cadastral parcel be calculated intuitively, but the multidimensional unification of the calculation method is realized.

The property comparison between our model and existing topological relation computation models is shown in

Table 2. Comparison among different topological relation computation models (the “+” means advantage, “−” means weakness, and more “+” means a greater advantage).

Method	Multidimensional–Unified	Adaptive	Simplicity of Algorithm Structure
Models in Euclidean space	−	−	++
Geometric algebra (GA) model	++	++	+
GOTR model	++	++	+
Our model	++	++	+++

. Compared with topological relation computation models in Euclidean space, our model is multidimensional–unified, which is important in the field of 3D cadastre. Since higher dimensional elements can be represented directly by lower dimensional elements using the outer product, topological models based on CGA are also more adaptive than models in Euclidean space. The GA model proposed by Yuan calculates topological relations by applying the meet operator to the whole multivector tree [30]. Apparently, this way increases the simplicity of the algorithm structure. Comparatively, our model does not need to carry out the outer product for the whole multivector tree. The geometry-oriented topological relation (GOTR) model proposed by Yu calculates topological relations based on both a Meet operator and a further boundary judgment [31]. The topological analysis methods proposed in this paper realize topological calculation only with the outer product, which is a single basic geometric operator in CGA. The goal of using a single geometric algebra operator to calculate complex topological relations in 3D space is realized, making full use of the extensibility of the outer product operation in different dimensional spaces. Meanwhile, when we iterate the outer product among different dimensions, it only needs to apply the outer product to the specific construction elements, and it does not need to carry on the operation to the entire multivector tree. This means that the property of simplicity of algorithm structure in our model is more concise than existing topological relations calculation methods based on CGA.

6. Conclusions

This paper puts forward a method for defining the multidimensional unified expression of cadastral constructive elements in conformal space. The multivector structure is used to realize the multidimensional fusion expression for constructive topology and geometric information of cadastral parcels in 3D space. A topological operation, GeoSpaceOP, is designed on the basis of the outer product. Taking advantage of the characteristic of the outer product’s geometrical meaning remaining consistent in different dimensional subspaces, the GeoSpaceOP operator is applied to all constructive hierarchical structures of cadastral parcels in order from higher dimension to lower dimension, according to specific conditions, adopting the recursive method. The algebraic calculation of topological relations between a boundary point and a cadastral parcel is abstracted, and the correlations between algebraic calculation results and geometric topological relations are constructed. The calculation method for topological relations between a boundary line and a cadastral parcel in 3D space is based on the calculation frame of topological relations between a boundary point and a cadastral parcel. A total of 13 types of topological relations between a boundary point and a cadastral parcel and 48 types of topological relations between a boundary line and a cadastral parcel are obtained.

In future research, the topological calculation among arbitrary dimensional elements should be considered as well as the construction of a more concise calculation process.