# Spatial Reasoning Based on 3D-ICSRM Model

Authors: Yongshan Liu; Xiang Gong; Dehan Kong
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

The existing spatial relationship composite models have defects in both cognitive habits and differentiation degree when describing the spatial relationship between the three dimensional objects. These defects can cause inaccuracy in the process of spatial reasoning. In order to solve this problem, this paper proposes a Three-Dimensional Improved Composite Spatial Relationship Model (3D-ICSRM). Then a high-precision spatial relationship reasoning algorithm is presented based on this model, which combines qualitative and quantitative analyses. Finally, both the correctness and performance advantages of spatial reasoning algorithm are verified by experiments based on this proposed model.


---

## Body

## 1. Introduction

The representation and reasoning of spatial information is the core of Artificial Intelligence system, Geographic Information System (GIS), and so on [1]. In order to make better use of the spatial information in practice, it is of importance to understand, describe, analyze, and process the spatial relationship accurately [2]. Spatial relationship expression model is the basis of describing and analyzing the spatial relationship between objects in GIS. Single-mode spatial relationship model is lack of the accuracy of describing the relationship between objects and completeness of expressing the spatial information. Therefore, the research of spatial relationship tends to compound model in recent years. At present, there are three limitations in the study of the compound expression model: (1) Cognitive view: although the size of the object itself is considered, there is a big difference between the definition of the direction and the human cognitive habit which leads to serious semantic conflict in the process of spatial relation reasoning [3]. (2) Differentiation degree: the spatial location information is described with low accuracy which can lead to large errors in the calculation processing and obvious limitations in solving complex spatial relationships. (3) Spatial dimension: there are few studies on three-dimensional space due to the fact that the present research mainly focuses on the two-dimensional space. In summary, in small scale three-dimensional space, spatial object is often represented as a point, rather than the influence of the shape and size of the object itself [4]. Therefore, the spatial relation model in this environment has higher requirements in terms of spatial cognition and division. This paper proposes a compound 3D spatial relation model named Three-Dimensional Improved Composite Spatial expression Relationship Model (3D-ICSRM) to solve the problem. Moreover, a new high-precision algorithm of position relation reasoning is presented on the basis of this model. The remainder of the paper is organized as follows: Section 2 reviews related works of spatial relationship. Section 3 proposes the 3D-ICSRM model and evaluates the performance of the model. Section 4 presents a high-precision spatial relation reasoning algorithm based on the description of spatial information. Section 5 provides the reasoning results, verifies the correctness of the composite model and reasoning algorithm, and presents the advantages of the inference algorithm over composite table method by using comparison experiments. Section 6 summarizes the work of this paper and presents an outlook for future works.


## 2. Related Works

At present, the common composite methods of 3D spatial relations are projection-matrix method, direction-topological method, and direction-distance method. In the aspect of projection-matrix method, Chen et al. [5] used the intersection cube matrix to describe the directional relationship in 3D space. Wang et al. [6] represented 3D spatial directional relationship with a 3x9 matrix and gave the corresponding reasoning method. Gu et al. [7] applied the double-projection 3x3 matrix model to describe the directional relationship. Spatial objects were represented by the Minimum Bounding Rect (MBR) in all of the above models as shown in Figure 1(a). Obviously, there is a difference between the definition of direction in these MBR-based models and human cognitive habits. People do not describe North in such a rigid way as MBR-based model does. There are a lot of researches on the combination of direction and topology. Song et al. [8] proposed an effective complex spatial relationship model named TDSC based on the relationship of topology, direction, and size. Li et al. [9] presented a consistency algorithm to deal with the constraints of topological relationship and directional relationship. Salamat et al. [10] proposed a method for reasoning of two dimensional spatial scenes with the Combination of Topological Direction (CTD) to handle the combination of topological and directional relationships. However, these models are still imprecise when describing the qualitative relationship between spatial objects. In the study of the composite model of directional relationship and distance relationship, Liu et al. [11] proposed a combination of directional model and qualitative distance as shown in Figure 1(b). Although this model has some improvement in cognition, it still has some shortcomings as inaccuracy for the division and description of the direction. Li et al. [12] presented 3DR44-4d model by adding distance relationship into 3DR44 model. This model increased the accuracy of the expression. Meanwhile, the division and cognition of spatial directional relationship have not been improved effectively. Wang et al. [13] combined the 8-direction cone model with the distance relationship as shown in Figure 1(c). However, the model can only be applied to 2D spatial objects, and the position information of 3D spatial objects cannot be expressed correctly in these models. These defects affect the accuracy of spatial reasoning results directly. More and more attention has been paid to the processing of complex spatial information [14]. As a result, there is a higher requirement for the three-dimensional spatial relationship model in the aspect of both cognition and accuracy. However, the existing models are deficient. To solve this problem, this paper proposes a three-dimensional improved composite spatial relationship model (3D-ICSRM) and presents a new algorithm for high-precision spatial relation reasoning.Figure 1
Models of spatial direction relations.
(a)
MBR model (b)
8-direction cone model A (c)
8-direction cone model B (d)
16-direction cone model


## 3. 3D-ICSRM Model

