# Unified Spatial Intersection Algorithms Based on Conformal Geometric Algebra

Authors: Feng Zhang; Xiaomin Jiang; Xiaoyi Zhang; Yingzhi Wang; Zhenhong Du; Renyi Liu
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

Conformal Geometric Algebra has been introduced into geographic information science as a mathematical theory because of its advantages in terms of uniform multidimensional representation and computation. The traditional intersection computation between two geometric objects of different types is not unified. In this study, we propose algorithms based on Conformal Geometric Algebra to determine the spatial relationships between geographic objects in a unified manner. The unified representation and intersection computation can be realized for geometric objects of different dimensions. Different basic judgment rules are provided for different simple geometries. The algorithms are designed and implemented using MapReduce to improve the efficiency of the algorithms. From the results of several experiments we provide, the correctness and effectiveness of the algorithms can be verified.


---

## Body

## 1. Introduction

Geographic information is used widely to support digital replicas of the real world. For decades, spatial objects and their relationships have been represented and calculated based on Euclidean geometry. Due to the variable requirements for the expression and computation of multidimensional objects, researchers have aimed to improve or find new ways to satisfy needs, including the mathematical foundations employed [1]. Thus, Liu et al. proposed a general-field model to unify continuous field and discrete object conceptualizations [2]. Li and Qian presented a combined dynamic binary generalization tree method to represent two-dimensional geographic objects and for managing spatial data based on volunteered geographic information [3]. Yang et al. proposed a multiscale expression-oriented subdivisional encoding method to meet the demands of geographic object representation at different application levels, with different details, and arbitrary scales [4].The feature of multidimensional-unified representation makes Geometric Algebra (GA) become a hot research in geography. Yuan et al. proposed a multidimensional-unified data model based on Clifford algebra and they developed a prototype software system called Clifford algebra based on unified spatial-temporal analysis (CAUSTA) for investigating and modeling the distribution characteristics and dynamic processes of complex geographical phenomena [5]. GA has been employed widely as a new mathematical tool for multidimensional-unified representation and computation [6–15]. Luo et al. developed a new data structure to support unified organization and computation of geometrical primitives, which can reduce the complexity of data architectures and improve the processing ability of computer graphic software, but the extra two dimensions in Conformal Geometric Algebra could bring in low efficiency [16]. Yu et al. implemented multidimensional representation for 3D vector dat, and calculated intersection relations between Delaunay-Triangulated Irregular Networks (DTINs) with meet operator. They conducted parallel computation by GPU to improve computing efficiency [17]. In this paper, we use meet operator to judge intersection relation between objects of different types and MapReduce to implement parallel computing.Many scholars do some researches on the triangle-to-triangle intersection test. In [18], Möller proposed a signed distance method to exclude some nonintersection situations and detect intersection if two segments between one triangle and the plane to which the other triangle belongs overlap. In [19], based on signed distance and the intersection relationship between the two intersection line segments, Held gave an algorithm for different kinds of geometric objects. From the algebraic perspective, Tropp et al. made full use of the process values during the problem resolving and the linear relation in matrix operation to accelerate the problem to be resolved [20]. Guigue and Devillers employed the signed determinant and the intersection line relationship to determine the intersection relationships of the two triangles [21]. In [22], based on Conformal Geometric Algebra, Zong et al. discussed the intersection computation between two triangles and verified the algorithm by using Antarctic ice sheet simulation data. Luo et al. resolved the intersection relationship of two triangles based onMVTree structure, but some optimization methods may be used to increase some efficiency in the future [16]. In [23], Shen et al. implemented a fast detection algorithm for 3D convex polygons based on clamping-edge pair. Wei presented an algorithm which absorbed the idea from Tropp reducing the intersection test to the segment and triangle in the same planar and used the idea of classified discussions by comparing directions of coplanar vectors’ cross products [24]. Sugihara developed an intersection algorithm based on Delaunay triangulation [25]. Most of them show intersect in the intersection algorithm between two triangles and test the intersection relationship between two polygons by decomposing them into triangles.However, the above studies mainly aimed at the intersection relationship judgment between two triangles. The algorithms dealing with geometric objects of different types are rare and not unified.The computation of spatial relationships is the most basic operation in spatial analysis, including topological, order, and metric relationships. The intersection algorithm is a basic operator for topological computation. The parallel line segment intersection strategy based on uniform grids was developed for use in a shared architecture, which can effectively utilize computational resources in a parallel manner [26]. Wang proposed a parallel intersection algorithm for vector polygon overlay [27]. The parallel computation strategy can work well when coping with large volumes of data.In the present study, we attempt to handle geometric objects of different types in a unified fashion based on Conformal GA (CGA) and to expand the algorithm on the MapReduce platform to process massive amounts of spatiotemporal data.The main contributions of the present study are as follows.(1)
We propose unified spatial algorithms and specific rules for intersection relationships judgment for geometric objects of different types.(2)
We design several experiments to verify the correctness of the unified intersection algorithms. And the algorithms are implemented on the MapReduce platform to overcome the restriction of using hardware on standalone mode.


## 2. Methodology

### 2.1. CGA

GA is an algebraic language that solves geometric problems in algebraic form. The geometric product unifies the dimension, geometry, vector, and scalar operations [28–30].Suppose that we have two arbitrary multivectors,A,B; then, the geometric product between A and B is(1)AB=∑s=1nAsB=∑s=1nAsB,where A denotes a linear combination of its homogeneous grades parts, n denotes the dimension of A,As denotes multivector part of grade s. The product can be decomposed into basic geometric products of grade 1 vectors [31, 32].CGA is the most common GA space. Based on the traditional Euclidean space, two extra base vectors,eo and e∞, are employed to represent basic geometric objects. The hierarchical geometric structure corresponds to the hierarchical Grassmann structure for the outer product in CGA. The inner product in CGA can describe basic metric information such as the distance and angle. We construct a multidimensional-unified data model based onblade andmultivector and intersection algorithms using the basic operations in CGA.


### 2.2. Multidimensional-Unified Representation

