# Representation and Reasoning of Three-Dimensional Spatial Relationships Based on R5DOS-Intersection Model Representation and Reasoning Based on R5DOS Model

Authors: Jian Li; Weijian Zhang; Yating Hu; Zhun Wang
Journal: Complexity
 (2020)

---

## Abstract

This paper aims to disclose the compound topological and directional relationships of three simple regions in the three-dimensional (3D) space. For this purpose, the directional model and the 8-intersection model were coupled into an R5DOS-intersection model and used to represent three simple regions in the 3D space. The matrices represented by the model were found to be complete and mutually exclusive. Then, a self-designed algorithm was adopted to solve the model, yielding 11,038 achievable topological and directional relationships. Compared with the minimum bounding rectangle (MBR) model, the proposed model boasts strong expressive power. Finally, our model was applied to derive the topological and directional relationships between simple regions A and C from the known relationships between simple regions A and B and those between B and C. Based on the results, a compound relationship reasoning table was established for A and C. The research results shed new light on the representation and reasoning of 3D spatial relationships.


---

## Body

## 1. Introduction

The reasoning of spatial relationship, a.k.a. spatial reasoning, can be implemented quantitatively or qualitatively. Qualitative spatial reasoning, aiming to represent and analyze spatial information, is an important tool in artificial intelligence (AI), machine vision, robot navigation [1, 2], and geographic information system [3].Over three decades, many theories and models have been developed for spatial reasoning. For instance, Randell et al. [4, 5] put forward the region connection calculus (RCC) theory. Egenhofer and Franzosa [6, 7] proposed the theory of 4-intersection model and 9-intersection model. Li [8] derived a dynamic reasoning method for azimuth relationship.In recent years, spatial reasoning has evolved rapidly, thanks to the emerging AI applications in image processing [9, 10], computer vision [11, 12], and model prediction [13]. However, most studies on spatial reasoning focus on the spatial relationships on two-dimensional (2D) planes rather than those in three-dimensional (3D) spaces. The 3D space contains too many information elements to be handled by ordinary reasoning methods.At present, the relationships between objects in the 3D space are mostly solved by compound reasoning. The common approaches of compound reasoning include the compound reasoning of directional and topological relationships [14, 15] and the compound reasoning of directional and distance relationships [16]. Liu et al. [17] designed a 3D improved composite spatial relationship model (3D-ICSRM) in a large-scale environment and proposed a reasoning algorithm to solve that model. The accuracy of the 3D-ICSRM is very limited, and it considers the relationship between qualitative distance and direction. In 2016, Hou et al. [18] extended the convex tractable subalgebra into 3D space and used the BCD algorithm to calculate it. In 2019, Wang et al. [19] extended the oriented point relation algebra (OPRAm) model to 3D and proposed oriented point relation algebra in three-dimensional (OPRA3Dm) algorithm, which has certain practical significance. These two papers consider the direction relationship. In recent years, the literature mainly studies the relationship between the direction and qualitative distance, while there is less research on the direction and topological relationship. This article will focus on the direction and topological relationship to fill the gaps in this field.This paper aims to disclose the compound topological and directional relationships of three simple regions in the 3D space. Firstly, the RCC-5 model was combined with a strong directional relationship model for two simple regions, based on the extended 4-intersection theory and spatial orientation relationship in RCC5. The combined model was used to identify the compound topological and azimuth relationships between two simple regions, and solved by a self-designed algorithm. Through programming, a total of 65 topological and directional relationships were obtained in the 3D space.On this basis, the extended 4-intersection matrix was replaced with an 8-intersection matrix to represent the 3D spatial topological and directional relationships between three simple regions. Then, it was found that the topological and directional relationships between the R5DOS-intersection model of two regions and three regions are complete and mutually exclusive. Further programming reveals a total of 11,038 topological and azimuth relationships between three simple regions in the 3D space and derives a simple topological and directional relationshipR (A, C) from two sets of two simple regions R (A, B) and R (B, C).


## 2. Materials and Methods

### 2.1. RCC Theory

In 1992, Randell et al. [4, 5] proposed the RCC theory and established the RCC-8 intersection model, which is a boundary-sensitive model. Based on the boundary-sensitive conditions, the RCC-5 intersection model can be derived (Figure 1).Figure 1
The relationships between RCC-8 and RCC-5 intersection models.In 1991 and 1995, Egenhofer et al. constructed an extended 4-intersection matrix, which covers two space objectsA and B, with A° being the interior of A:(1)Ao∩BoAo∩BcoAoo∩BoAoC∩Bco.The value of each position set is either empty or nonempty. Then, the five kinds of relationships in the RCC-5 intersection model can be represented as the matrix in Table1 and expressed as a set R5=0111,1111,1011,1001,1101.Table 1
Matrix representation of the RCC-5 relationships.
RCC5 relationshipsDR (A, B)PO (A, B)PP (A, B)EQ (A, B)PPI (A, B)Extended 4-intersection matrix representation01111111101110011101For three simple areasA, B, and C, R2−∂A∪∂B∪∂C can be partitioned into 8 parts (Figure 2).Figure 2
The spatial partition of three simple areas.The eight parts can be illustrated by an 8-intersection matrix:(2)Ao∩Bo∩CoAo∩Bo∩CcoAo∩Bco∩CoAo∩Bco∩CcoAco∩Bo∩CoAco∩Bo∩CcoAco∩Bco∩CoAco∩Bco∩Cco.The RCC theory fuels the research on spatial relationship models in the past three decades, giving birth to many new theories. Nonetheless, most of these theories target the 2D plane rather than the 3D space. Recently, there is a growing interest in the spatial relationship models of the 3D space, especially the compound reasoning of directional and topological relationships, and that of directional and distance relationships.


### 2.2. Orientation Model

Minimum bounding rectangle (MBR) is a commonly used model for directional relationship in space [18–20]. The MBR model, 8-direction model, and 16-direction model are shown in Figure 3 below. The MBR model is not consistent with human cognition of directions.Figure 3
(a) The MBR model, (b) 8-direction model, and (c) 16-direction model.
(a)(b)(c)In 2010, He and Bian [21] came up with a special 8-direction cone model (Figure 4), which divides the space into eight regions: NW, NE, EN, ES, SE, SW, WS, and WN. Among them, NW and NE belong to the N direction, EN and ES belong to the E direction, SE and SW belong to the S direction, and WS and WN belong to the W direction.Figure 4
The 8-direction cone model.The 8-direction cone model is easy to describe and recognize and is flexible in dealing with relationships in multiple dimensions. Compared with the 8-direction cone model, the16-direction cone model is also consistent with the human cognition of directions, but too complicated to express. Hence, the 8-direction cone model is more suitable for the reasoning of spatial relationships.Considering its excellence in spatial segmentation, the 8-direction cone model was coupled with the RCC-5 intersection model for compound reasoning of topological and azimuth relationships in the 3D space.


### 2.3. Model Construction