The cone model is more suitable for human cognition than other models in the definition of the spatial directional relationship, and it is easy to implement and maintain. The comparison of the three cone models showed in Figures1(b), 1(c), and 1(d) shows that the cone model in Figure 1(c) is better than other models in space division. Therefore, this paper presents 3D-ICSRM based on the model shown in Figure 1(c). The 3D-ICSRM model is shown in Figure 5.Definition 1.
4 Layers. Define 4 layers as Up (Abbreviations:u), MiddleUp (Abbreviations: mu), MiddleDown (Abbreviations: md), and Down (Abbreviations: d), which fits our cognition in verticle.
As Is Shown in Figure2. The space in verticle is divided into 4 layers, which are u, mu, md, and d. Layer u and layer mu are divided by a line which is angled 45 degrees from the x-axis. As the same reason layer md and layer d are divided. There are four objects O1, O2, O3, and O4 in this area, and they are in u, mu, md, and d separately.Figure 2
4 layers.Definition 2.
8 Directional Areas. Define 8 directional areas as North (Abbreviations:N), NorthWest (Abbreviations: NW), West (Abbreviations: W), SouthWest (Abbreviations: SW), South (Abbreviations: S), SouthEast (Abbreviations: SE), East (Abbreviations: E), and NorthEast (Abbreviations: NE), which fits our cognition in horizontal.
As Is Shown in Figure3. The spaces in one level are separated into N, NW, W, SW, S, SE, E, and NE 8 directional areas.Figure 3
8 directional areas.Definition 3.
5 Qualitative Distances. Define 5 qualitative distance areas as veryclose (q0=[0, k1)), close (q1=[ k1, k2)), intermediate (q2=[ k2, k3)), far (q3=[ k3, k4)), and veryfar (q4=[ k4, ∞ )) (k1,k2,k3,k4ϵ (0,∞)), which close to our real life.
For example, when the distance between me and the storm is 0m to 100m, I would say it is very close to me. While when the distance changes to 100m to 500m, I claim it is close to me. More than, 500m to 1000m is intermediate for me. 1000m to 1500m is far for me. As for the distance up to 1500m, it is very far for me. Take this as an example; when I set my qualitative distance, I would setq0=[0,100), q1=[100,500),q2=[500,1000),q3=[1000,1500), and q4=[1500,∞). 5 qualitative distances change with the domain of the observer’s cognition for distance in real. As Is Shown in Figure 4. The distance of one direction is divided into 5 areas, which means veryclose (q0), close (q1), intermediate (q2), far (q3), and veryfar (q4).Figure 4
5 qualitative distances.Figure 5
Improved Composite Spatial Relationship Model of 3D.Definition 4.
3D-ICSRM Model. Based on the above three definitions, in three-dimensional space, with the reference object as the center, three-dimensional space is divided into 4∗ 8 ∗ 5 areas (4 layers combine 8 directional areas and combine 5 qualitative distances). Point O(x,y,z) represents the centroid of a three-dimensional object. And 4 layers combine 8 directional areas; divide the three-dimensional space into 32 areas as follows:(1)Nu,x,yϵ3π8,5π8,zϵ0,π4Nmu,x,yϵ3π8,5π8,zϵπ4,π2Nmd,x,yϵ3π8,5π8,zϵπ2,3π4Nd,x,yϵ3π8,5π8,zϵ3π4,π,NWu,x,yϵ5π8,7π8,zϵ0,π4NWmu,x,yϵ5π8,7π8,zϵπ4,π2NWmd,x,yϵ5π8,7π8,zϵπ2,3π4NWd,x,yϵ5π8,7π8,zϵ3π4,π,Wu,x,yϵ7π8,9π8,zϵ0,π4Wmu,x,yϵ7π8,9π8,zϵπ4,π2Wmd,x,yϵ7π8,9π8,zϵπ2,3π4Wd,x,yϵ7π8,9π8,zϵ3π4,π,SWu,x,yϵ9π8,11π8,zϵ0,π4SWmu,x,yϵ9π8,11π8,zϵπ4,π2SWmd,x,yϵ9π8,11π8,zϵπ2,3π4SWd,x,yϵ9π8,11π8,zϵ3π4,π,Su,x,yϵ11π8,13π8,zϵ0,π4Smu,x,yϵ11π8,13π8,zϵπ4,π2Smd,x,yϵ11π8,13π8,zϵπ2,3π4Sd,x,yϵ11π8,13π8,zϵ3π4,π,SEu,x,yϵ11π8,13π8,zϵ0,π4SEmu,x,yϵ11π8,13π8,zϵπ4,π2SEmd,x,yϵ11π8,13π8,zϵπ2,3π4SEd,x,yϵ11π8,13π8,zϵ3π4,π,NEu,x,yϵπ8,3π8,zϵ0,π4NEmu,x,yϵπ8,3π8,zϵπ4,π2NEmd,x,yϵπ8,3π8,zϵπ2,3π4NEd,x,yϵπ8,3π8,zϵ3π4,π,Eu,x,yϵ15π8,2π,zϵ0,π4Emu,x,yϵ15π8,2π,zϵπ4,π2Emd,x,yϵ15π8,2π,zϵπ2,3π4Ed,x,yϵ15π8,2π,zϵ3π4,π.The 3D-ICRSM model includes 4 layers in vertical. Each level of horizontal is divided into 8 directional areas average. Each part of the 32 separated areas in the three-dimensional space has 5 qualitative distances. Thus through this model, each object’s direction can be described easily. The schematic diagram of the 3D-ICSRM is shown in Figure 5.The distance between the adjacent qualitative areas meets a fixed proportion of k (kϵN+). D3 is used to represent the 32 directional regions around the reference object while d3 is the symbol set of the 5 distance regions. Take the map as an example; the scale is smaller and the content is more detailed. On the contrary, the scope is larger and the content is simple. The 5 evaluation indexes of the model proposed by Goyal are an important basis for evaluating the performance of a spatial relation model [15]. The following is a theoretical analysis of the performance of the model from five aspects: (1) Formal. The directional terminology used by people to communicate with each other may have different meanings for different people, but in GIS it is necessary to have a formal definition of the direction terms, which can be used to formalize the model. The definitions of 3D-ICSRM in both horizontal and vertical direction are more in line with the spatial cognition of human daily habits. Combined with the rigorous qualitative distance of the space division, the formal ability is well. (2) Inferential. The spatial relation model has the ability to infer the unknown spatial relationship from the spatial relations among the known spatial objects and obtain the relationship between other objects. There is an accurate range and range of distances for each spatial region of the 3D-ICSRM model. If there is no coincidence, there will be 25600 kinds of reasoning results. (3) Shape-Sensitive. The result is the same when the model describes objects at different observation scales. Because of the limitation of the cone model in describing spatial relations, the 3D-ICSRM model can only be used to describe and define the spatial relations between three dimensional objects in a small scale environment. (4) Dimension-Neutral. The space object is treated as a point in the cone model, and the shape of the object does not have a great influence on the judgment of the spatial relationship. Therefore, the 3D-ICSRM model does not consider the shape of the reference object. (5) Comparable. Due to the increase of the horizontal and vertical division of the 3D-ICSRM model, there are 160 kinds of position relations that can be distinguished directly.