Ablade is the outer product of a series of linearly independent vectors. Ablade with gradek can be represented byk-blade. When grade is 0, 1, 2, 3, 4, and 5, the correspondingblade is scalar, vector, bivector, trivector, quadvector, and pseudoscalar, respectively [29].Amultivector is the linear combination of geometric objects with different dimensions and it is the basic mathematical structure for multidimensional objects. Themultivector can be utilized to represent complex geometry objects and it contributes to making objects with different dimensions representation-unified.The grade extracting operation〈〉i is used to resolve the part with grade i in themultivector. For example, in the 5 dimensions conformal space, for example, for A=a0+a1e1+⋯+a12e12+⋯+a123e123+⋯+a1234e1230+⋯+a12345e1230∞, the resolution results are as follows:(2)A0=a0ScalarA1=a1e1+⋯VectorA2=a12e12+⋯BivectorA3=a123e123+⋯TrivectorA4=a1234e1234+⋯QuadvectorA5=a12345e1230∞Pseudoscalar.For instance, given two pointsP1(1,0,0) and P2(0,1,0), the representations in conformal space are P1=e1+(1/2)e∞+e0 and P2=e2+(1/2)e∞+e0. The line constructed by the two points is LP1P2=P1∧P2∧e∞. Using the outer product, the operation is LP1P2=e1∧e2∧e∞+e1∧e0∧e∞+e0∧e2∧e∞, which is part of A and corresponding to 〈A〉3 in the grade resolution. For other basic objects, for example, the point can be resolved using 〈A〉1, the point pair 〈A〉2, the line and circle 〈A〉3, and the plane and sphere 〈A〉4. Thus, themultivector is capable of representing geometry with different dimensions. In this study, a geographic object is represented by amultivector with boundary constraints. The data modeling process is illustrated in Figure 1.Figure 1
Multidimensional-unified representation data model process based on the CGA.We can represent an arbitrary geometric object in the following CGA format:(3)ObjectType,ObjectID,ObjectFormat,Attr1,Attr2,…,Timestampconstraint,whereObjectType represents the type of the object,ObjectID represents the unique identifier,ObjectFormat represents the multivector representation,Attr1,Attr2… represent attribute information for the object,Timestamp represents the time information, and constraint is the boundary constraint. When theObjectType is a point,ObjectID is the point ID. When theObjectType is a line segment, constraint denotes the ID of the endpoints of the line segment. When theObjectType is a polygon, constraint denotes the ID of the boundary lines of the polygon.


### 2.3. Intersection Algorithm

#### 2.3.1. Meet Operator

The meet operator can be utilized to determine the intersection relationship between two objects of different dimensions in a unified fashion. The objects that the meet operator can deal with directly are basic geometric objects with no boundaries.Given two blades,A andB, the meet operator satisfies(4)∀x:x∧A=0x∧B=0.The concrete computing formula is as follows:(5)M=A∩B=B·IAB·A=B∗·A,where IAB denotes thepseudoscalar forming the minimal subspace which containsA andB. B∗ is the duality operation ofB. In [16], Luo et al. employed meet operator to judge intersection relationships.Under certain circumstances, the objects are constrained with their boundaries. The specific intersection relationship judgment rules are depicted in Section2.3.2.


#### 2.3.2. Specific Judgment Rules

Cameron and Lasenby stated that CGA can provide benefits for understanding multivectors and improving algorithms for computer graphics and vision. They discuss intersection ordering for from/back-face to investigate possible advantages to show different spheres and triangular facets in a scene. Here, we try to construct a comprehensive inclusion relationship between basic geometric objects [33]. Different intersection algorithms are employed for different types of geometric objects. For the intersection judgment, the outer product, inner product, and geometric product are employed.First, the line segment is the basic construction unit for a polygon. The complex geometric objects are decomposed into several simple geometric objects to perform the intersection operation. The meet operation results between basic objects are as seen in Table1. Here, we define MGAO (Meaningless Geometric Algebra Object), which refers to the objects that are not meaningful in GIS. If the computation result is recorded as MGAO that means that the basic GA objects are not intersected.Table 1
The meet operation results between basic objects.
Re ⁡ s = P 1 ∩ P 2 IfRe⁡s = point, P1,P2 intersect IfRe⁡s = MGAO, P1,P2 do not intersect  Re ⁡ s = P ∩ L IfRe⁡s = point, P,L do not intersect IfRe⁡s = MGAO, P,L do not intersect  Re ⁡ s = P ∩ Φ IfRe⁡s = point, P,Φ intersect IfRe⁡s = MGAO, P,Φ do not intersect  Re ⁡ s = L 1 ∩ L 2 IfRe⁡s = point, L1,L2 intersect IfRe⁡s = line, L1,L2 intersect IfRe⁡s = MGAO, L1,L2 do not intersect  Re ⁡ s = L ∩ Φ IfRe⁡s = point, L,Φ intersect IfRe⁡s = line, L,Φ intersect IfRe⁡s = MGAO, L,Φ do not intersect  Re ⁡ s = Φ 1 ∩ Φ 2 IfRe⁡s = point, Φ1,Φ2 intersect IfRe⁡s = plane, Φ1,Φ2 intersect IfRe⁡s = MGAO, Φ1,Φ2 do not intersectCase 1 (the intersection relationship between two pointsP1 and P2).
Record meet operation resultRe⁡s between the two points P1 and P2. If Re⁡s is a point, P1 intersects with P2, and If Re⁡s is MGAO, P1 does not intersect with P2.Case 2 (the intersection relationship between pointP and line segment LAB).
Line segmentLAB is a line with a boundary constraint. Straight line LSL is the line going through line segment LAB. Record, meet operation result Re⁡s between point P and straight line LSL.IfRe⁡s is MGAO, P and LAB do not intersect. If Re⁡s is a point, then, for line LSL containing A and B, the outer product representation is LSL=A∧B∧e∞. We need to determine the intersection relationship between point P and line segment LAB. According to the inner product, outer product, and geometric product in GA, we can construct two representations, as follows:(6)t1=A∧P∧e∞LSLt2=P∧B∧e∞LSL.Ift1=0∥t2=0, then point P matches one of the endpoints of line segment LAB, which means that P intersects with LAB.Ift1<0∥t2<0, then point P is not within line segment LAB, which means that P does not intersect with LAB.Case 3 (the intersection relationship between pointP and polygon M).
Record the meet operator resultRe⁡s between point P and polygon M. If Re⁡s is MGAO, P and M do not intersect. If Re⁡s is a point, then we construct the representation: t=(P∧L)·Φ, where P is the point that needs to be assessed, L is the boundary of the polygon, Φ is the plane to which M belongs, Φ=C∧e∞, C is the circle that surrounds polygon M, and e∞ is infinity.
We obtain the boundary of polygonM sequentially and if equation t<0∥t=0 meets each boundary, then point P is within or on the boundary of polygon M (that is P intersects with M); otherwise, point P is outside polygon M (i.e., P does not intersect with M).Case 4 (the intersection relationship between two line segmentsLA1B1 and LA2B2).
For lineLSL1 containing A1 and B1, LSL1=A1∧B1∧e∞, and, for the line LSL2 containing A2 and B2, LSL2=A2∧B2∧e∞. By transferring the entities from Euclidean space into conformal space, the following equation can be obtained:(7)L=L1eo12+L2eo13+L3eo1∞+L4eo23+L5eo2∞+L6eo3∞+L7e123+L8e12∞+L9e13∞+L10e23∞.By using the meet operation, we have the following:(8)MeetLSL1LSL2=LSL1∩LSL2=LSL2·I·LSL1.This operation yields the multivector, MGAO, or a point object.Step  1. The meet operation is used to compute the intersection result between two lines. If the result is MGAO, then the two lines are parallel; otherwise, go to Step 2.Step  2. Assess the intersection relationship between the intersection point and the two line segments, according to the detailed rules described in Case 2.Step  3. If the intersection point is within or matches with one endpoint of the two line segments, then the two line segments intersect.Case 5 (the intersection relationship between line segmentL and polygon M).
Construct straight lineLSL going through the line segment and plane Φ covers the polygon. Record the meet operator result Re⁡s between LSL and Φ.
IfRe⁡s is MGAO, LSL and Φ do not intersect and the line segment L and the polygon M do not intersect either. If Re⁡s is a line, L and M intersect. If Re⁡s is a point, named Q, then, according to Case 2, we obtain the intersection relationship IR1 between point Q and line segment L. According to Case 3, intersection relationship IR2 between point Q and polygon M is achieved. If IR1 and IR2 meet the conditions simultaneously, L and M intersect; otherwise, L and M do not intersect.Case 6 (the intersection relationship between two polygonsM1 and M2).
We construct two planes using three points that are not collinear and infinity; that is,Φ1=A1∧B1∧C1∧e∞ and Φ2=A2∧B2∧C2∧e∞. Record the meet operator result Re⁡s between two planes Φ1 and Φ2.IfRe⁡s is a plane, it means that the two polygons are coplanar. The intersection relationship judgment is a coplanar problem. The detailed judgment rule is as follows.For the two polygons, the representations areΣ1=A1∧B1∧C1∧e∞A1,B1,C1,… and Σ2=A2∧B2∧C2∧e∞A2,B2,C2,…, respectively. The IDs in angle bracket are boundary constraints. First, we assess the intersection relationship between the vertices of one polygon and the other polygon (see Case 3). If the intersection relationship is not satisfied, we assess the intersection relationship between the boundary line segments of the two polygons (see Case 4). Thus, we can summarize the assessment steps as follows.Step 1. Assess the intersection relationship between the vertices of these two polygons. If there is one vertex within the other polygon, the two polygons intersect; otherwise, go to Step 2.Step 2. Decompose the polygon into a boundary line set.Step 3. According to Step 1, we have taken the situation where one object is inside the other one into consideration. Then, for each line segment in one polygon, we obtain its intersection relationship with each line segment in the other polygon. If there is an intersection relationship between the two line segments, then the two polygons intersect; otherwise, they do not intersect with each other.IfRe⁡s is a straight line, named LSL, we have to determine the intersection relationship between LSL and Φ1,Φ2, respectively.For each line segment in polygonM1, we obtain its intersection relationship with straight line LSL (see Case 5). Also, we obtain the intersection relationship between each line segment of polygon M2 and straight line LSL. If both of these two situations meet, the two polygons intersect; otherwise, they do not intersect with each other.The above assessments are specific judgment rules for testing intersection relationships. To cope with massive amounts of spatial data, we must implement the intersection algorithms in parallel. However, one computer always lacks sufficient computational resources for this purpose in terms of its CPU and memory, especially when the target data reach a specific volume. Thus, it is obviously difficult for a standard PC to run a massive data computation program and it is also time-consuming, along with being unsuitable in certain conditions. In many studies, parallel computing has been performed using massively parallel processors, symmetric multiprocessors, OpenMP, or clusters. The computational power can be enhanced and the time required can be decreased, but the hardware on one personal computer is still limited. Thus, we used the open source parallel implementation of MapReduce to achieve our aim.