Any object in space is wrapped by an outer sphere ⊙A with a radius rA (Figure 5), that is, ∀xA,yA,zA∈⊙A.Figure 5
The outer sphere.Taking the center of ⊙A as the origin of the rectangular coordinate system in space, the spatial Cartesian coordinate system can be established and the reference space can be divided into eight intervals by the x-, y-, and z-axes. Each interval is called a hexagram limit Oct=1,2,3,4,5,6,7,8 (Figure 6).Figure 6
The hexagram limits.Supposen points Bixi,yi,zi∈i=1,2,…,n are scattered in the space. The centroid bxb,yb,zb of the point set B=B1,B2,…,Bn can be obtained by k-means clustering (KMC) [20] and treated as the center of the sphere of point set B:(3)xb=xqB+xpB2,yb=yqB+ypB2,zb=zqB+zpB2.The outer sphereB completely covers the n points: ∀xBi,yBi,zBi∈⊙B. Similarly, the outer sphere C for point set C can be defined as follows:(4)xC=xqC+xpC2,yC=yqC+ypC2,zC=zqC+zpC2.∀xCi,yCi,zCi∈⊙C,If it is impossible to find the outer sphere of the space object, the object can be treated as an irregular convex object. Then, five planesπ1:y=0,π2:x=0,π3:z=0,π4:y=z, andπ5:y=−z, can be inserted into the rectangular coordinate system in space (Figure 7).Figure 7
The insertion of five planes.Then, the 3D space can be represented asDic=NE,EN,ES,SE,SW,WS,WN,NW. The angle corresponding to each region can be described as follows:(5)θNE∈0,π4,θEN∈π4,π2,θES∈π2,3π4,θSE∈3π4,π,θSW∈π,5π4,θWS∈5π4,3π2,θWN∈3π2,7π4,θNW∈7π4,2π,where θ is the dihedral angle of the plane πii=1,2,3,4,5. Adding the set of hexagram limits Oct=1,2,3,4,5,6,7,8, the space can be divided into 16 regions:(6)DO=1NE2NE3NW4NW1EN2EN3NW4NW5ES6ES7WS8WS5SE6SE7SW8SW,where DO is the set of 3D regions and their hexagram limits. If the center of outer sphere B exists in region 1NE, then B strongly exists in that region, denoted as s1NE. If outer sphere B partly exists in region 2NE, then B weakly exists in that region, denoted as w2NE. We let “0” indicate that there is no object in the area, “1” indicates that the object “strongly exists” in this area, and “2” indicates that the object “weakly exists” in this area. An example is shown in Figure 8:(7)DOS=1200200000000000.Figure 8
Examples of “weakly presence”.For simplicity, only strong existence scenarios were considered. Then, the set of regions, whereB strongly exists, can be defined as follows:(8)DOS=s1NEs2NEs3NWs4NWs1ENs2ENs3NWs4NWs5ESs6ESs7WSs8WSs5SEs6SEs7SWs8SW,where(9)s1NE;xb≥0,yb≥0,zb≥0,θob∈0,π4,s2NE;xb<0,yb≥0,zb≥0,θob∈0,π4,s1EN;xb≥0,yb≥0,zb≥0,θob∈π4,π2,s2EN;xb<0,yb≥0,zb≥0,θob∈π4,π2,s5ES;xb≥0,yb≥0,zb<0,θob∈π2,3π4,s6ES;xb<0,yb≥0,zb<0,θob∈π2,3π4,s5SE;xb≥0,yb≥0,zb<0,θob∈3π4,π,s6SE;xb<0,yb≥0,zb<0,θob∈3π4,π,s8SW;xb≥0,yb≥0,zb<0,θob∈π,5π4,s7SW;xb≥0,yb≥0,zb≥0,θob∈π,5π4,s8WS;xb≥0,yb<0,zb<0,θob∈5π4,3π2,s7WS;xb<0,yb<0,zb<0,θob∈5π4,3π2,s4WN;xb≥0,yb<0,zb≥0,θob∈3π2,7π4,s3WN;xb<0,yb<0,zb≥0,θob∈3π2,7π4,s4NW;xb≥0,yb<0,zb≥0,θob∈7π4,2π,s3NW;xb<0,yb<0,zb≥0,θob∈7π4,2π,where θob the dihedral angle formed by planes πob and π1, which is perpendicular to the x-axis and passes the straight line ab (Figure 9).Figure 9
The dihedral angle.For two regions, the extended 4-intersection matrix can be introduced to the DOS:(10)R52DOS=Ao∩BoAo∩BcoAco∩BoAco∩Bcos1NEs2ENs3NWs4NWs1ENs2ENs3NWs4NWs5ESs6ESs7WSs8WSs5SEs6SEs7SWs8SW.For three regions, the 8-intersection matrix can be introduced to the DOS:(11)R53DOS=Ao∩Bo∩CoAo∩Bo∩CcoAo∩Bco∩CoAo∩Bco∩CcoAco∩Bo∩CoAco∩Bo∩CcoAco∩Bco∩CoAco∩Bco∩Ccos1NEs2NEs3NWs4NWs1ENs2ENs3NWs4NWs5ESs6ESs7WSs8WSs5SEs6SEs7SWs8SW.Our model consists of two layers: the first layer is the topological relationshipR5 layer, and the second layer is the orientation relationship DOS layer. Then, the following definition can be derived.Definition 1.
For the orientation relationship layer, there is(12)εDOS=1,the enter of the outer sphereBexists in this region,0,otherwise.
Suppose(13)εR52DOS=εAo∩BoεAo∩BcoεAco∩BoεAco∩Bcoεs1NEεs2ENεs3NWεs4NWεs1ENεs2ENεs3NWεs4NWεs5ESεs6ESεs7WSεs8WSεs5SEεs6SEεs7SWεs8SW.
For any two simple regionsA and B, it is possible to obtain a 5 × 4‘0-1 matrix. In theory, a total of 220 matrices could be acquired, which correspond to 220 topological and directional relationships in the 3D space:(14)R53DOS=εAo∩Bo∩CoεAo∩Bo∩CcoεAo∩Bco∩CoεAo∩Bco∩CcoεAco∩Bo∩CoεAco∩Bo∩CcoεAco∩Bco∩CoεAco∩Bco∩Ccoεs1NEεs2NEεs3NWεs4NWεs1ENεs2ENεs3NWεs4NWεs5ESεs6ESεs7WSεs8WSεs5SEεs6SEεs7SWεs8SW.
Based on the topological relationship between outer spheresB and C, the existence of the centers of the two spheres can be described in two cases.Case 1.
Only the center of one outer sphere exists in the current region:(15)εDOS=0,no center exists in the current region,1,the center of outer sphereBexists in the current region,2,the center of outer sphereCexists in the current region.Case 2.
The centers of both outer spheres exist in the current region:(16)εDOS=0,no center exists in the current region,1,the centers of both outer spheres exist in the current region.
According to the above conditions, 28 × 316 matrices could be obtained theoretically, which correspond to 28 × 316 topological and directional relationships in the 3D space.


### 2.4. Model Properties