## 4. Reasoning

### 4.1. Principle of Reasoning Method

Reasoning is deriving unknown directions from the known directions. As shown in Formula (2). The spatial relationship between object A and object C could be inferred by two known directions qidir(A,B) and qjdir(B,C). Here dir(A,B) means the direction of two objects in three-dimensional, directions(A,B) abbreviations: dir(A,B). The symbol ∧ means combine two directions of reasoning. → is a deduced symbol which means one can derive results from combined conditions. dAC means the distance between objects A and C; it represents the abbreviation of distanceAC.(2)qidirA,B∧qjdirB,C→dACdirA,CIn the 3D-ICSRM model and the spherical coordinate system, angleα,β and distance d are used to describe the relationship between the Target Object (TO) and the Reference Object (RO). Angle α represents 8 horizontal regions: N represents (3π/8,5π/8], NW represents (5π/8,7π/8], W represents (7π/8,9π/8], SW represents (9π/8,11π/8], S represents (11π/8,13π/8], SE represents (13π/8,15π/8], NE represents (π/8,3π/8], and E represents (15π/8,2π]. Angle β represents 4 vertical regions: u represents (0,π/4]), mu represents (π/4,π/2]), md represents (π/2,3π/4]), and d represents (3π/4,π]). d represents qualitative distance between the TO and RO. Thus αϵ{N,S,E,W,NE,NW,SE,SW}, βϵ{u, mu, md, d}, and dϵd3. The conversion formula between spherical coordinates and Cartesian coordinates is shown as Formula (3). α,β indicate the angle between the object and the three-dimensional Cartesian axis.(3)x=rsin⁡βcos⁡αy=rsin⁡βsin⁡α,r≥0,βϵ0,π,αϵ0,2πz=rcos⁡βThe coordinate of object A is (xA, yA,zA), and the coordinate of object B is (xB, yB, zB); then the spherical coordinates are shown in Formula (4). dAB means the distance of object A and object B in three-dimensional space. (4)xB-xA=dABsin⁡βAcos⁡αAyB-yA=dABsin⁡βAsin⁡αA,dABϵd,βAϵ0,π,αAϵ0,2πzB-zA=dABcos⁡βASet object C as (xC, yC,zC); then the relationship between C and B meets Formula (5).(5)xC-xB=dBCsin⁡βBcos⁡αByC-yB=dBCsin⁡βBsin⁡αB,dBCϵd,βBϵ0,π,αBϵ0,2πzC-zB=dBCcos⁡βBMeanwhile, the relationship between C and A meets Formula (6).(6)xC-xA=xC-xB+xB-xAyC-yA=yC-yB+yB-yAzC-zA=zC-zB+zB-zASo the reasoning is shown in Formula (7).(7)xC-xA=dABsin⁡βAcos⁡αA+dBCsin⁡βBcos⁡αByC-yA=dABsin⁡βAsin⁡αA+dBCsin⁡βBsin⁡αB,dAB,dBCϵd,βA,βBϵ0,π,αA,αBϵ0,2πzC-zA=dABcos⁡βA+dBCcos⁡βBThe angle αA is included angle between segment AB and line y=yA,z=zA positive while the angle αB is included angle between segment BC and line {x=xB,z=zB} positive. The angle βA is included angle between AB and line {x=xA,y=yA} positive while the angle βB is included angle between BC and line {x=xB,y=yB} positive. For example, when the coordinate of object A is origin, then the line {y=yA,z=zA}. Based on the 3D-ICSRM model, the qualitative distance satisfies the following three limitations: (1) Monotone increasing. q(k1)≤q(k2), ∀k1,k2ϵN+,k1≤k2. (2) The range of a given distance is greater than that of all previous ranges which can be expressed as qi≥Δi-1,i≥1. (3) The absorption rate. Define “>>” as a logical relation, ∀ε>0; if qi/qj≥ε, then qi>>qj. If qi>>qj, then qi±qj≈qi. qj is “absorbed."


### 4.2. The Algorithm of HPSRA

