Journal of Software Engineering and Applications, 2011, 4, 191-194
doi:10.4236/jsea.2011.43022 Published Online March 2011 (http://www.SciRP.org/journal/jsea)
191
A Model of Representing Extension and
Shrinking for Spatial Relations
Shan Zhong1, Junpeng Wan2
1School of Computer Science and Engineering, Changshu Institute of Technology, Changshu, China; 2School of Computer Science
and Telecommunication Engineering, Jiangsu University, Zhenjiang, China.
Received March 8th, 2011; revised March 16th, 2011; accepted March 18th, 2011.
ABSTRACT
Aiming at region connection calculus (RCC) can only roughly represent spatial topological relations, and have diffi-
culty in representin g the distance, direction and so on. Therefore, based on RCC theory, Region Extension and Shrink-
ing Calculus are proposed, and then a formalized metrization method using region as a basic unit is introduced. Based
on RESC theory, taking the advantage su ch as applica tion simplicity and easy realization of g ird area method. The ex-
periment proves the spatial relations can be easily obtained by Grid-Region method, and it is an effective way to repre-
sent spatial relations.
Keywords: RCC, Spatial Extension, Qualitative, Topolog ical
1. Introduction
SR [1] (Spatial Reasoning) is an important subfield of AI
(Artificial Intelligence), usually us ing the technology and
method of AI to model, describe and represent about the
spatial objects. Research in SR is motivated by a wide
variety of possible application areas including GIS (Geo-
graphic Information System), robotic navigation, and high
level vision, spatial propositional semantics of natural
languages, engineering design, and common-sense reas o n -
ing about physical systems.
The qualitative spatial relation s mainly include topolo-
gical, direction and distance relations. The topological re-
lation is the most important basic relation of spatial rela-
tion. The model can be divided to region topology and
point set topology. The direction relation describes the
sequence relation among spatial relations, and its main
describing methods are based on cone and projection.
The distance relation is some metrization relation among
spatial objects. Clementine d ivided the distance to differ-
ent layers such as near, middle and far layers, and com-
bing the cone direction model and distance relation, then
introduced position calculus method.
Spatial reasoning usually needs to combine various
spatial relations, but still so far no unified model can for-
mally describes the topological, directional and the dis-
tance spatial relations based on the same theory.
Based on solving the above problems, a new model
named ESFR for region extension and shrinking is pro-
posed. The model takes advantage of the novel metriza-
tion method to define the topological, directional and the
distance relation. And at the meantime, based on the pro-
perties of easily realization of the grid area method, it is
used to verify the formal model of spatial relations based
on spatial region extension and shrinking.
2. Region Extension and Shrinking
In order to unify the spatial topological, qualitative dis-
tance relation and qualitative direction relation, the spa-
tial representing model is constructed. So the notion of
extension and shrinking of region is defined.
The notion of Region ex tension and shrinking is based
on sum of region (namely sum region). Now, there are a
lot of forms of region [2,4]. Tiansi [5] introduced how to
recognize a spatial environment when the spatial rela-
tions are changed . The literature [2] defined the sum of x
and y:




,,,,
s
umxyz wCwzCwxCwy 









 (1)
To generalize the definition, the region x and y are
modified to the sum of some region satisfied with some
condition, the definition of the modified sum region is
defined as follows:

,,sumxywC wyvvC wv  










 (2)

A Model of Representing Extension and Shrinking for Spatial Relations 192
Especially, for the region A and E, if the predicate

x
equals

,,CGxECA x, in which

,CGx E repre- sents x equals E, and then the region satisfied with the predicate

is:
   
,,, ,,,sumCGxEC AxywCwyvCGvEC AxCwv 













 (3)
If the predicate

x equals
 
,,
P
EXx EA, and P is
the partial relations of RCC-8, then the sum region satis- fied predicate

is:
 

   
,,,,, ,sumPEXxEAywCwyvPEXvEACw v 






 






 (4)
2.1. Region Extension
Given the region A and E, then the extending region
from A to E is the sum region satisfied predicate

,,CGx ECA x, namely,

,EXA E, and
  
,,,EXA EsumCGx ECA x, in which A is
the base region, E is the metrization region of A. A is
extended by n from A, denoted by

,EXA E, namely,
  

,,,,
n
EXA EEXEXEXA EEE (5)

0,EXA EA (6)
2.2. Region Shrinking
Given the region A and E, then the shrinking region from
A to E is the sum region satisfied the predicate
 
,,
P
EXxEA, namely,

,SHRA E, namely,
  

,,,SHRA EsumPEXx EA, A is the base re-
gion, E is the metrization region. A is shrinking from A
for n times shrinking, namely

,
n
SHRAE.
  

,,,,
n
SHRA ESHRSHRSHRA EEE (7)

0,SHRAEA (8)
When A and B are fixed, the max value of n in

,
n
SHRAE can be denoted as


_
,
m
SHRMaxA E,
which is the center of A, or the centre region.
Using the region as the spatial primitive, C(x,y) and
congruence relation CG(x,y) as the original spatial rela-
tion, and adding the metrization function of region ex-
tension, the spatial relations such as topology, distance,
direction, position and move can be formalized.
3. Spatial Relation
3.1. Topology Relation
In the model of topology of RCC-8, DC(x, y) represents
x is apart from y. In the application, the apart degree
should be considered. Therefore, based on the region
extension, DC can be separated to,nE
DC .
Definition 5 Apart degree. Given the region A and B,
if there exits a region E and the positive integer n, A is
not connected to B thr ough E by n-1 times extensio n, but
A is connected to B thro ugh E by n times extension, then
the apart agree of A and B can be represented as


,, nE
DCA B, namely, shown as the Equation (9):






,
1
,
,,,,,
nE
nn
DCA B
nEDC EXAEBC EXAEB






 (9)
The predicate


,, nE
DCA B is known as “The apart
degree between A and B is n*E”. The Figure 1 can be
represented the apart degree of A and B is n*E, the sur-
round region of A represented by the n times extension
using as n dashed circle. According the definition 2, the
Equation (10) can be obtained:


,,
,,
nE nE
DCA BDCBA (10)
The predicate of


,, nE
DCA B represented the apart
degree of A and B is measured by n and E, and the gra-
nularity of metrization is depended on E. When E is con-
firmed, the bigger is the variable of n, and the bigger is
the apart degree.
3.2. Direction Relation
A and B is two regions, A. East, A. South, A. West and
A. North is fo ur borde rl ine s o f the region o f region A .
 





1, ,
,,.,, .,,
nS nS
EastABnSSSCETTA EastSBCETTA EastSB


 

 (11)
The other direction relations can be defined as West (A,B), South( A, B ), North(A,B), etc.
   


    
  



1, ,
1, ,
1, ,
,,.,, .,,
,,.,, .,,
,,.,,.,,
nS nS
nS nS
nS nS
WestABnSSSCETTAWest SBCETTAWest SB
SouthA BnSSSCETTASouth SBCETTASouth SB
NorthABnSSSCETTANorthSBCETTANorth SB




 


 


 




(12)

A Model of Representing Extension and Shrinking for Spatial Relations 193
Figure 1. Apart degree.
For example, when the region calculus is got on the
object B, and the extending region

,ETTB S from B
is firstly intersection with A. East, so we say the object B
is in the east of object A is shown as East(B,A), and the
Figure 2 is showed as follows:
4. Grid Region Method
Grid region method has th e properties of easy application
and realization. If some part of A accounts for some grid,
then all the grids accounting the region can be represen-
ted as the predicate S(A). The grid region is extended
based on the RESC theory, using the grid unit as the me-
trization region, and the metrization region can be ex-
tended as Figure 3.
The algorism for grid region extension is as follows:
1) Choose the region need to be extended
2) Read the region grid coordinate of the selective re-
gion
3) According to the mark of the read grid unit, justify
whether the grid unit is the outer grid unit, if it is the
outer grid unit, then executing (4). If it not the outer grid
unit, then execute (5).
4) Extension according to the coordinate obtained
from (3). Firstly, fetch three grid units such as the top left,
top, top right corners, and justify whether the mark is the
free grid unit. If it is the free grid unit, change the value
of the mark (the counts of the extension). After that,
fetch the right bottom corner, bottom and the left bottom
corners to do the same justify. Finally, fetch the left and
right grid unit to do the same justify. After the justifica-
tion is finished, execute (3).
5) Go on read the grid coordinate of the next region,
execute (3).
5. Application Instance
Based on the introduction of the above RESC, grid re-
gion method realizes qualitative spatial representing sys-
tem.
Figure 2. Direction representing.
Figure 3. Grid region extension.
Figure 4. Application instance.
The system has three modules such as topology rela-
tion reasoning module, direction relation module, dis-
tance relation module. The space is firstly grid, then giv-
en the region 1 and 2, and the given region is grid, the
grid unit is as the extending region to extend the region
S(1), according RESC theory, the topology relation of
S(1) and S(2) is shown as apart (DC), and the apart de-
gree is 3 grid degree, direction relation is S(2) is in the
north of S(1), the distance relation is the absolute dis-
tance between A and B is 3 grid unit distance, namely,
the distance relation is