Definition 2.
In layerR5, any m × n -order 0-1 matrices A=aijm×n and B=bijm×n can be defined as A∪B=aij∨bijm×n. Then, a 0-1 diagonal matrix can be established as Table 2.
The following proposition can be derived from Table2:Table 2
The 0-1 diagonal matrix.
∨01001111Proposition 1.
εA∪B=εA∨εB.
ForR5=0111,1111,1011,1001,1101, R (A, B) is the element that corresponds to the topological relationship R5 between any two simple regions A and B.Then, the following theorem can be obtained.Theorem 1.
For simple regionsA, B, and C, there exists εAo∩BoεAo∩BcoεAco∩BoεAoC∩Bco=RA,B∈R5.
Similarly, there existsεAo∩CoεAo∩CcoεAco∩CoεAoC∩Cco=RA,C∈R5.Theorem 2.
In the 3D space given by the R5DOS-intersection matrix, the topological relationship between the three simple regions is mutually exclusive and complete. The DOS space of the R5DOS-intersection matrix, which consists of 16 regions, is a half-open, half-closed interval with mutual exclusion. That is, for any three simple regionsA, B, and C in the 3D space, there exists only one relationship satisfied by the ordered pair <A, B, C>.Proof.
For any three simple regionsA, B, and C, the 8 and 16 regions divided by the 8-interesection matrix are disjoint. The 0-1 matrix of three simple regions uniquely corresponds to the matrix derived from the R5DOS-intersection model. In other words, the three regions have the relationship represented by this matrix so that the R5DOS-intersection matrix model gives a complete topological relationship in the 3D space.
Then, it is assumed that the topological relationship betweenA, B, and C corresponds to two matrices R53DOSa and R53DOSb and can be induced by the R53DOS-intersection model. Then, there exists 1≤i≤24 such that R53DOSai≠R53DOSbi. If i=1,R53DOSai=0andR53DOSbi=1, A°∩B°∩C° is both empty and nonempty, which is obviously contradictory. Hence, the above theorem was proved valid.


### 2.5. Constraints on Two Simple Regions

Theoretically, two simple regions might correspond to 220 matrices, but there must be 0-1 matrices that cannot be realized. Therefore, the following constraints were designed on two simple regions.Constraint 1: to correspond to a real-world topological relationship, the 0-1 matrix of layerR5 must belong to one of the five cases: R5=0111,1111,1011,1001,1101.Constraint 2: if layerR5 satisfies R5=1001, that is, outer spheres A and B are equal, then the 0-1 matrix of the DOS layer is DOS=0000000000000000. This means, when outer spheres A and B are equal, the center b of outer sphere B is G, which coincides with that of outer sphere A: bxb,yb,zb=0,0,0.Constraint 3: since the 16 regions are disjoint, they must be mutually exclusive and complete. IfR (A, B) does not fall at the center of outer sphere B, it can only exist in one of these regions. In the DOS layer, an outer sphere only exists in one of the 16 intervals. In this way, a total of 65 directional and topological relationships can be obtained (Table 3).Case 1.
(17)DRs1NE,DRs2NE,DRs1EN,DRs2EN,DRs5ES,DRs6ES,DRs5SE,DRs6SE,DRs8SW,DRs7SW,DRs8WS,DRs7WS,DRs4WN,DRs3WN,DRs4NW,DRs3NW∈DRall,POs1NE,POs2NE,POs1EN,POs2EN,POs5ES,POs6ES,POs5SE,POs6SE,POs8SW,POs7SW,POs8WS,POs7WS,POs4WN,POs3WN,POs4NW,POs3NW∈POall,PPs1NE,PPs2NE,PPs1EN,PPs2EN,PPs5ES,PPs6ES,PPs5SE,PPs6SE,PPs8SW,PPs7SW,PPs8WS,PPs7WS,PPs4WN,PPs3WN,PPs4NW,PPs3NW∈PPall,PPIs1NE,PPIs2NE,PPIs1EN,PPIs2EN,PPIs5ES,PPIs6ES,PPIs5SE,PPIs6SE,PPIs8SW,PPIs7SW,PPIs8WS,PPIs7WS,PPIs4WN,PPIs3WN,PPIs4NW,PPIs3NW∈PPIall.Case 2.
(18)DRall,POall,PPall,EQ,PPIall∈Φ.


### 2.6. Constraints on Three Simple Regions

The following constraints were designed on three simple regions.Constraint 1: to uniquely correspond to the topological and directional relationships in the 3D space, aR53DOS matrix must satisfy the following conditions.Definition 3.
(19)εAo∩Bo∩CoεAo∩Bco∩CoεAco∩Bo∩CoεAco∩Bco∩Co∨εAo∩Bo∩CcoεAo∩Bco∩CcoεAco∩Bo∩CcoεACo∩Bco∩Cco,RA,B=εAo∩BoεAo∩BcoεAco∩BoεAoC∩Bco∈R5,εAo∩Bo∩CoεAo∩Bo∩CcoεAco∩Bo∩CoεAco∩Bo∩Cco∨εAo∩Bco∩CoεAo∩Cco∩CcoεAco∩Bco∩CoεAco∩Bco∩Cco,RA,C=εAo∩CoεAo∩CcoεAco∩CoεAoC∩Cco∈R5,εAo∩Bo∩CoεAo∩Bo∩CcoεAo∩Bco∩CoεAo∩Bco∩Cco∨εAco∩Bo∩CoεAco∩Bo∩CcoεAco∩Bco∩CoεACo∩Bco∩Cco,RB,C=εBo∩CoεBo∩CcoεBco∩CoεBoC∩Cco∈R5.Constraint 2: since all three simple regions are bounded,AC°∩​BC°∩​CC° is always 1.From Constraints 1 and 2, it can be inferred that layerR5 has109 topological relationships for any three simple regions in the 3D space.Constraint 3: after adding the orientation relationship, some topological relationships are not satisfied in the orientation regions. In some topological relationships, the center of an outer sphere will change with that of the other outer spheres. For instance, if layerR5=01011001, the outer sphere B will change with the overlap between outer spheres A and C (Figure 10).Case 1: if theA, B, and C are equal, they can be regarded as one area:(20)DOS=0000000000000000.Case 2: if any two of the three simple regions are equal, the ternary region can be regarded as a binary region with only one 1 in the DOS layer.Case 3: if any two of the three simple regions are inclusive or noninclusive, the ternary region can be regarded as a binary region when any two regions intersect and the sum of layerR5 is 4.Case 4: if only one of the three simple regions is inclusive or noninclusive, the ternary region can be regarded as a binary region when any two regions intersect and the sum of layerR5 is 5.Case 5: if the three simple regions are disjoint, the ternary region can be regarded as a binary region when any two regions intersect and the sum of layerR5 is 5.Case 6: if simple regionsB and C are inclusive or noninclusive and separated from A, then the center of the A can only fall within B and C:(21)xin,yin,zin∈Pout.
For a ternary reference object in the 3D space, there are theoretically 28 × 316 matrices. Under the above constraints, a total of 11,038 matrices were obtained after removing the nonexistent scenarios.


### 2.7. Topological Relationship Algorithm for 3 Simple Regions in the 3D Space

The topological relationship algorithm for 3 simple regions in the 3D space can be implemented in the following steps.Step 1: assign each object a row vector [a1, a2, …, a24]. Generate a theoretical object of the type 28 × 316, i.e., a matrix A of 28 × 316 row vectors.Step 2: scan each row of matrixA, and mark all row vectors that satisfy the constraints.Step 3: save all the marked row vectors as a matrixB and output the matrix as the final result.The pseudocode of the algorithm is displayed as follows.Topological and directional relationship:Gen (null;R53DOSa)//Input: null; output: topological relationship satisfying constraints (Algorithm 1).Algorithm 1
(1)
R53DOSaALL ⟵ 28 ∗ 316 basic topological relationships//All basic topological relationships(2)
R53DOSa  ⟵  null//TR empty Test(3)
for eachx in R53DOSaALL(4)
ifx satisfies Constraint 1//if t satisfies Constraint 1Test(5)
ifx satisfies Constraint 2//if t satisfies Constraint 2Test(6)
ifx satisfies Constraint 3//if t satisfies Constraint 3(7)
R53DOSa ⟵ {R53DOSa, x}//If the constraint is satisfied, t is placed in TR(8)
end if(9)
end if(10)
end for(11)
returnR53DOSa//Return result