Consider the definition and description of spatial 3D-ICSRM model and spatial relation reasoning principle proposed in the previous section. The reasoning algorithm of HPSRA (High-precision Spatial Reasoning Algorithm) based on 3D-ICSRM is presented (See Algorithm1). The main ideas of the algorithm are as follows: Step1: The establishment of a spatial relationship model. The 3D-ICSRM model is constructed based on the reference object. The space around reference object is divided into 4 levels, each level contains 8 directions, and each direction contains 5 sections of qualitative distance range, as a total of 160 kinds of space area. Step2: Spatial relation reasoning. Based on the 3D-ICSRM model, judge whether there is the phenomenon of “absorption” in the distance relation of known spatial objects. If there is absorption, the position relation of an unknown object is equal to the position relation of the object with a large distance. Otherwise, the reasoning of the location relation of unknown objects in space is deduced based on the reasoning principle proposed in preceding 4.1. Step3: Processing of result sets. According to the definition of the model in Step1, we can judge the locations of all the elements in Step2 and then infer all possible spatial position relationships of the unknown objects according to the region type.Algorithm 1:The algorithm Of HPSRA.
Input: The location relationship between A and B:the distance of A and B (abbreviations:disA,B),the direction of A and B(abbreviations: dirA,B); The location relationship betweenB and C: disB,C, dirB,C Output: The location relationship between A and C: disA,C, dirA,C 1: Create Model 2:ai,ai+1← InitdisA,B(Init means initialize the distance between two objects) 3:aj,aj+1← InitdisB,C 4:αA,βA←dirA,B 5:αB,βB←dirB,C 6: IF(ai+1/aj+1≥k2) 7:disA,C= disA,B and dirA,C= dirA,B 8: ELSE IF(aj+1/ai+1≥k2) 9:disA,C= disB,C and dirA,C= dirB,C 10: ELSE 11:xC,yC,zC←Reason(ai,ai+1,aj,aj+1,αA,βA,αB,βB)(Reason means conduct spatial direction relationship reasoning ) 12:list.add() 13:fori=0;i<list.Count-1;i++do 14:an,an+1,αC,βC←Reason(List(i)) 15:list.add() 16:end for 17:forj=0;j<list.Count-1;j++do 18:disA,C←Caldis(list(j))(Caldis means Calculate the distance) 19:dirA,C←Caldir(list(j))(Caldir means Calculate the dirtional relationship) 20:end for 21: ReturndisA,C, dirA,CIn 1st line, the definition of the 3D-ICSRM model is given. Then the spatial position relation between objectsA and B, B and C is given based on the model. From 6th to 9th lines of code is used to judge whether the known position satisfies the constraint conditions of qualitative distance. The numerical calculation of the relative relation of the implicit object is done from 11th line to 13th line. The calculations of all results angles and distances are done from 13th line to 15th line. Then, the distance relationship is got in 18th line, and directional relationship is calculated in 19th line. Finally, the location relationship of objects A and C is returned in 21st line.The advantages of reasoning algorithm for 3D location relation based on spatial compound expression model are obvious. The model 3D-ICSRM is used to describe the spatial relationships betweenA, B, and C, which are consistent with human cognition and have a high degree of similarity to similar spatial relationships, providing a detailed description of the spatial relationship information and reasoning for the calculation of the premise. Consider the restriction mechanism of spatial relation, calculation principle, and conversion formula, and use quantitative calculation of qualitative distance constraints and 3D object position by way of objects A, C spatial relation reasoning. The reasoning process is a precise numerical calculation. Therefore, the inference results are more accurate with less error. The quantitative calculation results are returned and the spatial region is judged and described based on the 3D-ICSRM model. Finally, the spatial position relationship between A and C is obtained.


## 4.1. Principle of Reasoning Method