## 2.1. CGA

GA is an algebraic language that solves geometric problems in algebraic form. The geometric product unifies the dimension, geometry, vector, and scalar operations [28–30].Suppose that we have two arbitrary multivectors,A,B; then, the geometric product between A and B is(1)AB=∑s=1nAsB=∑s=1nAsB,where A denotes a linear combination of its homogeneous grades parts, n denotes the dimension of A,As denotes multivector part of grade s. The product can be decomposed into basic geometric products of grade 1 vectors [31, 32].CGA is the most common GA space. Based on the traditional Euclidean space, two extra base vectors,eo and e∞, are employed to represent basic geometric objects. The hierarchical geometric structure corresponds to the hierarchical Grassmann structure for the outer product in CGA. The inner product in CGA can describe basic metric information such as the distance and angle. We construct a multidimensional-unified data model based onblade andmultivector and intersection algorithms using the basic operations in CGA.


## 2.2. Multidimensional-Unified Representation

Ablade is the outer product of a series of linearly independent vectors. Ablade with gradek can be represented byk-blade. When grade is 0, 1, 2, 3, 4, and 5, the correspondingblade is scalar, vector, bivector, trivector, quadvector, and pseudoscalar, respectively [29].Amultivector is the linear combination of geometric objects with different dimensions and it is the basic mathematical structure for multidimensional objects. Themultivector can be utilized to represent complex geometry objects and it contributes to making objects with different dimensions representation-unified.The grade extracting operation〈〉i is used to resolve the part with grade i in themultivector. For example, in the 5 dimensions conformal space, for example, for A=a0+a1e1+⋯+a12e12+⋯+a123e123+⋯+a1234e1230+⋯+a12345e1230∞, the resolution results are as follows:(2)A0=a0ScalarA1=a1e1+⋯VectorA2=a12e12+⋯BivectorA3=a123e123+⋯TrivectorA4=a1234e1234+⋯QuadvectorA5=a12345e1230∞Pseudoscalar.For instance, given two pointsP1(1,0,0) and P2(0,1,0), the representations in conformal space are P1=e1+(1/2)e∞+e0 and P2=e2+(1/2)e∞+e0. The line constructed by the two points is LP1P2=P1∧P2∧e∞. Using the outer product, the operation is LP1P2=e1∧e2∧e∞+e1∧e0∧e∞+e0∧e2∧e∞, which is part of A and corresponding to 〈A〉3 in the grade resolution. For other basic objects, for example, the point can be resolved using 〈A〉1, the point pair 〈A〉2, the line and circle 〈A〉3, and the plane and sphere 〈A〉4. Thus, themultivector is capable of representing geometry with different dimensions. In this study, a geographic object is represented by amultivector with boundary constraints. The data modeling process is illustrated in Figure 1.Figure 1
Multidimensional-unified representation data model process based on the CGA.We can represent an arbitrary geometric object in the following CGA format:(3)ObjectType,ObjectID,ObjectFormat,Attr1,Attr2,…,Timestampconstraint,whereObjectType represents the type of the object,ObjectID represents the unique identifier,ObjectFormat represents the multivector representation,Attr1,Attr2… represent attribute information for the object,Timestamp represents the time information, and constraint is the boundary constraint. When theObjectType is a point,ObjectID is the point ID. When theObjectType is a line segment, constraint denotes the ID of the endpoints of the line segment. When theObjectType is a polygon, constraint denotes the ID of the boundary lines of the polygon.