## 2.1. RCC Theory

In 1992, Randell et al. [4, 5] proposed the RCC theory and established the RCC-8 intersection model, which is a boundary-sensitive model. Based on the boundary-sensitive conditions, the RCC-5 intersection model can be derived (Figure 1).Figure 1
The relationships between RCC-8 and RCC-5 intersection models.In 1991 and 1995, Egenhofer et al. constructed an extended 4-intersection matrix, which covers two space objectsA and B, with A° being the interior of A:(1)Ao∩BoAo∩BcoAoo∩BoAoC∩Bco.The value of each position set is either empty or nonempty. Then, the five kinds of relationships in the RCC-5 intersection model can be represented as the matrix in Table1 and expressed as a set R5=0111,1111,1011,1001,1101.Table 1
Matrix representation of the RCC-5 relationships.
RCC5 relationshipsDR (A, B)PO (A, B)PP (A, B)EQ (A, B)PPI (A, B)Extended 4-intersection matrix representation01111111101110011101For three simple areasA, B, and C, R2−∂A∪∂B∪∂C can be partitioned into 8 parts (Figure 2).Figure 2
The spatial partition of three simple areas.The eight parts can be illustrated by an 8-intersection matrix:(2)Ao∩Bo∩CoAo∩Bo∩CcoAo∩Bco∩CoAo∩Bco∩CcoAco∩Bo∩CoAco∩Bo∩CcoAco∩Bco∩CoAco∩Bco∩Cco.The RCC theory fuels the research on spatial relationship models in the past three decades, giving birth to many new theories. Nonetheless, most of these theories target the 2D plane rather than the 3D space. Recently, there is a growing interest in the spatial relationship models of the 3D space, especially the compound reasoning of directional and topological relationships, and that of directional and distance relationships.


## 2.2. Orientation Model

Minimum bounding rectangle (MBR) is a commonly used model for directional relationship in space [18–20]. The MBR model, 8-direction model, and 16-direction model are shown in Figure 3 below. The MBR model is not consistent with human cognition of directions.Figure 3
(a) The MBR model, (b) 8-direction model, and (c) 16-direction model.
(a)(b)(c)In 2010, He and Bian [21] came up with a special 8-direction cone model (Figure 4), which divides the space into eight regions: NW, NE, EN, ES, SE, SW, WS, and WN. Among them, NW and NE belong to the N direction, EN and ES belong to the E direction, SE and SW belong to the S direction, and WS and WN belong to the W direction.Figure 4
The 8-direction cone model.The 8-direction cone model is easy to describe and recognize and is flexible in dealing with relationships in multiple dimensions. Compared with the 8-direction cone model, the16-direction cone model is also consistent with the human cognition of directions, but too complicated to express. Hence, the 8-direction cone model is more suitable for the reasoning of spatial relationships.Considering its excellence in spatial segmentation, the 8-direction cone model was coupled with the RCC-5 intersection model for compound reasoning of topological and azimuth relationships in the 3D space.


## 2.3. Model Construction

Any object in space is wrapped by an outer sphere ⊙A with a radius rA (Figure 5), that is, ∀xA,yA,zA∈⊙A.Figure 5
The outer sphere.Taking the center of ⊙A as the origin of the rectangular coordinate system in space, the spatial Cartesian coordinate system can be established and the reference space can be divided into eight intervals by the x-, y-, and z-axes. Each interval is called a hexagram limit Oct=1,2,3,4,5,6,7,8 (Figure 6).Figure 6
The hexagram limits.Supposen points Bixi,yi,zi∈i=1,2,…,n are scattered in the space. The centroid bxb,yb,zb of the point set B=B1,B2,…,Bn can be obtained by k-means clustering (KMC) [20] and treated as the center of the sphere of point set B:(3)xb=xqB+xpB2,yb=yqB+ypB2,zb=zqB+zpB2.The outer sphereB completely covers the n points: ∀xBi,yBi,zBi∈⊙B. Similarly, the outer sphere C for point set C can be defined as follows:(4)xC=xqC+xpC2,yC=yqC+ypC2,zC=zqC+zpC2.∀xCi,yCi,zCi∈⊙C,If it is impossible to find the outer sphere of the space object, the object can be treated as an irregular convex object. Then, five planesπ1:y=0,π2:x=0,π3:z=0,π4:y=z, andπ5:y=−z, can be inserted into the rectangular coordinate system in space (Figure 7).Figure 7
The insertion of five planes.Then, the 3D space can be represented asDic=NE,EN,ES,SE,SW,WS,WN,NW. The angle corresponding to each region can be described as follows:(5)θNE∈0,π4,θEN∈π4,π2,θES∈π2,3π4,θSE∈3π4,π,θSW∈π,5π4,θWS∈5π4,3π2,θWN∈3π2,7π4,θNW∈7π4,2π,where θ is the dihedral angle of the plane πii=1,2,3,4,5. Adding the set of hexagram limits Oct=1,2,3,4,5,6,7,8, the space can be divided into 16 regions:(6)DO=1NE2NE3NW4NW1EN2EN3NW4NW5ES6ES7WS8WS5SE6SE7SW8SW,where DO is the set of 3D regions and their hexagram limits. If the center of outer sphere B exists in region 1NE, then B strongly exists in that region, denoted as s1NE. If outer sphere B partly exists in region 2NE, then B weakly exists in that region, denoted as w2NE. We let “0” indicate that there is no object in the area, “1” indicates that the object “strongly exists” in this area, and “2” indicates that the object “weakly exists” in this area. An example is shown in Figure 8:(7)DOS=1200200000000000.Figure 8
Examples of “weakly presence”.For simplicity, only strong existence scenarios were considered. Then, the set of regions, whereB strongly exists, can be defined as follows:(8)DOS=s1NEs2NEs3NWs4NWs1ENs2ENs3NWs4NWs5ESs6ESs7WSs8WSs5SEs6SEs7SWs8SW,where(9)s1NE;xb≥0,yb≥0,zb≥0,θob∈0,π4,s2NE;xb<0,yb≥0,zb≥0,θob∈0,π4,s1EN;xb≥0,yb≥0,zb≥0,θob∈π4,π2,s2EN;xb<0,yb≥0,zb≥0,θob∈π4,π2,s5ES;xb≥0,yb≥0,zb<0,θob∈π2,3π4,s6ES;xb<0,yb≥0,zb<0,θob∈π2,3π4,s5SE;xb≥0,yb≥0,zb<0,θob∈3π4,π,s6SE;xb<0,yb≥0,zb<0,θob∈3π4,π,s8SW;xb≥0,yb≥0,zb<0,θob∈π,5π4,s7SW;xb≥0,yb≥0,zb≥0,θob∈π,5π4,s8WS;xb≥0,yb<0,zb<0,θob∈5π4,3π2,s7WS;xb<0,yb<0,zb<0,θob∈5π4,3π2,s4WN;xb≥0,yb<0,zb≥0,θob∈3π2,7π4,s3WN;xb<0,yb<0,zb≥0,θob∈3π2,7π4,s4NW;xb≥0,yb<0,zb≥0,θob∈7π4,2π,s3NW;xb<0,yb<0,zb≥0,θob∈7π4,2π,where θob the dihedral angle formed by planes πob and π1, which is perpendicular to the x-axis and passes the straight line ab (Figure 9).Figure 9
The dihedral angle.For two regions, the extended 4-intersection matrix can be introduced to the DOS:(10)R52DOS=Ao∩BoAo∩BcoAco∩BoAco∩Bcos1NEs2ENs3NWs4NWs1ENs2ENs3NWs4NWs5ESs6ESs7WSs8WSs5SEs6SEs7SWs8SW.For three regions, the 8-intersection matrix can be introduced to the DOS:(11)R53DOS=Ao∩Bo∩CoAo∩Bo∩CcoAo∩Bco∩CoAo∩Bco∩CcoAco∩Bo∩CoAco∩Bo∩CcoAco∩Bco∩CoAco∩Bco∩Ccos1NEs2NEs3NWs4NWs1ENs2ENs3NWs4NWs5ESs6ESs7WSs8WSs5SEs6SEs7SWs8SW.Our model consists of two layers: the first layer is the topological relationshipR5 layer, and the second layer is the orientation relationship DOS layer. Then, the following definition can be derived.Definition 1.
For the orientation relationship layer, there is(12)εDOS=1,the enter of the outer sphereBexists in this region,0,otherwise.
Suppose(13)εR52DOS=εAo∩BoεAo∩BcoεAco∩BoεAco∩Bcoεs1NEεs2ENεs3NWεs4NWεs1ENεs2ENεs3NWεs4NWεs5ESεs6ESεs7WSεs8WSεs5SEεs6SEεs7SWεs8SW.
For any two simple regionsA and B, it is possible to obtain a 5 × 4‘0-1 matrix. In theory, a total of 220 matrices could be acquired, which correspond to 220 topological and directional relationships in the 3D space:(14)R53DOS=εAo∩Bo∩CoεAo∩Bo∩CcoεAo∩Bco∩CoεAo∩Bco∩CcoεAco∩Bo∩CoεAco∩Bo∩CcoεAco∩Bco∩CoεAco∩Bco∩Ccoεs1NEεs2NEεs3NWεs4NWεs1ENεs2ENεs3NWεs4NWεs5ESεs6ESεs7WSεs8WSεs5SEεs6SEεs7SWεs8SW.
Based on the topological relationship between outer spheresB and C, the existence of the centers of the two spheres can be described in two cases.Case 1.
Only the center of one outer sphere exists in the current region:(15)εDOS=0,no center exists in the current region,1,the center of outer sphereBexists in the current region,2,the center of outer sphereCexists in the current region.Case 2.
The centers of both outer spheres exist in the current region:(16)εDOS=0,no center exists in the current region,1,the centers of both outer spheres exist in the current region.
According to the above conditions, 28 × 316 matrices could be obtained theoretically, which correspond to 28 × 316 topological and directional relationships in the 3D space.