Reasoning is deriving unknown directions from the known directions. As shown in Formula (2). The spatial relationship between object A and object C could be inferred by two known directions qidir(A,B) and qjdir(B,C). Here dir(A,B) means the direction of two objects in three-dimensional, directions(A,B) abbreviations: dir(A,B). The symbol ∧ means combine two directions of reasoning. → is a deduced symbol which means one can derive results from combined conditions. dAC means the distance between objects A and C; it represents the abbreviation of distanceAC.(2)qidirA,B∧qjdirB,C→dACdirA,CIn the 3D-ICSRM model and the spherical coordinate system, angleα,β and distance d are used to describe the relationship between the Target Object (TO) and the Reference Object (RO). Angle α represents 8 horizontal regions: N represents (3π/8,5π/8], NW represents (5π/8,7π/8], W represents (7π/8,9π/8], SW represents (9π/8,11π/8], S represents (11π/8,13π/8], SE represents (13π/8,15π/8], NE represents (π/8,3π/8], and E represents (15π/8,2π]. Angle β represents 4 vertical regions: u represents (0,π/4]), mu represents (π/4,π/2]), md represents (π/2,3π/4]), and d represents (3π/4,π]). d represents qualitative distance between the TO and RO. Thus αϵ{N,S,E,W,NE,NW,SE,SW}, βϵ{u, mu, md, d}, and dϵd3. The conversion formula between spherical coordinates and Cartesian coordinates is shown as Formula (3). α,β indicate the angle between the object and the three-dimensional Cartesian axis.(3)x=rsin⁡βcos⁡αy=rsin⁡βsin⁡α,r≥0,βϵ0,π,αϵ0,2πz=rcos⁡βThe coordinate of object A is (xA, yA,zA), and the coordinate of object B is (xB, yB, zB); then the spherical coordinates are shown in Formula (4). dAB means the distance of object A and object B in three-dimensional space. (4)xB-xA=dABsin⁡βAcos⁡αAyB-yA=dABsin⁡βAsin⁡αA,dABϵd,βAϵ0,π,αAϵ0,2πzB-zA=dABcos⁡βASet object C as (xC, yC,zC); then the relationship between C and B meets Formula (5).(5)xC-xB=dBCsin⁡βBcos⁡αByC-yB=dBCsin⁡βBsin⁡αB,dBCϵd,βBϵ0,π,αBϵ0,2πzC-zB=dBCcos⁡βBMeanwhile, the relationship between C and A meets Formula (6).(6)xC-xA=xC-xB+xB-xAyC-yA=yC-yB+yB-yAzC-zA=zC-zB+zB-zASo the reasoning is shown in Formula (7).(7)xC-xA=dABsin⁡βAcos⁡αA+dBCsin⁡βBcos⁡αByC-yA=dABsin⁡βAsin⁡αA+dBCsin⁡βBsin⁡αB,dAB,dBCϵd,βA,βBϵ0,π,αA,αBϵ0,2πzC-zA=dABcos⁡βA+dBCcos⁡βBThe angle αA is included angle between segment AB and line y=yA,z=zA positive while the angle αB is included angle between segment BC and line {x=xB,z=zB} positive. The angle βA is included angle between AB and line {x=xA,y=yA} positive while the angle βB is included angle between BC and line {x=xB,y=yB} positive. For example, when the coordinate of object A is origin, then the line {y=yA,z=zA}. Based on the 3D-ICSRM model, the qualitative distance satisfies the following three limitations: (1) Monotone increasing. q(k1)≤q(k2), ∀k1,k2ϵN+,k1≤k2. (2) The range of a given distance is greater than that of all previous ranges which can be expressed as qi≥Δi-1,i≥1. (3) The absorption rate. Define “>>” as a logical relation, ∀ε>0; if qi/qj≥ε, then qi>>qj. If qi>>qj, then qi±qj≈qi. qj is “absorbed."


## 4.2. The Algorithm of HPSRA

Consider the definition and description of spatial 3D-ICSRM model and spatial relation reasoning principle proposed in the previous section. The reasoning algorithm of HPSRA (High-precision Spatial Reasoning Algorithm) based on 3D-ICSRM is presented (See Algorithm1). The main ideas of the algorithm are as follows: Step1: The establishment of a spatial relationship model. The 3D-ICSRM model is constructed based on the reference object. The space around reference object is divided into 4 levels, each level contains 8 directions, and each direction contains 5 sections of qualitative distance range, as a total of 160 kinds of space area. Step2: Spatial relation reasoning. Based on the 3D-ICSRM model, judge whether there is the phenomenon of “absorption” in the distance relation of known spatial objects. If there is absorption, the position relation of an unknown object is equal to the position relation of the object with a large distance. Otherwise, the reasoning of the location relation of unknown objects in space is deduced based on the reasoning principle proposed in preceding 4.1. Step3: Processing of result sets. According to the definition of the model in Step1, we can judge the locations of all the elements in Step2 and then infer all possible spatial position relationships of the unknown objects according to the region type.Algorithm 1:The algorithm Of HPSRA.
Input: The location relationship between A and B:the distance of A and B (abbreviations:disA,B),the direction of A and B(abbreviations: dirA,B); The location relationship betweenB and C: disB,C, dirB,C Output: The location relationship between A and C: disA,C, dirA,C 1: Create Model 2:ai,ai+1← InitdisA,B(Init means initialize the distance between two objects) 3:aj,aj+1← InitdisB,C 4:αA,βA←dirA,B 5:αB,βB←dirB,C 6: IF(ai+1/aj+1≥k2) 7:disA,C= disA,B and dirA,C= dirA,B 8: ELSE IF(aj+1/ai+1≥k2) 9:disA,C= disB,C and dirA,C= dirB,C 10: ELSE 11:xC,yC,zC←Reason(ai,ai+1,aj,aj+1,αA,βA,αB,βB)(Reason means conduct spatial direction relationship reasoning ) 12:list.add() 13:fori=0;i<list.Count-1;i++do 14:an,an+1,αC,βC←Reason(List(i)) 15:list.add() 16:end for 17:forj=0;j<list.Count-1;j++do 18:disA,C←Caldis(list(j))(Caldis means Calculate the distance) 19:dirA,C←Caldir(list(j))(Caldir means Calculate the dirtional relationship) 20:end for 21: ReturndisA,C, dirA,CIn 1st line, the definition of the 3D-ICSRM model is given. Then the spatial position relation between objectsA and B, B and C is given based on the model. From 6th to 9th lines of code is used to judge whether the known position satisfies the constraint conditions of qualitative distance. The numerical calculation of the relative relation of the implicit object is done from 11th line to 13th line. The calculations of all results angles and distances are done from 13th line to 15th line. Then, the distance relationship is got in 18th line, and directional relationship is calculated in 19th line. Finally, the location relationship of objects A and C is returned in 21st line.The advantages of reasoning algorithm for 3D location relation based on spatial compound expression model are obvious. The model 3D-ICSRM is used to describe the spatial relationships betweenA, B, and C, which are consistent with human cognition and have a high degree of similarity to similar spatial relationships, providing a detailed description of the spatial relationship information and reasoning for the calculation of the premise. Consider the restriction mechanism of spatial relation, calculation principle, and conversion formula, and use quantitative calculation of qualitative distance constraints and 3D object position by way of objects A, C spatial relation reasoning. The reasoning process is a precise numerical calculation. Therefore, the inference results are more accurate with less error. The quantitative calculation results are returned and the spatial region is judged and described based on the 3D-ICSRM model. Finally, the spatial position relationship between A and C is obtained.