## 2.3. Intersection Algorithm

### 2.3.1. Meet Operator

The meet operator can be utilized to determine the intersection relationship between two objects of different dimensions in a unified fashion. The objects that the meet operator can deal with directly are basic geometric objects with no boundaries.Given two blades,A andB, the meet operator satisfies(4)∀x:x∧A=0x∧B=0.The concrete computing formula is as follows:(5)M=A∩B=B·IAB·A=B∗·A,where IAB denotes thepseudoscalar forming the minimal subspace which containsA andB. B∗ is the duality operation ofB. In [16], Luo et al. employed meet operator to judge intersection relationships.Under certain circumstances, the objects are constrained with their boundaries. The specific intersection relationship judgment rules are depicted in Section2.3.2.


### 2.3.2. Specific Judgment Rules

Cameron and Lasenby stated that CGA can provide benefits for understanding multivectors and improving algorithms for computer graphics and vision. They discuss intersection ordering for from/back-face to investigate possible advantages to show different spheres and triangular facets in a scene. Here, we try to construct a comprehensive inclusion relationship between basic geometric objects [33]. Different intersection algorithms are employed for different types of geometric objects. For the intersection judgment, the outer product, inner product, and geometric product are employed.First, the line segment is the basic construction unit for a polygon. The complex geometric objects are decomposed into several simple geometric objects to perform the intersection operation. The meet operation results between basic objects are as seen in Table1. Here, we define MGAO (Meaningless Geometric Algebra Object), which refers to the objects that are not meaningful in GIS. If the computation result is recorded as MGAO that means that the basic GA objects are not intersected.Table 1
The meet operation results between basic objects.
Re ⁡ s = P 1 ∩ P 2 IfRe⁡s = point, P1,P2 intersect IfRe⁡s = MGAO, P1,P2 do not intersect  Re ⁡ s = P ∩ L IfRe⁡s = point, P,L do not intersect IfRe⁡s = MGAO, P,L do not intersect  Re ⁡ s = P ∩ Φ IfRe⁡s = point, P,Φ intersect IfRe⁡s = MGAO, P,Φ do not intersect  Re ⁡ s = L 1 ∩ L 2 IfRe⁡s = point, L1,L2 intersect IfRe⁡s = line, L1,L2 intersect IfRe⁡s = MGAO, L1,L2 do not intersect  Re ⁡ s = L ∩ Φ IfRe⁡s = point, L,Φ intersect IfRe⁡s = line, L,Φ intersect IfRe⁡s = MGAO, L,Φ do not intersect  Re ⁡ s = Φ 1 ∩ Φ 2 IfRe⁡s = point, Φ1,Φ2 intersect IfRe⁡s = plane, Φ1,Φ2 intersect IfRe⁡s = MGAO, Φ1,Φ2 do not intersectCase 1 (the intersection relationship between two pointsP1 and P2).
Record meet operation resultRe⁡s between the two points P1 and P2. If Re⁡s is a point, P1 intersects with P2, and If Re⁡s is MGAO, P1 does not intersect with P2.Case 2 (the intersection relationship between pointP and line segment LAB).
Line segmentLAB is a line with a boundary constraint. Straight line LSL is the line going through line segment LAB. Record, meet operation result Re⁡s between point P and straight line LSL.IfRe⁡s is MGAO, P and LAB do not intersect. If Re⁡s is a point, then, for line LSL containing A and B, the outer product representation is LSL=A∧B∧e∞. We need to determine the intersection relationship between point P and line segment LAB. According to the inner product, outer product, and geometric product in GA, we can construct two representations, as follows:(6)t1=A∧P∧e∞LSLt2=P∧B∧e∞LSL.Ift1=0∥t2=0, then point P matches one of the endpoints of line segment LAB, which means that P intersects with LAB.Ift1<0∥t2<0, then point P is not within line segment LAB, which means that P does not intersect with LAB.Case 3 (the intersection relationship between pointP and polygon M).
Record the meet operator resultRe⁡s between point P and polygon M. If Re⁡s is MGAO, P and M do not intersect. If Re⁡s is a point, then we construct the representation: t=(P∧L)·Φ, where P is the point that needs to be assessed, L is the boundary of the polygon, Φ is the plane to which M belongs, Φ=C∧e∞, C is the circle that surrounds polygon M, and e∞ is infinity.
We obtain the boundary of polygonM sequentially and if equation t<0∥t=0 meets each boundary, then point P is within or on the boundary of polygon M (that is P intersects with M); otherwise, point P is outside polygon M (i.e., P does not intersect with M).Case 4 (the intersection relationship between two line segmentsLA1B1 and LA2B2).
For lineLSL1 containing A1 and B1, LSL1=A1∧B1∧e∞, and, for the line LSL2 containing A2 and B2, LSL2=A2∧B2∧e∞. By transferring the entities from Euclidean space into conformal space, the following equation can be obtained:(7)L=L1eo12+L2eo13+L3eo1∞+L4eo23+L5eo2∞+L6eo3∞+L7e123+L8e12∞+L9e13∞+L10e23∞.By using the meet operation, we have the following:(8)MeetLSL1LSL2=LSL1∩LSL2=LSL2·I·LSL1.This operation yields the multivector, MGAO, or a point object.Step  1. The meet operation is used to compute the intersection result between two lines. If the result is MGAO, then the two lines are parallel; otherwise, go to Step 2.Step  2. Assess the intersection relationship between the intersection point and the two line segments, according to the detailed rules described in Case 2.Step  3. If the intersection point is within or matches with one endpoint of the two line segments, then the two line segments intersect.Case 5 (the intersection relationship between line segmentL and polygon M).
Construct straight lineLSL going through the line segment and plane Φ covers the polygon. Record the meet operator result Re⁡s between LSL and Φ.
IfRe⁡s is MGAO, LSL and Φ do not intersect and the line segment L and the polygon M do not intersect either. If Re⁡s is a line, L and M intersect. If Re⁡s is a point, named Q, then, according to Case 2, we obtain the intersection relationship IR1 between point Q and line segment L. According to Case 3, intersection relationship IR2 between point Q and polygon M is achieved. If IR1 and IR2 meet the conditions simultaneously, L and M intersect; otherwise, L and M do not intersect.Case 6 (the intersection relationship between two polygonsM1 and M2).
We construct two planes using three points that are not collinear and infinity; that is,Φ1=A1∧B1∧C1∧e∞ and Φ2=A2∧B2∧C2∧e∞. Record the meet operator result Re⁡s between two planes Φ1 and Φ2.IfRe⁡s is a plane, it means that the two polygons are coplanar. The intersection relationship judgment is a coplanar problem. The detailed judgment rule is as follows.For the two polygons, the representations areΣ1=A1∧B1∧C1∧e∞A1,B1,C1,… and Σ2=A2∧B2∧C2∧e∞A2,B2,C2,…, respectively. The IDs in angle bracket are boundary constraints. First, we assess the intersection relationship between the vertices of one polygon and the other polygon (see Case 3). If the intersection relationship is not satisfied, we assess the intersection relationship between the boundary line segments of the two polygons (see Case 4). Thus, we can summarize the assessment steps as follows.Step 1. Assess the intersection relationship between the vertices of these two polygons. If there is one vertex within the other polygon, the two polygons intersect; otherwise, go to Step 2.Step 2. Decompose the polygon into a boundary line set.Step 3. According to Step 1, we have taken the situation where one object is inside the other one into consideration. Then, for each line segment in one polygon, we obtain its intersection relationship with each line segment in the other polygon. If there is an intersection relationship between the two line segments, then the two polygons intersect; otherwise, they do not intersect with each other.IfRe⁡s is a straight line, named LSL, we have to determine the intersection relationship between LSL and Φ1,Φ2, respectively.For each line segment in polygonM1, we obtain its intersection relationship with straight line LSL (see Case 5). Also, we obtain the intersection relationship between each line segment of polygon M2 and straight line LSL. If both of these two situations meet, the two polygons intersect; otherwise, they do not intersect with each other.The above assessments are specific judgment rules for testing intersection relationships. To cope with massive amounts of spatial data, we must implement the intersection algorithms in parallel. However, one computer always lacks sufficient computational resources for this purpose in terms of its CPU and memory, especially when the target data reach a specific volume. Thus, it is obviously difficult for a standard PC to run a massive data computation program and it is also time-consuming, along with being unsuitable in certain conditions. In many studies, parallel computing has been performed using massively parallel processors, symmetric multiprocessors, OpenMP, or clusters. The computational power can be enhanced and the time required can be decreased, but the hardware on one personal computer is still limited. Thus, we used the open source parallel implementation of MapReduce to achieve our aim.