3,1, 2 s
Dist ,in which S is the
grid unit, the distance between them is 3 grid unit, the
direction relation is South(1,2),namely, the region 2 is in
the south of the region 1, which is showed as Figure 4.

A Model of Representing Extension and Shrinking for Spatial Relations 194
REFERENCES
[1] TBITTNER, B. Smith, “Granular Spatio-Temporal On-
tologies,” AAA I Spring Symposium on, Foundations and
Applications of Spatio-Temporal Reasoning (FASTR),
AAA I Press, MenloPark, 2003, pp. 12217.
[2] D. Randell, Z. Cui and A. G. Cohn, “A Spatial Logic
Based on Regions and Connection,” Proceedings of the
3rd International Conference on Knowledge Representa-
tion and Reasoning, Morgan Kaufmann, 1992, pp.
165-176.
[3] A. G. Cohn, B. Bennett, J. Gooday and N. M. Gotts,
“Qualitative Spatial Representation and Reasoning with
the Region Connection Calculus,” GeoInformatica, Vol. 1,
No. 1, 1997. pp. 1- 44.
[4] T. S. Dong, “SNAPVis and SPANVis: Ontologies for Re-
cognizing Variable Vista Spatial Environments,” In
Christian Freksa, et al. Eds., Spatial Cognition IV, LNAI
3343, Springer-Verlag, Berlin Heidelberg, 2005, pp.
344-365
[5] B. Bennett, A. G. Cohn, P. Torrini and S. M. Hazarika,
“A Foundation for Region-Based Qualitative Geometry,”
Proceedings of the 14th European Conference on AI
(ECAI-2000), IOS Press, Berlin, 2000, pp. 204-208.