## 5. Experimental Results and Analysis

### 5.1. Reasoning Method Verification

The development environment of prototype reasoning system based on compound model is Microsoft Visual Studio 2010 and Matlab R2012a. Whendir(C,B)=qiNu, dir(B,A)=qjEmd, then dir(C,A)= dir(C,B)dir(B,A)=qiNuqjEmd. The result of reasoning is shown in Table 1. Note: NUEMD={Eu, Emd, NEu, NEmu, Emu, NEmd, Nu, Nmu}. NUEMD_NU={Eu, Emu, NEu, NEmu, Nu, Nmu}. NUEMD_EMD={Eu, Emu, Emd,NEmu, NEmd}.Table 1
Reasoning result ofqiNu, qjEmd.
q 0 E m d q 1 E m d q2Emd q 3 E m d q 4 E m d q0Nu q 0 | q 1 q 0 | q 1 | q 2 q 2 E m d q 3 E m d q 4 E m d N U E M D N U E M D _ E M D q1Nu q 0 | q 1 | q 2 q 0 | q 1 | q 2 q 1 | q 2 | q 3 q 3 E m d q 3 E m d N U E M D _ N U N U E M D N U E M D _ N U q2Nu q 2 N u q 1 | q 2 | q 3 q 1 | q 2 | q 3 q 2 | q 3 | q 4 q 4 E m d N U E M D _ N U N U E M D N U E M D _ N U q3Nu q 3 N u q 3 N u q 2 | q 3 | q 4 q 2 | q 3 | q 4 q 3 | q 4 N U E M D _ N U N U E M D N U E M D_EMD q4Nu q 4 N u q 4 N u q 4 N q 3 | q 4 q 3 | q 4 N U E M D _ N U N U E M DAccording to Table1, we can draw the following rules of reasoning results: (1) if i=j, then qiNu∧qjEmd→qi-1/qi/qi+1Eu, Emu, Emd, NEu, NEmu, NEmd,Nu, Nmu. (2) If i=j+1, then qiNu∧qjEmd→qi-1/qi/qi+1Eu, Emu, NEu, NEmu, Nu, Nmu. The reasoning result of Nu and Emd is biased in the direction of Nu. (3) If j=i+1, then qiN∧qjEmd→qj-1/qj/qj+1Eu, Emu, Emd, NEmu, NEmd. The reasoning result of Nu and Emd is biased in the direction of Emd. (4)i-j=2, qiN∧qjEmd→qiNu or qiN,qjEmd→qjEmd. The image simulations of q2Nu and q1Emd reasoning results in different dimensions are shown in Figure 6. Based on the 3D-ICSRM model, there are 160∗160 kinds of combination types in 3D spatial reasoning, which is consistent with the above inference principle. This section does not list one by one.Figure 6
The result of point cloud rabbit registration.
(a)
Reasoning in 3D space (b)
Reasoning in XOY plane (c)
Reasoning in XOZ plane


### 5.2. Comparison and Analysis of Reasoning Methods