## 2.3.1. Meet Operator

The meet operator can be utilized to determine the intersection relationship between two objects of different dimensions in a unified fashion. The objects that the meet operator can deal with directly are basic geometric objects with no boundaries.Given two blades,A andB, the meet operator satisfies(4)∀x:x∧A=0x∧B=0.The concrete computing formula is as follows:(5)M=A∩B=B·IAB·A=B∗·A,where IAB denotes thepseudoscalar forming the minimal subspace which containsA andB. B∗ is the duality operation ofB. In [16], Luo et al. employed meet operator to judge intersection relationships.Under certain circumstances, the objects are constrained with their boundaries. The specific intersection relationship judgment rules are depicted in Section2.3.2.


## 2.3.2. Specific Judgment Rules

Cameron and Lasenby stated that CGA can provide benefits for understanding multivectors and improving algorithms for computer graphics and vision. They discuss intersection ordering for from/back-face to investigate possible advantages to show different spheres and triangular facets in a scene. Here, we try to construct a comprehensive inclusion relationship between basic geometric objects [33]. Different intersection algorithms are employed for different types of geometric objects. For the intersection judgment, the outer product, inner product, and geometric product are employed.First, the line segment is the basic construction unit for a polygon. The complex geometric objects are decomposed into several simple geometric objects to perform the intersection operation. The meet operation results between basic objects are as seen in Table1. Here, we define MGAO (Meaningless Geometric Algebra Object), which refers to the objects that are not meaningful in GIS. If the computation result is recorded as MGAO that means that the basic GA objects are not intersected.Table 1
The meet operation results between basic objects.
Re ⁡ s = P 1 ∩ P 2 IfRe⁡s = point, P1,P2 intersect IfRe⁡s = MGAO, P1,P2 do not intersect  Re ⁡ s = P ∩ L IfRe⁡s = point, P,L do not intersect IfRe⁡s = MGAO, P,L do not intersect  Re ⁡ s = P ∩ Φ IfRe⁡s = point, P,Φ intersect IfRe⁡s = MGAO, P,Φ do not intersect  Re ⁡ s = L 1 ∩ L 2 IfRe⁡s = point, L1,L2 intersect IfRe⁡s = line, L1,L2 intersect IfRe⁡s = MGAO, L1,L2 do not intersect  Re ⁡ s = L ∩ Φ IfRe⁡s = point, L,Φ intersect IfRe⁡s = line, L,Φ intersect IfRe⁡s = MGAO, L,Φ do not intersect  Re ⁡ s = Φ 1 ∩ Φ 2 IfRe⁡s = point, Φ1,Φ2 intersect IfRe⁡s = plane, Φ1,Φ2 intersect IfRe⁡s = MGAO, Φ1,Φ2 do not intersectCase 1 (the intersection relationship between two pointsP1 and P2).
Record meet operation resultRe⁡s between the two points P1 and P2. If Re⁡s is a point, P1 intersects with P2, and If Re⁡s is MGAO, P1 does not intersect with P2.Case 2 (the intersection relationship between pointP and line segment LAB).
Line segmentLAB is a line with a boundary constraint. Straight line LSL is the line going through line segment LAB. Record, meet operation result Re⁡s between point P and straight line LSL.IfRe⁡s is MGAO, P and LAB do not intersect. If Re⁡s is a point, then, for line LSL containing A and B, the outer product representation is LSL=A∧B∧e∞. We need to determine the intersection relationship between point P and line segment LAB. According to the inner product, outer product, and geometric product in GA, we can construct two representations, as follows:(6)t1=A∧P∧e∞LSLt2=P∧B∧e∞LSL.Ift1=0∥t2=0, then point P matches one of the endpoints of line segment LAB, which means that P intersects with LAB.Ift1<0∥t2<0, then point P is not within line segment LAB, which means that P does not intersect with LAB.Case 3 (the intersection relationship between pointP and polygon M).
Record the meet operator resultRe⁡s between point P and polygon M. If Re⁡s is MGAO, P and M do not intersect. If Re⁡s is a point, then we construct the representation: t=(P∧L)·Φ, where P is the point that needs to be assessed, L is the boundary of the polygon, Φ is the plane to which M belongs, Φ=C∧e∞, C is the circle that surrounds polygon M, and e∞ is infinity.
We obtain the boundary of polygonM sequentially and if equation t<0∥t=0 meets each boundary, then point P is within or on the boundary of polygon M (that is P intersects with M); otherwise, point P is outside polygon M (i.e., P does not intersect with M).Case 4 (the intersection relationship between two line segmentsLA1B1 and LA2B2).
For lineLSL1 containing A1 and B1, LSL1=A1∧B1∧e∞, and, for the line LSL2 containing A2 and B2, LSL2=A2∧B2∧e∞. By transferring the entities from Euclidean space into conformal space, the following equation can be obtained:(7)L=L1eo12+L2eo13+L3eo1∞+L4eo23+L5eo2∞+L6eo3∞+L7e123+L8e12∞+L9e13∞+L10e23∞.By using the meet operation, we have the following:(8)MeetLSL1LSL2=LSL1∩LSL2=LSL2·I·LSL1.This operation yields the multivector, MGAO, or a point object.Step  1. The meet operation is used to compute the intersection result between two lines. If the result is MGAO, then the two lines are parallel; otherwise, go to Step 2.Step  2. Assess the intersection relationship between the intersection point and the two line segments, according to the detailed rules described in Case 2.Step  3. If the intersection point is within or matches with one endpoint of the two line segments, then the two line segments intersect.Case 5 (the intersection relationship between line segmentL and polygon M).
Construct straight lineLSL going through the line segment and plane Φ covers the polygon. Record the meet operator result Re⁡s between LSL and Φ.
IfRe⁡s is MGAO, LSL and Φ do not intersect and the line segment L and the polygon M do not intersect either. If Re⁡s is a line, L and M intersect. If Re⁡s is a point, named Q, then, according to Case 2, we obtain the intersection relationship IR1 between point Q and line segment L. According to Case 3, intersection relationship IR2 between point Q and polygon M is achieved. If IR1 and IR2 meet the conditions simultaneously, L and M intersect; otherwise, L and M do not intersect.Case 6 (the intersection relationship between two polygonsM1 and M2).
We construct two planes using three points that are not collinear and infinity; that is,Φ1=A1∧B1∧C1∧e∞ and Φ2=A2∧B2∧C2∧e∞. Record the meet operator result Re⁡s between two planes Φ1 and Φ2.IfRe⁡s is a plane, it means that the two polygons are coplanar. The intersection relationship judgment is a coplanar problem. The detailed judgment rule is as follows.For the two polygons, the representations areΣ1=A1∧B1∧C1∧e∞A1,B1,C1,… and Σ2=A2∧B2∧C2∧e∞A2,B2,C2,…, respectively. The IDs in angle bracket are boundary constraints. First, we assess the intersection relationship between the vertices of one polygon and the other polygon (see Case 3). If the intersection relationship is not satisfied, we assess the intersection relationship between the boundary line segments of the two polygons (see Case 4). Thus, we can summarize the assessment steps as follows.Step 1. Assess the intersection relationship between the vertices of these two polygons. If there is one vertex within the other polygon, the two polygons intersect; otherwise, go to Step 2.Step 2. Decompose the polygon into a boundary line set.Step 3. According to Step 1, we have taken the situation where one object is inside the other one into consideration. Then, for each line segment in one polygon, we obtain its intersection relationship with each line segment in the other polygon. If there is an intersection relationship between the two line segments, then the two polygons intersect; otherwise, they do not intersect with each other.IfRe⁡s is a straight line, named LSL, we have to determine the intersection relationship between LSL and Φ1,Φ2, respectively.For each line segment in polygonM1, we obtain its intersection relationship with straight line LSL (see Case 5). Also, we obtain the intersection relationship between each line segment of polygon M2 and straight line LSL. If both of these two situations meet, the two polygons intersect; otherwise, they do not intersect with each other.The above assessments are specific judgment rules for testing intersection relationships. To cope with massive amounts of spatial data, we must implement the intersection algorithms in parallel. However, one computer always lacks sufficient computational resources for this purpose in terms of its CPU and memory, especially when the target data reach a specific volume. Thus, it is obviously difficult for a standard PC to run a massive data computation program and it is also time-consuming, along with being unsuitable in certain conditions. In many studies, parallel computing has been performed using massively parallel processors, symmetric multiprocessors, OpenMP, or clusters. The computational power can be enhanced and the time required can be decreased, but the hardware on one personal computer is still limited. Thus, we used the open source parallel implementation of MapReduce to achieve our aim.