## 2.4. Model Properties

Definition 2.
In layerR5, any m × n -order 0-1 matrices A=aijm×n and B=bijm×n can be defined as A∪B=aij∨bijm×n. Then, a 0-1 diagonal matrix can be established as Table 2.
The following proposition can be derived from Table2:Table 2
The 0-1 diagonal matrix.
∨01001111Proposition 1.
εA∪B=εA∨εB.
ForR5=0111,1111,1011,1001,1101, R (A, B) is the element that corresponds to the topological relationship R5 between any two simple regions A and B.Then, the following theorem can be obtained.Theorem 1.
For simple regionsA, B, and C, there exists εAo∩BoεAo∩BcoεAco∩BoεAoC∩Bco=RA,B∈R5.
Similarly, there existsεAo∩CoεAo∩CcoεAco∩CoεAoC∩Cco=RA,C∈R5.Theorem 2.
In the 3D space given by the R5DOS-intersection matrix, the topological relationship between the three simple regions is mutually exclusive and complete. The DOS space of the R5DOS-intersection matrix, which consists of 16 regions, is a half-open, half-closed interval with mutual exclusion. That is, for any three simple regionsA, B, and C in the 3D space, there exists only one relationship satisfied by the ordered pair <A, B, C>.Proof.
For any three simple regionsA, B, and C, the 8 and 16 regions divided by the 8-interesection matrix are disjoint. The 0-1 matrix of three simple regions uniquely corresponds to the matrix derived from the R5DOS-intersection model. In other words, the three regions have the relationship represented by this matrix so that the R5DOS-intersection matrix model gives a complete topological relationship in the 3D space.
Then, it is assumed that the topological relationship betweenA, B, and C corresponds to two matrices R53DOSa and R53DOSb and can be induced by the R53DOS-intersection model. Then, there exists 1≤i≤24 such that R53DOSai≠R53DOSbi. If i=1,R53DOSai=0andR53DOSbi=1, A°∩B°∩C° is both empty and nonempty, which is obviously contradictory. Hence, the above theorem was proved valid.


## 2.5. Constraints on Two Simple Regions

Theoretically, two simple regions might correspond to 220 matrices, but there must be 0-1 matrices that cannot be realized. Therefore, the following constraints were designed on two simple regions.Constraint 1: to correspond to a real-world topological relationship, the 0-1 matrix of layerR5 must belong to one of the five cases: R5=0111,1111,1011,1001,1101.Constraint 2: if layerR5 satisfies R5=1001, that is, outer spheres A and B are equal, then the 0-1 matrix of the DOS layer is DOS=0000000000000000. This means, when outer spheres A and B are equal, the center b of outer sphere B is G, which coincides with that of outer sphere A: bxb,yb,zb=0,0,0.Constraint 3: since the 16 regions are disjoint, they must be mutually exclusive and complete. IfR (A, B) does not fall at the center of outer sphere B, it can only exist in one of these regions. In the DOS layer, an outer sphere only exists in one of the 16 intervals. In this way, a total of 65 directional and topological relationships can be obtained (Table 3).Case 1.
(17)DRs1NE,DRs2NE,DRs1EN,DRs2EN,DRs5ES,DRs6ES,DRs5SE,DRs6SE,DRs8SW,DRs7SW,DRs8WS,DRs7WS,DRs4WN,DRs3WN,DRs4NW,DRs3NW∈DRall,POs1NE,POs2NE,POs1EN,POs2EN,POs5ES,POs6ES,POs5SE,POs6SE,POs8SW,POs7SW,POs8WS,POs7WS,POs4WN,POs3WN,POs4NW,POs3NW∈POall,PPs1NE,PPs2NE,PPs1EN,PPs2EN,PPs5ES,PPs6ES,PPs5SE,PPs6SE,PPs8SW,PPs7SW,PPs8WS,PPs7WS,PPs4WN,PPs3WN,PPs4NW,PPs3NW∈PPall,PPIs1NE,PPIs2NE,PPIs1EN,PPIs2EN,PPIs5ES,PPIs6ES,PPIs5SE,PPIs6SE,PPIs8SW,PPIs7SW,PPIs8WS,PPIs7WS,PPIs4WN,PPIs3WN,PPIs4NW,PPIs3NW∈PPIall.Case 2.
(18)DRall,POall,PPall,EQ,PPIall∈Φ.


## 2.6. Constraints on Three Simple Regions