In order to analyze the performance of HPSRA clearly, the comparative experiment is given between algorithm HPSRA and the complex tables method based on the 3D-ICSRM. Complex Tables Method (CTM) is a frequently-used method for spatial relation reasoning. The reasoning of positional relation under the CTM is a combination of distance relation and direction relation, which can get the results of valid inference. Tables2, 3, and 4 give the comparisons of the two methods under the conditions i=j, i=j+1, i=j-1 when reasoning qiNu and qjEmd.Table 2
The comparison of different reasoning result (i=j).
Methods i = 0, j=0 i=1,j=1 i = 2, j=2 i = 3, j=3 i = 4,j=4 HPSRA q 0 | q 1 q 0 | q 1 | q 2 q 1 | q 2 | q 3 q 2 | q 3 | q 4 q 3 | q 4 N U E M D N U E M D N U E M D N U E M D NUEMD ComplexTables q 0 | q 1 q 0 | q 1 | q 2 q 0 | q 1 | q 2 | q 3 q 0 | q 1 | q 2 | q 3 | q 4 q0|q1|q2|q3|q4 N U E M D 1 N U E M D 1 N U E M D 1 N U E M D 1 N U E M D 1Table 3
The comparison of different reasoning result (i=j+1).
Methods i=1,j=0 i = 2 , j = 1 i = 3 , j = 2 i = 4 , j = 3 HPSRA q 0 | q 1 | q 2 q 1 | q 2 | q 3 q 2 | q 3 | q 4 q 3 | q 4 N U E M D _ N U N U E M D _ N U N U E M D _ N U N U E M D _ N U ComplexTables q 0 | q 1 | q 2 q 0 | q 1 | q 2 | q 3 q 0 | q 1 | q 2 | q 3 | q 4 q 0 | q 1 | q 2 | q 3 | q 4 N U E M D 1 N U E M D 1 N U E M D 1 N U E M D 1Table 4
The comparison of different reasoning result (j=i+1).
Methods i=0,j=1 i = 1 , j = 2 i = 2 , j = 3 i = 3 , j = 4 HPSRA q 0 | q 1 | q 2 q 1 | q 2 | q 3 q 2 | q 3 | q 4 q 3 | q 4 N U E M D _ E M D N U E M D _ E M D N U E M D _ E M D N U E M D _ E M D ComplexTables q 0 | q 1 | q 2 q 0 | q 1 | q 2 | q 3 q 0 | q 1 | q 2 | q 3 | q 4 q 0 | q 1 | q 2 | q 3 | q 4 N U E M D 1 N U E M D 1 N U E M D 1 N U E M D 1Note:NUEMD1={Nu,Nmu,Nmd,NEu,NEmu, NEmd,Eu,Emu,Emd}. Comparing the results under the conditions i=j, i=j+1, and i=j-1 in Table 2, we can conclude that the HPSRA algorithm has the following advantages compared with the CTM:( 1 ) Higher Accuracy. There are different results in the result of HPSRA algorithm based on the distance between objects. For example, when the distance is equal that i=j, reasoning results for all possible directions, when the distance range is i-j=1, the result of direction relations tends to the side distance range of Nu or Emd. Both the horizontal and vertical directions are satisfied. The fundamental reason is that the HPSRA algorithm takes into account the two constraints in the reasoning process: the distance and the direction. CTM is only a combination of two spatial relations, without considering the interaction between the two spatial relations. Therefore, the HPSRA algorithm is more accurate.Note:NUEMD1={Nu, Nmu,Nmd,NEu, NEmu,NEmd, Eu,Emu, Emd}Note:NUEMD1={Nu, Nmu, Nmd, NEu, NEmu, NEmd, Eu, Emu, Emd}( 2 ) The scope is smaller, and the error is less. From Tables 2, 3, and 4 comparison results can be seen: under the conditions i=j, i=j+1, and i=j-1. The result of HPSRA algorithm about the location of unknown space objects is smaller than the composite tables method. Because of the definition of spatial relations, 3D-ICSRM uses a semiclosed definition such as q2ϵ(k,k2], αAϵ(3π/8,5π/8],βAϵ(0,π/4]. The HPSRA algorithm is used to solve the boundary problem. The boundary generated by the inference process has a clear definition of which spatial relations belong to it. So the result of HPSRA algorithm is smaller with less error.( 3 )Stronger Regularity. The HPSRA algorithm, when i=j, results for qi-1/qi/qi+1NUEMD. When i=j+1, the result of reasoning is qi-1/qi/qi+1NUEMD_NU, and the direction of the direction is biased to the side of Nu. When j=i+1, inference results for qj-1/qj/qj+1NUEMD_NU, and there is a strong regularity in the direction of the deviation of the direction of Emd. CTM results for all the directions. When the distance is greater than q3, it is close to the complete set.


## 5.1. Reasoning Method Verification

The development environment of prototype reasoning system based on compound model is Microsoft Visual Studio 2010 and Matlab R2012a. Whendir(C,B)=qiNu, dir(B,A)=qjEmd, then dir(C,A)= dir(C,B)dir(B,A)=qiNuqjEmd. The result of reasoning is shown in Table 1. Note: NUEMD={Eu, Emd, NEu, NEmu, Emu, NEmd, Nu, Nmu}. NUEMD_NU={Eu, Emu, NEu, NEmu, Nu, Nmu}. NUEMD_EMD={Eu, Emu, Emd,NEmu, NEmd}.Table 1
Reasoning result ofqiNu, qjEmd.
q 0 E m d q 1 E m d q2Emd q 3 E m d q 4 E m d q0Nu q 0 | q 1 q 0 | q 1 | q 2 q 2 E m d q 3 E m d q 4 E m d N U E M D N U E M D _ E M D q1Nu q 0 | q 1 | q 2 q 0 | q 1 | q 2 q 1 | q 2 | q 3 q 3 E m d q 3 E m d N U E M D _ N U N U E M D N U E M D _ N U q2Nu q 2 N u q 1 | q 2 | q 3 q 1 | q 2 | q 3 q 2 | q 3 | q 4 q 4 E m d N U E M D _ N U N U E M D N U E M D _ N U q3Nu q 3 N u q 3 N u q 2 | q 3 | q 4 q 2 | q 3 | q 4 q 3 | q 4 N U E M D _ N U N U E M D N U E M D_EMD q4Nu q 4 N u q 4 N u q 4 N q 3 | q 4 q 3 | q 4 N U E M D _ N U N U E M DAccording to Table1, we can draw the following rules of reasoning results: (1) if i=j, then qiNu∧qjEmd→qi-1/qi/qi+1Eu, Emu, Emd, NEu, NEmu, NEmd,Nu, Nmu. (2) If i=j+1, then qiNu∧qjEmd→qi-1/qi/qi+1Eu, Emu, NEu, NEmu, Nu, Nmu. The reasoning result of Nu and Emd is biased in the direction of Nu. (3) If j=i+1, then qiN∧qjEmd→qj-1/qj/qj+1Eu, Emu, Emd, NEmu, NEmd. The reasoning result of Nu and Emd is biased in the direction of Emd. (4)i-j=2, qiN∧qjEmd→qiNu or qiN,qjEmd→qjEmd. The image simulations of q2Nu and q1Emd reasoning results in different dimensions are shown in Figure 6. Based on the 3D-ICSRM model, there are 160∗160 kinds of combination types in 3D spatial reasoning, which is consistent with the above inference principle. This section does not list one by one.Figure 6
The result of point cloud rabbit registration.
(a)
Reasoning in 3D space (b)
Reasoning in XOY plane (c)
Reasoning in XOZ plane


## 5.2. Comparison and Analysis of Reasoning Methods