## 3. Case Study

The intersection algorithms are implemented on open source codes GA sandbox 1.0.7. The basic operations, such as inner product, outer product, and geometric product, and the basic operators, like reverse, reflection, meet, join, and other operators, are implemented. So, it is convenient for us to accomplish our work.The data we used in our experiments are land use data, which are common vector data, such as shp, mdb, and gdb. We take land use data to test parallel intersection algorithms, the numbers of the 5 features sets are as follows: 22183, 174881, 695343, 1386987, and 5547948. In addition, the data we referred to in parallel experiments are coplanar.


### 3.1. The Correctness Verified Experiments

Point, polyline, and polygon are three basic types of geometries with which we often deal in spatial analysis. We are often confronted with the intersection computing among them. As described in Section2.3, we can implement the intersection computing in a unified manner. In Figure 2, intersection relationships between geometries of different types that can be distinguished are depicted.Figure 2
Intersection relationships between geometries of different types.In Figure2, using intersection algorithms, we can judge whether two points intersect. For one point and one line segment, we recognize the intersection relation meets when the point locates the edge or interior of the line segment. For one point and one polygon, as long as the point is situated in the edge or interior of the polygon, they intersect. For two line segments, we judge the location of intersecting point; if the intersecting point lies in the edge or interior of both line segments, they intersect. For one line segment and one polygon, we have to judge whether the intersecting point lies in the edge or interior of the line segment and, one special situation, that is, whether one edge of the line segment is inside the polygon. For two polygons, the 7 intersection situations can be distinguished according to the intersection algorithms.To verify the correctness of the algorithms, we design a series of experiments. In Figure3, the unified intersection algorithms are carried out. The features of different types intersecting with the region in red color are selected. Experiments show that the unified algorithms are correct.Figure 3
Results resolved by unified spatial intersection algorithms.Also, we conduct the unified intersection algorithms using massive data; the intersection results of different types are shown, respectively, in Figure4.Figure 4
Results conducted by unified algorithms using massive data.Through several experiments, the unified algorithms proposed by us prove to be correct with regard to the intersection results. However, the time consumption is not so satisfactory. To improve the efficiency and widen the applications of the algorithms, we need to make further research.