The following constraints were designed on three simple regions.Constraint 1: to uniquely correspond to the topological and directional relationships in the 3D space, aR53DOS matrix must satisfy the following conditions.Definition 3.
(19)εAo∩Bo∩CoεAo∩Bco∩CoεAco∩Bo∩CoεAco∩Bco∩Co∨εAo∩Bo∩CcoεAo∩Bco∩CcoεAco∩Bo∩CcoεACo∩Bco∩Cco,RA,B=εAo∩BoεAo∩BcoεAco∩BoεAoC∩Bco∈R5,εAo∩Bo∩CoεAo∩Bo∩CcoεAco∩Bo∩CoεAco∩Bo∩Cco∨εAo∩Bco∩CoεAo∩Cco∩CcoεAco∩Bco∩CoεAco∩Bco∩Cco,RA,C=εAo∩CoεAo∩CcoεAco∩CoεAoC∩Cco∈R5,εAo∩Bo∩CoεAo∩Bo∩CcoεAo∩Bco∩CoεAo∩Bco∩Cco∨εAco∩Bo∩CoεAco∩Bo∩CcoεAco∩Bco∩CoεACo∩Bco∩Cco,RB,C=εBo∩CoεBo∩CcoεBco∩CoεBoC∩Cco∈R5.Constraint 2: since all three simple regions are bounded,AC°∩​BC°∩​CC° is always 1.From Constraints 1 and 2, it can be inferred that layerR5 has109 topological relationships for any three simple regions in the 3D space.Constraint 3: after adding the orientation relationship, some topological relationships are not satisfied in the orientation regions. In some topological relationships, the center of an outer sphere will change with that of the other outer spheres. For instance, if layerR5=01011001, the outer sphere B will change with the overlap between outer spheres A and C (Figure 10).Case 1: if theA, B, and C are equal, they can be regarded as one area:(20)DOS=0000000000000000.Case 2: if any two of the three simple regions are equal, the ternary region can be regarded as a binary region with only one 1 in the DOS layer.Case 3: if any two of the three simple regions are inclusive or noninclusive, the ternary region can be regarded as a binary region when any two regions intersect and the sum of layerR5 is 4.Case 4: if only one of the three simple regions is inclusive or noninclusive, the ternary region can be regarded as a binary region when any two regions intersect and the sum of layerR5 is 5.Case 5: if the three simple regions are disjoint, the ternary region can be regarded as a binary region when any two regions intersect and the sum of layerR5 is 5.Case 6: if simple regionsB and C are inclusive or noninclusive and separated from A, then the center of the A can only fall within B and C:(21)xin,yin,zin∈Pout.
For a ternary reference object in the 3D space, there are theoretically 28 × 316 matrices. Under the above constraints, a total of 11,038 matrices were obtained after removing the nonexistent scenarios.


## 2.7. Topological Relationship Algorithm for 3 Simple Regions in the 3D Space

The topological relationship algorithm for 3 simple regions in the 3D space can be implemented in the following steps.Step 1: assign each object a row vector [a1, a2, …, a24]. Generate a theoretical object of the type 28 × 316, i.e., a matrix A of 28 × 316 row vectors.Step 2: scan each row of matrixA, and mark all row vectors that satisfy the constraints.Step 3: save all the marked row vectors as a matrixB and output the matrix as the final result.The pseudocode of the algorithm is displayed as follows.Topological and directional relationship:Gen (null;R53DOSa)//Input: null; output: topological relationship satisfying constraints (Algorithm 1).Algorithm 1
(1)
R53DOSaALL ⟵ 28 ∗ 316 basic topological relationships//All basic topological relationships(2)
R53DOSa  ⟵  null//TR empty Test(3)
for eachx in R53DOSaALL(4)
ifx satisfies Constraint 1//if t satisfies Constraint 1Test(5)
ifx satisfies Constraint 2//if t satisfies Constraint 2Test(6)
ifx satisfies Constraint 3//if t satisfies Constraint 3(7)
R53DOSa ⟵ {R53DOSa, x}//If the constraint is satisfied, t is placed in TR(8)
end if(9)
end if(10)
end for(11)
returnR53DOSa//Return result


## 3. Results and Discussion

### 3.1. Comparison between R53DOS-Intersection Model and MBR Model

This section proves that the R53DOS-intersection model has stronger expressive power than the MBR model in the 3D space [21–23].First, layerR5 was defined as R (A, B) = PPI, R (A, C) = PPI, and R (B, C) = PPI, and the center of outer sphere B was assumed to fall into 1NE or 2NE. This situation does not exist in the real world. Under Constraints 2 and 4, there is no solution to this situation. However, the R53DOS-intersection model can explain the situation that cannot be realized in the 3D space.Next, the R53DOS-intersection model was found capable of expressing situation that cannot be illustrated by the MBR model through the analysis of the following example. For any three external spheres A–C in the 3D space, it is assumed that the topological and azimuth relationships between them are known, and these spheres are separated from each other.For the MBR model, Example 1: (a) dir (A, B)=(1, 1, 1) and (b) dir (A, C)=(1, 1, 1) were obtained for the two examples (Figures 11 and 12).Figure 10
Special case.Figure 11
MBR model in Example 1(a).Figure 12
MBR model in Example 1(b).For the R53DOS-intersection model, layer R5 can be described asR (A, B) = DR, R (A, C) = DR, and R (B, C) = DR. Then,(22)εAo∩Bo∩CoεAo∩Bco∩CoεAco∩Bo∩CoεAco∩Bco∩Co∨εAo∩Bo∩CcoεAo∩Bco∩CcoεAco∩Bo∩CcoεAco∩Bco∩Cco,RA,B=εAo∩BoεAo∩BcoεAoo∩BoεAoC∩Bco=0111,εAo∩Bo∩CoεAo∩Bo∩CcoεAco∩Bo∩CoεAco∩Bo∩Cco∨εAo∩Bco∩CoεAo∩Bco∩CcoεAco∩Bco∩CoεACo∩Bco∩Cco,RA,C=εAo∩CoεAo∩CcoεAco∩CoεAcC∩Cco=0111,εAo∩Bo∩CoεAo∩Bo∩CcoεAo∩Bco∩CoεAo∩Bco∩Cco∨εAco∩Bo∩CoεAco∩Bo∩CcoεAco∩Bco∩CoεACo∩Bco∩Cco,RB,C=εBo∩CoεBo∩CcoεBco∩CoεBoC∩Cco=0111.Without changing the positions ofA–C, the images of the R53DOS-intersection model in the two examples can be obtained as Figures 13 and 14, where green, blue, and red balls are the outer spheres A–C, respectively.(23)R53DOS1=000101110000100000000000,(24)R53DOS2=000101112000100000000000.Figure 13
R53DOS-intersection model in Example 1(a).Figure 14
R53DOS-intersection model in Example 1(b).Example 2.
(a) dir (A, B)=(0, 0, 1) and (b) dir (A, C) = (0, 1, 1) were obtained for the two examples (Figures 15 and 16).
In the same way, we can get the corresponding R53DOS-intersection model (Figures 17 and 18):(25)R53DOS3=100011112000000000000000,(26)R53DOS4=100011012100000000000000.
Through the above comparison, it can be seen that the R53DOS-intersection model can represent the topological relationship of space objects A, B, and C, and it can accurately represent the spatial situation that the MBR model cannot represent.Figure 15
MBR model in Example 2(a).Figure 16
MBR model in Example 2(b).Figure 17
R53DOS-intersection model in Example 2(a).Figure 18
R53DOS-intersection model in Example 2(a).