In order to analyze the performance of HPSRA clearly, the comparative experiment is given between algorithm HPSRA and the complex tables method based on the 3D-ICSRM. Complex Tables Method (CTM) is a frequently-used method for spatial relation reasoning. The reasoning of positional relation under the CTM is a combination of distance relation and direction relation, which can get the results of valid inference. Tables2, 3, and 4 give the comparisons of the two methods under the conditions i=j, i=j+1, i=j-1 when reasoning qiNu and qjEmd.Table 2
The comparison of different reasoning result (i=j).
Methods i = 0, j=0 i=1,j=1 i = 2, j=2 i = 3, j=3 i = 4,j=4 HPSRA q 0 | q 1 q 0 | q 1 | q 2 q 1 | q 2 | q 3 q 2 | q 3 | q 4 q 3 | q 4 N U E M D N U E M D N U E M D N U E M D NUEMD ComplexTables q 0 | q 1 q 0 | q 1 | q 2 q 0 | q 1 | q 2 | q 3 q 0 | q 1 | q 2 | q 3 | q 4 q0|q1|q2|q3|q4 N U E M D 1 N U E M D 1 N U E M D 1 N U E M D 1 N U E M D 1Table 3
The comparison of different reasoning result (i=j+1).
Methods i=1,j=0 i = 2 , j = 1 i = 3 , j = 2 i = 4 , j = 3 HPSRA q 0 | q 1 | q 2 q 1 | q 2 | q 3 q 2 | q 3 | q 4 q 3 | q 4 N U E M D _ N U N U E M D _ N U N U E M D _ N U N U E M D _ N U ComplexTables q 0 | q 1 | q 2 q 0 | q 1 | q 2 | q 3 q 0 | q 1 | q 2 | q 3 | q 4 q 0 | q 1 | q 2 | q 3 | q 4 N U E M D 1 N U E M D 1 N U E M D 1 N U E M D 1Table 4
The comparison of different reasoning result (j=i+1).
Methods i=0,j=1 i = 1 , j = 2 i = 2 , j = 3 i = 3 , j = 4 HPSRA q 0 | q 1 | q 2 q 1 | q 2 | q 3 q 2 | q 3 | q 4 q 3 | q 4 N U E M D _ E M D N U E M D _ E M D N U E M D _ E M D N U E M D _ E M D ComplexTables q 0 | q 1 | q 2 q 0 | q 1 | q 2 | q 3 q 0 | q 1 | q 2 | q 3 | q 4 q 0 | q 1 | q 2 | q 3 | q 4 N U E M D 1 N U E M D 1 N U E M D 1 N U E M D 1Note:NUEMD1={Nu,Nmu,Nmd,NEu,NEmu, NEmd,Eu,Emu,Emd}. Comparing the results under the conditions i=j, i=j+1, and i=j-1 in Table 2, we can conclude that the HPSRA algorithm has the following advantages compared with the CTM:( 1 ) Higher Accuracy. There are different results in the result of HPSRA algorithm based on the distance between objects. For example, when the distance is equal that i=j, reasoning results for all possible directions, when the distance range is i-j=1, the result of direction relations tends to the side distance range of Nu or Emd. Both the horizontal and vertical directions are satisfied. The fundamental reason is that the HPSRA algorithm takes into account the two constraints in the reasoning process: the distance and the direction. CTM is only a combination of two spatial relations, without considering the interaction between the two spatial relations. Therefore, the HPSRA algorithm is more accurate.Note:NUEMD1={Nu, Nmu,Nmd,NEu, NEmu,NEmd, Eu,Emu, Emd}Note:NUEMD1={Nu, Nmu, Nmd, NEu, NEmu, NEmd, Eu, Emu, Emd}( 2 ) The scope is smaller, and the error is less. From Tables 2, 3, and 4 comparison results can be seen: under the conditions i=j, i=j+1, and i=j-1. The result of HPSRA algorithm about the location of unknown space objects is smaller than the composite tables method. Because of the definition of spatial relations, 3D-ICSRM uses a semiclosed definition such as q2ϵ(k,k2], αAϵ(3π/8,5π/8],βAϵ(0,π/4]. The HPSRA algorithm is used to solve the boundary problem. The boundary generated by the inference process has a clear definition of which spatial relations belong to it. So the result of HPSRA algorithm is smaller with less error.( 3 )Stronger Regularity. The HPSRA algorithm, when i=j, results for qi-1/qi/qi+1NUEMD. When i=j+1, the result of reasoning is qi-1/qi/qi+1NUEMD_NU, and the direction of the direction is biased to the side of Nu. When j=i+1, inference results for qj-1/qj/qj+1NUEMD_NU, and there is a strong regularity in the direction of the deviation of the direction of Emd. CTM results for all the directions. When the distance is greater than q3, it is close to the complete set.


## 6. Conclusion

In this paper, aiming at the shortcomings of the existing 3D spatial compound expression model in the accurate description of position information and the practical application, a new model 3D-ICSRM of three-dimensional spatial relations is proposed, which is consistent with human cognitive habits and spatial division. Based on the compound expression model, the method of qualitative description and quantitative reasoning of HPSRA is given. This paper presents a kind of high precision spatial reasoning algorithm based on the mutual restriction mechanism of different spatial relations, the principle of 3D coordinate transformation, and the formula of calculation. Finally, based on 3D-ICSRM, the results of HPSRA algorithm and CTM are compared. The results show that the method proposed in this paper has obvious advantages in terms of accuracy, range, error, and regularity. The research work in the future will focus on the use of composite model 3D-ICSRM combined with spatial index technology for three-dimensional spatial data query.



---

*Source: 2892545-2019-07-18.xml*