92 
Fig. 9- Example of a point-quadtree space partition 
2.3 R-tree 
The organization of the data by the R-tree rules is used to 
store rectangular regions of a map or features MBR 
(minimum bounding rectangle) in case of vector 
description of geographic objects; this system is 
particularly used when big amount of data are stored, 
because it allows to less disk accesses than other 
structures. 
An integer number K (order of the tree) is associated to 
each node. Each non-leaf node contains at least K! 2 and 
at most K rectangles (the unique possible exception is the 
root); therefore each branch can be at most half empty, in 
this way the eventuality of cases of empty branches of the 
tree is avoided. Each disk access returns a page 
containing different rectangles; the height of the tree 
results therefore smaller than the previous methods. 
The data we have could be rectangles groups 
(corresponding to the tree nodes) or single rectangles 
(corresponding to the tree leaves). The R-tree record 
structure is shown in Fig. 10. 
typedef struct 
{ 
rectangle_type REC_1, REC_2,..., REC_K; 
node P_1, P_2,..., P_K; 
} node; 
Fig. 10 - Structure of a R-tree record 
The rectangie_type field depends on the representation 
type that has been selected for the data. 
When we want to insert a new rectangle, it has to be 
inserted in the node involving the smallest group area 
extension; If the group has already reached the K limit of 
leaves, we add a level to the tree decomposing the group 
in other subgroups. 
As an example of insertion, we suppose to have a 3 order 
R-tree. in which the data shown in Table 2. 
GROUP I AREAS 
G1 
A1. A2 
G2 
A3. A4, AS 
Table 2 - Groups and areas considered in the example 
If we want to insert two new areas, for instance the areas 
A6 and A7, represented in Fig. 11 in reverse, we have 
that the A6 can be added without problems to the group 
G1, but A7 can not be added to the group G2, as it is 
already full. 
Fig. 11- The new areas A6 and A7 to be added 
Because it is not possible to create a new group only with 
A7 inside (each tree node must contain at least 2 leaves), 
a new group G3 containing A7 and A5 has been built (see 
Fig. 12). ■ 
Fig-12 - The procedure to insert the new areas A6 and A7 
3. SPA 
In the fii 
amount 
only the 
shape. I 
called si 
regular p 
By def 
transforr 
finite set 
Usually ’ 
which r 
example 
resolutio 
represer 
As an e> 
data gee 
represer 
data strt 
object a 
impossit 
all the p 
an infini 
which is 
sense tf 
look to a 
complet« 
1 
3 
0 
2 
5 
7 
4 
6 
1 
3 
0 
2 
Fig. 13- 
resolutio