### 3.2. Parallel Computing Using the Unified Intersection Algorithms in MapReduce

The introduction of two extra dimensions in the unified intersection algorithms brings heavy computation work and results in low efficiency. Furthermore, due to the explosive growth in the volume of geospatial data, many researchers have described the processing of massive data volumes using MapReduce. Zhang et al. implemented parallel spatial querying with a geographical spatial semantic network [34]. Aridhi et al. applied parallel computing to shortest path computing in a large-scale network [35]. The multidimensional-unified representation and computation facilitate parallel computing. Here, we use MapReduce [36] as the programming model to implement parallel computing as in Figure 5.Figure 5
Overall parallel computation process.Hadoop Distributed File System is used to store data in GA structure; we design methods to resolve data into GA structure using open source GDAL/OGR. The attributes and geometry information can be obtained in the method. The intersection algorithms (see Figure5, namedResolveIntersectRelation) are implemented based on GA sandbox (C++), geometric product, and basic operators. We use JNI (Java Native Interface, which can be used to call C++ algorithm in Java environment) to call intersection algorithms in MapReduce. The desired computation results are obtained according to different experiment requirements. For example, we can obtain all objects that intersect with specified objects and sum up the area of the intersecting objects according to some attributes and so on.We are often confronted with the intersection computing among them. The demand of obtaining the objects that intersect with the specified spatial extent in land use data is in existence. The traditional method to meet the analogous demands is not unified. In our experiments, we implement the intersection algorithms with the unified algorithms and the specific judgment rules.In the experiments, we use four computers with the Debian operation system and Hadoop 2.6.0, in which one computer is the namenode and the other three are datanodes. For each computer, the CPU is an Intel® Core™ i-7 4790 CPU@3.60 GHz; there are also 7883 MB of RAM and the hard disk’s capacity is 1.0 TB.Based on the vector data model described above, we organize the geographic objects in a specific CGA format as shown in Algorithm1.Algorithm 1:Data organization of objects.
P o l y g o n [ P o l y g o n , P o l y g o n I D , P o l y g o n O b j e c t F o r m a t , A t t r 1 , A t t r 2 , … , T i m e S t a m p ] P o l y g o n _  c o n s t r a i n t [ M B C , m _ c [ 0 ] , m _ c [ 1 ] , m _ c [ 2 ] , m _ c [ 3 ] , m _ c [ 4 ] , m _ c [ 5 ] , m _ c [ 6 ] , m _ c [ 7 ] , m _ c [ 8 ] , m _ c [ 9 ] ] [ P o l y l i n e , P o l y l i n e I D , P o l y l i n e O b j e c t F o r m a t , A t t r 1 , A t t r 2 , … , T i m e S t a m p ] P o l y l i n e _  c o n s t r a i n t … [ P o i n t , P o i n t I D , P o i n t O b j e c t F o r m a t , A t t r 1 , A t t r 2 , … , T i m e S t a m p ] P o i n t _  c o n s t r a i n t … / P o l y g o n P o l y l i n e [ P o l y l i n e , P o l y l i n e I D , P o l y l i n e O b j e c t F o r m a t , A t t r 1 , A t t r 2 , … , T i m e S t a m p ] P o l y l i n e _  c o n s t r a i n t [ P o i n t , P o i n t I D , P o i n t O b j e c t F o r m a t , A t t r 1 , A t t r 2 , … , T i m e S t a m p ] P o i n t _  c o n s t r a i n t … / P o l y l i n e P o i n t [ P o i n t , P o i n t I D , P o i n t O b j e c t F o r m a t , A t t r 1 , A t t r 2 , … , T i m e S t a m p ] P o i n t _  c o n s t r a i n t … / P o i n tFinally, the intersection relationships are computed for the four types of different experiment data in the Hadoop platform and standalone mode, respectively. Each experiment has been done three times to reduce some accident errors. The data in parallel experiments are land use polygons which contain necessary attributes and geometrical information, and the exact amounts are shown in Tables2 and 3. In the MapReduce frameworks, the computational results obtained are shown in Table 2.Table 2
Time consumption in MapReduce framework.
Time Number 22183 174881 695343 1386987 5547948 Time 1 12 s 11 s 1 min 23 s 4 min 34 s 23 min 27 s Time 2 12 s 11 s 1 min 23 s 4 min 35 s 23 min 28 s Time 3 12 s 11 s 1 min 22 s 4 min 33 s 23 min 29 sTable 3
Time consumption in standalone mode.
Time Number 22183 174881 695343 1386987 5547948 Time 1 6 s 9 s 3 min 58 s 16 min 57 s No response Time 2 5 s 9 s 4 min 16 s 15 min 57 s No response Time 3 5 s 8 s 4 min 23 s 15 min 21 s No responseThe time consumption results in standalone mode are shown in Table3. From Table 3, we know that when the number of computed objects exceeds a certain amount, the computing becomes unavailable under specific hardware conditions.Experiments show that unified intersection algorithms based on CGA can work. The results indicate that the algorithms we present are valid compared to the traditional method. Furthermore, parallel intersection computing using MapReduce is efficient. There are no major advantages in terms of efficiency for using MapReduce or not. However, the latter one can address the limitations of the standalone mode in processing massive volumes of data.


## 3.1. The Correctness Verified Experiments

Point, polyline, and polygon are three basic types of geometries with which we often deal in spatial analysis. We are often confronted with the intersection computing among them. As described in Section2.3, we can implement the intersection computing in a unified manner. In Figure 2, intersection relationships between geometries of different types that can be distinguished are depicted.Figure 2
Intersection relationships between geometries of different types.In Figure2, using intersection algorithms, we can judge whether two points intersect. For one point and one line segment, we recognize the intersection relation meets when the point locates the edge or interior of the line segment. For one point and one polygon, as long as the point is situated in the edge or interior of the polygon, they intersect. For two line segments, we judge the location of intersecting point; if the intersecting point lies in the edge or interior of both line segments, they intersect. For one line segment and one polygon, we have to judge whether the intersecting point lies in the edge or interior of the line segment and, one special situation, that is, whether one edge of the line segment is inside the polygon. For two polygons, the 7 intersection situations can be distinguished according to the intersection algorithms.To verify the correctness of the algorithms, we design a series of experiments. In Figure3, the unified intersection algorithms are carried out. The features of different types intersecting with the region in red color are selected. Experiments show that the unified algorithms are correct.Figure 3
Results resolved by unified spatial intersection algorithms.Also, we conduct the unified intersection algorithms using massive data; the intersection results of different types are shown, respectively, in Figure4.Figure 4
Results conducted by unified algorithms using massive data.Through several experiments, the unified algorithms proposed by us prove to be correct with regard to the intersection results. However, the time consumption is not so satisfactory. To improve the efficiency and widen the applications of the algorithms, we need to make further research.