### 3.2. Comnd Relationship Reasoning Based on R53DOS-Intersection Model

This section applies the R53DOS-Intersection Model to the reasoning of the compound relationships between simple regions in the 3D space. It is assumed that the topological and azimuth relationships between simple regions A and B and those between simple regions B and C are known in advance. Then, the goal is to deduce the possible topological and azimuth relationships between simple regions A and C.According to Section 2.3, we have(27)R52DOS=Ao∩BoAo∩BcoAco∩BoAco∩Bcos1NEs2ENs3NWs4NWs1ENs2ENs3NWs4NWs5ESs6ESs7WSs8WSs5SEs6SEs7SWs8SW.Using the R53DOS-intersection model, a total of 65 topological and azimuth relationships were obtained from the real world. Hence, it is possible to obtain 65 0-1 matrices of 5 rows and 4 columns, which is denoted as Ω1=Ri;i=1,…,65Ri. Targeting at region A, the topological and directional relationships between A and C and those between B and C were taken into account.Since the topological and azimuth relationships between simple regionsA and B and those between simple regions B and C are known in advance, we have RB,C∈Ω1. Then, the possible topological and orientation relationships between A and C were derived from the R53DOS-intersection model. According to Definition 2, we have(28)εAo∩Bo∩CoεAo∩Bco∩CoεAco∩Bo∩CoεAco∩Bco∩Co∨εAo∩Bo∩CcoεAo∩Bco∩CcoεAco∩Bo∩CcoεACo∩Bco∩Cco,RA,B=εAo∩BoεAo∩BcoεAco∩BoεAoC∩Bco,εAo∩Bo∩CoεAo∩Bo∩CcoεAo∩Bco∩CoεAo∩Bco∩Cco∨εAco∩Bo∩CoεAco∩Bo∩CcoεAco∩Bco∩CoεACo∩Bco∩Cco,RB,C=εBo∩CoεBo∩CcoεBco∩CoεBoC∩Cco.Suppose the real-world 0-1 matrices satisfy(29)M=Mi=1,…,n,Then, all 0-1 matrices must meet:(30)mi=RA,B∨RB,C,i=1,…,n.Hence, the matrix that does not satisfy the condition belongs to the empty set, namely,M∈∅. This shows the topological and directional relationships R (A, B) and R (A, C) cannot be compounded. Then, all 0-1 matrices represented in the R53DOS-intersection model were judged one by one. The duplicates in the set {Mi = 1, …, n} were removed, leaving the possible topological and azimuth relationships between A and C.In theory, there are a total of 65 × 65 = 4,225 topological-azimuth relationshipsR (A, B) and R (B, C). On this basis, the compound relationship reasoning table was set up (Table 4).Table 3
The list of all directional and topological relationships.
Topological relationshipsRegionsDRDRs1NE,DRs2NE,DRs1EN,DRs2EN,DRs5ES,DRs6ES,DRs5SE,DRs6SE,DRs8SW,DRs7SW,DRs8WS,DRs7WS,DRs4WN,DRs3WN,DRs4NW,DRs3NWPOPOs1NE,POs2NE,POs1EN,POs2EN,POs5ES,POs6ES,POs5SE,POs6SE,POs8SW,POs7SW,POs8WS,POs7WS,POs4WN,POs3WN,POs4NW,POs3NWPPPPs1NE,PPs2NE,PPs1EN,PPs2EN,PPs5ES,PPs6ES,PPs5SE,PPs6SE,PPs8SW,PPs7SW,PPs8WS,PPs7WS,PPs4WN,PPs3WN,PPs4NW,PPs3NWEQEqualPPIPPIs1NE,PPIs2NE,PPIs1EN,PPIs2EN,PPIs5ES,PPIs6ES,PPIs5SE,PPIs6SE,PPIs8SW,PPIs7SW,PPIs8WS,PPIs7WS,PPIs4WN,PPIs3WN,PPIs4NW,PPIs3NWTable 4
Compound relationship reasoning table.
R (B, C)R (A, B)R (A, C)DR (B, C)all (A, B)ΦPOall (A, B)DRall (A, C); POall (A, C); PPIall (A, C)PPall (A, B)all (A, C)EQall (A, B)all (A, C)PPIall (A, B)DRall (A, C); POall (A, C); PPIall (A, C)PO (B, C)DRall (A, B)DRall (A, C); POall (A, C); PPall (A, C)POall (A, B)ΦPPall (A, B)DRall (A, C); POall (A, C); PPall (A, C)EQall (A, B)POall (A, C)PPIall (A, B)POall (A, C); PPIall (A, C)PP (B, C)DRall (A, B)DRall (A, C); POall (A, C); PPall (A, C)POall (A, B)POall (A, C); PPall (A, C)PPall (A, B)PPall (A, C)EQall (A, B)PPall (A, C)PPIall (A, B)POall (A, C); EQall (A, C); PPall (A, C); PPIall (A, C)EQ (B, C)DRall (A, B)all (A, C)POall (A, B)POall (A, C)PPall (A, B)PPall (A, C)EQall (A, B)EQall (A, C)PPIall (A, B)PPIall (A, C)PPI (B, C)DRall (A, B)DRall (A, C)POall (A, B)DRall (A, C); POall (A, C); PPIall (A, C)PPall (A, B)ΦEQall (A, B)PPIall (A, C)PPIall (A, B)PPIall (A, C)


## 3.1. Comparison between R53DOS-Intersection Model and MBR Model

This section proves that the R53DOS-intersection model has stronger expressive power than the MBR model in the 3D space [21–23].First, layerR5 was defined as R (A, B) = PPI, R (A, C) = PPI, and R (B, C) = PPI, and the center of outer sphere B was assumed to fall into 1NE or 2NE. This situation does not exist in the real world. Under Constraints 2 and 4, there is no solution to this situation. However, the R53DOS-intersection model can explain the situation that cannot be realized in the 3D space.Next, the R53DOS-intersection model was found capable of expressing situation that cannot be illustrated by the MBR model through the analysis of the following example. For any three external spheres A–C in the 3D space, it is assumed that the topological and azimuth relationships between them are known, and these spheres are separated from each other.For the MBR model, Example 1: (a) dir (A, B)=(1, 1, 1) and (b) dir (A, C)=(1, 1, 1) were obtained for the two examples (Figures 11 and 12).Figure 10
Special case.Figure 11
MBR model in Example 1(a).Figure 12
MBR model in Example 1(b).For the R53DOS-intersection model, layer R5 can be described asR (A, B) = DR, R (A, C) = DR, and R (B, C) = DR. Then,(22)εAo∩Bo∩CoεAo∩Bco∩CoεAco∩Bo∩CoεAco∩Bco∩Co∨εAo∩Bo∩CcoεAo∩Bco∩CcoεAco∩Bo∩CcoεAco∩Bco∩Cco,RA,B=εAo∩BoεAo∩BcoεAoo∩BoεAoC∩Bco=0111,εAo∩Bo∩CoεAo∩Bo∩CcoεAco∩Bo∩CoεAco∩Bo∩Cco∨εAo∩Bco∩CoεAo∩Bco∩CcoεAco∩Bco∩CoεACo∩Bco∩Cco,RA,C=εAo∩CoεAo∩CcoεAco∩CoεAcC∩Cco=0111,εAo∩Bo∩CoεAo∩Bo∩CcoεAo∩Bco∩CoεAo∩Bco∩Cco∨εAco∩Bo∩CoεAco∩Bo∩CcoεAco∩Bco∩CoεACo∩Bco∩Cco,RB,C=εBo∩CoεBo∩CcoεBco∩CoεBoC∩Cco=0111.Without changing the positions ofA–C, the images of the R53DOS-intersection model in the two examples can be obtained as Figures 13 and 14, where green, blue, and red balls are the outer spheres A–C, respectively.(23)R53DOS1=000101110000100000000000,(24)R53DOS2=000101112000100000000000.Figure 13
R53DOS-intersection model in Example 1(a).Figure 14
R53DOS-intersection model in Example 1(b).Example 2.
(a) dir (A, B)=(0, 0, 1) and (b) dir (A, C) = (0, 1, 1) were obtained for the two examples (Figures 15 and 16).
In the same way, we can get the corresponding R53DOS-intersection model (Figures 17 and 18):(25)R53DOS3=100011112000000000000000,(26)R53DOS4=100011012100000000000000.
Through the above comparison, it can be seen that the R53DOS-intersection model can represent the topological relationship of space objects A, B, and C, and it can accurately represent the spatial situation that the MBR model cannot represent.Figure 15
MBR model in Example 2(a).Figure 16
MBR model in Example 2(b).Figure 17
R53DOS-intersection model in Example 2(a).Figure 18
R53DOS-intersection model in Example 2(a).