## 3.2. Parallel Computing Using the Unified Intersection Algorithms in MapReduce

The introduction of two extra dimensions in the unified intersection algorithms brings heavy computation work and results in low efficiency. Furthermore, due to the explosive growth in the volume of geospatial data, many researchers have described the processing of massive data volumes using MapReduce. Zhang et al. implemented parallel spatial querying with a geographical spatial semantic network [34]. Aridhi et al. applied parallel computing to shortest path computing in a large-scale network [35]. The multidimensional-unified representation and computation facilitate parallel computing. Here, we use MapReduce [36] as the programming model to implement parallel computing as in Figure 5.Figure 5
Overall parallel computation process.Hadoop Distributed File System is used to store data in GA structure; we design methods to resolve data into GA structure using open source GDAL/OGR. The attributes and geometry information can be obtained in the method. The intersection algorithms (see Figure5, namedResolveIntersectRelation) are implemented based on GA sandbox (C++), geometric product, and basic operators. We use JNI (Java Native Interface, which can be used to call C++ algorithm in Java environment) to call intersection algorithms in MapReduce. The desired computation results are obtained according to different experiment requirements. For example, we can obtain all objects that intersect with specified objects and sum up the area of the intersecting objects according to some attributes and so on.We are often confronted with the intersection computing among them. The demand of obtaining the objects that intersect with the specified spatial extent in land use data is in existence. The traditional method to meet the analogous demands is not unified. In our experiments, we implement the intersection algorithms with the unified algorithms and the specific judgment rules.In the experiments, we use four computers with the Debian operation system and Hadoop 2.6.0, in which one computer is the namenode and the other three are datanodes. For each computer, the CPU is an Intel® Core™ i-7 4790 CPU@3.60 GHz; there are also 7883 MB of RAM and the hard disk’s capacity is 1.0 TB.Based on the vector data model described above, we organize the geographic objects in a specific CGA format as shown in Algorithm1.Algorithm 1:Data organization of objects.
P o l y g o n [ P o l y g o n , P o l y g o n I D , P o l y g o n O b j e c t F o r m a t , A t t r 1 , A t t r 2 , … , T i m e S t a m p ] P o l y g o n _  c o n s t r a i n t [ M B C , m _ c [ 0 ] , m _ c [ 1 ] , m _ c [ 2 ] , m _ c [ 3 ] , m _ c [ 4 ] , m _ c [ 5 ] , m _ c [ 6 ] , m _ c [ 7 ] , m _ c [ 8 ] , m _ c [ 9 ] ] [ P o l y l i n e , P o l y l i n e I D , P o l y l i n e O b j e c t F o r m a t , A t t r 1 , A t t r 2 , … , T i m e S t a m p ] P o l y l i n e _  c o n s t r a i n t … [ P o i n t , P o i n t I D , P o i n t O b j e c t F o r m a t , A t t r 1 , A t t r 2 , … , T i m e S t a m p ] P o i n t _  c o n s t r a i n t … / P o l y g o n P o l y l i n e [ P o l y l i n e , P o l y l i n e I D , P o l y l i n e O b j e c t F o r m a t , A t t r 1 , A t t r 2 , … , T i m e S t a m p ] P o l y l i n e _  c o n s t r a i n t [ P o i n t , P o i n t I D , P o i n t O b j e c t F o r m a t , A t t r 1 , A t t r 2 , … , T i m e S t a m p ] P o i n t _  c o n s t r a i n t … / P o l y l i n e P o i n t [ P o i n t , P o i n t I D , P o i n t O b j e c t F o r m a t , A t t r 1 , A t t r 2 , … , T i m e S t a m p ] P o i n t _  c o n s t r a i n t … / P o i n tFinally, the intersection relationships are computed for the four types of different experiment data in the Hadoop platform and standalone mode, respectively. Each experiment has been done three times to reduce some accident errors. The data in parallel experiments are land use polygons which contain necessary attributes and geometrical information, and the exact amounts are shown in Tables2 and 3. In the MapReduce frameworks, the computational results obtained are shown in Table 2.Table 2
Time consumption in MapReduce framework.
Time Number 22183 174881 695343 1386987 5547948 Time 1 12 s 11 s 1 min 23 s 4 min 34 s 23 min 27 s Time 2 12 s 11 s 1 min 23 s 4 min 35 s 23 min 28 s Time 3 12 s 11 s 1 min 22 s 4 min 33 s 23 min 29 sTable 3
Time consumption in standalone mode.
Time Number 22183 174881 695343 1386987 5547948 Time 1 6 s 9 s 3 min 58 s 16 min 57 s No response Time 2 5 s 9 s 4 min 16 s 15 min 57 s No response Time 3 5 s 8 s 4 min 23 s 15 min 21 s No responseThe time consumption results in standalone mode are shown in Table3. From Table 3, we know that when the number of computed objects exceeds a certain amount, the computing becomes unavailable under specific hardware conditions.Experiments show that unified intersection algorithms based on CGA can work. The results indicate that the algorithms we present are valid compared to the traditional method. Furthermore, parallel intersection computing using MapReduce is efficient. There are no major advantages in terms of efficiency for using MapReduce or not. However, the latter one can address the limitations of the standalone mode in processing massive volumes of data.


## 4. Conclusions

CGA is a promising mathematical theory for representing geographic objects, especially complex and multidimensional geographic objects. This data representation model can be readily extended from low to high dimensions using geometric product. Unified intersection algorithms and specific rules are presented to determine intersection relationships between two geometric objects of different types. The unified representations and intersection algorithms lead to heavy computation; the parallel computation becomes sensible. The resolution of intersection relationships is important for determining spatial relationships. In this study, we investigate the use of an intersection algorithm based on the geometric product. We propose the use of the minimum bounding circle to preprocess the intersection relationship between two objects. This process can improve the efficiency of retrieval and computation. We employ MapReduce frameworks to construct the computing platform for massive data. Experiments show that unified spatial intersection algorithms work well and make up for the shortcomings caused by extra computation of two more dimensions. We can easily identify the objects of different types which meet spatial intersection with specified geometrical objects from massive data. In many domains, for land resource as an example, the intersection computation is needed; we need to compute the objects from land use data intersecting with other land data to make spatial and statistical analysis. In the future, we will extend our intersection algorithm to other spatial relationship algorithms and different domains. The parallel computation strategy is commonly used for massive data, from algorithm to data unit. We partition the data into parallel unit to accelerate our computation. Gaalop [29] is a more simple and efficient GA computation engine for parallel computing, and we look forward to using it in further research.



---

*Source: 7412373-2016-11-16.xml*