## 3.2. Comnd Relationship Reasoning Based on R53DOS-Intersection Model

This section applies the R53DOS-Intersection Model to the reasoning of the compound relationships between simple regions in the 3D space. It is assumed that the topological and azimuth relationships between simple regions A and B and those between simple regions B and C are known in advance. Then, the goal is to deduce the possible topological and azimuth relationships between simple regions A and C.According to Section 2.3, we have(27)R52DOS=Ao∩BoAo∩BcoAco∩BoAco∩Bcos1NEs2ENs3NWs4NWs1ENs2ENs3NWs4NWs5ESs6ESs7WSs8WSs5SEs6SEs7SWs8SW.Using the R53DOS-intersection model, a total of 65 topological and azimuth relationships were obtained from the real world. Hence, it is possible to obtain 65 0-1 matrices of 5 rows and 4 columns, which is denoted as Ω1=Ri;i=1,…,65Ri. Targeting at region A, the topological and directional relationships between A and C and those between B and C were taken into account.Since the topological and azimuth relationships between simple regionsA and B and those between simple regions B and C are known in advance, we have RB,C∈Ω1. Then, the possible topological and orientation relationships between A and C were derived from the R53DOS-intersection model. According to Definition 2, we have(28)εAo∩Bo∩CoεAo∩Bco∩CoεAco∩Bo∩CoεAco∩Bco∩Co∨εAo∩Bo∩CcoεAo∩Bco∩CcoεAco∩Bo∩CcoεACo∩Bco∩Cco,RA,B=εAo∩BoεAo∩BcoεAco∩BoεAoC∩Bco,εAo∩Bo∩CoεAo∩Bo∩CcoεAo∩Bco∩CoεAo∩Bco∩Cco∨εAco∩Bo∩CoεAco∩Bo∩CcoεAco∩Bco∩CoεACo∩Bco∩Cco,RB,C=εBo∩CoεBo∩CcoεBco∩CoεBoC∩Cco.Suppose the real-world 0-1 matrices satisfy(29)M=Mi=1,…,n,Then, all 0-1 matrices must meet:(30)mi=RA,B∨RB,C,i=1,…,n.Hence, the matrix that does not satisfy the condition belongs to the empty set, namely,M∈∅. This shows the topological and directional relationships R (A, B) and R (A, C) cannot be compounded. Then, all 0-1 matrices represented in the R53DOS-intersection model were judged one by one. The duplicates in the set {Mi = 1, …, n} were removed, leaving the possible topological and azimuth relationships between A and C.In theory, there are a total of 65 × 65 = 4,225 topological-azimuth relationshipsR (A, B) and R (B, C). On this basis, the compound relationship reasoning table was set up (Table 4).Table 3
The list of all directional and topological relationships.
Topological relationshipsRegionsDRDRs1NE,DRs2NE,DRs1EN,DRs2EN,DRs5ES,DRs6ES,DRs5SE,DRs6SE,DRs8SW,DRs7SW,DRs8WS,DRs7WS,DRs4WN,DRs3WN,DRs4NW,DRs3NWPOPOs1NE,POs2NE,POs1EN,POs2EN,POs5ES,POs6ES,POs5SE,POs6SE,POs8SW,POs7SW,POs8WS,POs7WS,POs4WN,POs3WN,POs4NW,POs3NWPPPPs1NE,PPs2NE,PPs1EN,PPs2EN,PPs5ES,PPs6ES,PPs5SE,PPs6SE,PPs8SW,PPs7SW,PPs8WS,PPs7WS,PPs4WN,PPs3WN,PPs4NW,PPs3NWEQEqualPPIPPIs1NE,PPIs2NE,PPIs1EN,PPIs2EN,PPIs5ES,PPIs6ES,PPIs5SE,PPIs6SE,PPIs8SW,PPIs7SW,PPIs8WS,PPIs7WS,PPIs4WN,PPIs3WN,PPIs4NW,PPIs3NWTable 4
Compound relationship reasoning table.
R (B, C)R (A, B)R (A, C)DR (B, C)all (A, B)ΦPOall (A, B)DRall (A, C); POall (A, C); PPIall (A, C)PPall (A, B)all (A, C)EQall (A, B)all (A, C)PPIall (A, B)DRall (A, C); POall (A, C); PPIall (A, C)PO (B, C)DRall (A, B)DRall (A, C); POall (A, C); PPall (A, C)POall (A, B)ΦPPall (A, B)DRall (A, C); POall (A, C); PPall (A, C)EQall (A, B)POall (A, C)PPIall (A, B)POall (A, C); PPIall (A, C)PP (B, C)DRall (A, B)DRall (A, C); POall (A, C); PPall (A, C)POall (A, B)POall (A, C); PPall (A, C)PPall (A, B)PPall (A, C)EQall (A, B)PPall (A, C)PPIall (A, B)POall (A, C); EQall (A, C); PPall (A, C); PPIall (A, C)EQ (B, C)DRall (A, B)all (A, C)POall (A, B)POall (A, C)PPall (A, B)PPall (A, C)EQall (A, B)EQall (A, C)PPIall (A, B)PPIall (A, C)PPI (B, C)DRall (A, B)DRall (A, C)POall (A, B)DRall (A, C); POall (A, C); PPIall (A, C)PPall (A, B)ΦEQall (A, B)PPIall (A, C)PPIall (A, B)PPIall (A, C)


## 4. Conclusions

This paper extends the compound directional and topological relationships on the 2D plane to the 3D space and then creates the R53DOS-intersection model. Based on the model, a total of 11,038 directional and topological relationships were calculated. Compared with the MBR model, the proposed model can describe the relationships between simple regions accurately and express the relationships with sufficient clarity. To further improve the model, the future research will consider the impact of simple area boundaries on the model and apply the R5DOS model to the formation control of UAV formations.



---

*Source: 3849053-2020-10-07.xml*