is , a node of QO is a structure shown below ;
structure node {
structure node x Son;, x Son», * Sons, * Sons ;
Set—of—Objects S ;
)
Now , a recursive algorithm of creating QO is given
below as the definition of QO.
Algorithm ; CreatQO(R, SO)
Procedure ,
step 1: Get a node as the root of the QO, set every
item of 7 null.
step 2; Let Ri, where? — 1,2,3,4, is the four quad
block of R ; For V o € SO ,if R(o) C Rand R(o) ER,
i = 1,2,3,4, then
r.S = r.S U (o);
step 3: Let S0; — (olo € SO — r. S,R(o) CR},
à = 1,2,3,4; If SO; is not empty , then create QO: =
CreatQO() by recursion, and let r. Son; points to QO; , i =
]1,2.3.4.
2.2 The operation on QO
The inserting, deleting and searching are the main basic
operations on QO . We give the inserting algorithm on
QO below.
INSERTQO( 7,0,R )
Begin
if » NULL
then get a node 7 as the root of QO, and
set all the items in 7 null.
if R(o) C- R
then begin
r. S — r. S |) (o) ;return;
end
Let R; is the ith quad block of R ,
if RO) CR;
then begin
if 7. Som =NULL
then get a node ,and let 7. Son;
points to it.
INSERTQOX( r. Son; ,0,R; ) ;
end ;
End
The deleting and searching algorithm are similar to the
inserting algorithm, so no details are given here.
Using the inserting algorithm, an algorithm of creating
QO with time consumption O(N) can be given.
2.3 QO and position—based queries
(1) To find the objects at a given position (z,y) ; only
check the objects stored at the nodes whose corresponding
84
quad blocks contain the point (z,y) .
(2) To open a window on a image ; if the set of nodes
» Whose corresponding quad blocks intersect with the win-
dow, is { nd; , nd2,. . . nd.) , then only check the objects
stored at all the ancestor nodes of nd; , 4 — 1,... ,m , and
the objects stored at the subtree whose root is nd; .
(3) To find all the objects contained in or intersecting
with a given region; At first , look up all the nodes whose
corresponding quad blocks intersect with the region , then
check the objects on these nodes.
2.4 The organization of objects stored at a node
Because the queries on QO are transferred to search on
some nodes on the tree, so it is necessary to organize the
objects stored at a node in a suitable way . A schema is to
store the objects by a sorted balanced binary tree with the
size of objects as the key. Using this structure can further
confine the searching scope and leads to a higher effec-
tiveness.
$3 The Querying Effectiveness of QO
Using QO, the searching in queries are confined at one
node or some nodes. So, in this section, we will discuss
the effectiveness by analysing the number of objects
Stored at a node or a series of nodes.
To simplify the discuss, we suppose the image corre-
sponding to a region of unit square [0,17], similarly ,
suppose that the total number of objects on the image is 1.
The diameter (or size ) 4(R) of a region R is defined as
d(R) ; max{d(a1 ,%2) |21 5x2 € R).
Suppose the probability density of d(R) is p(x) , where
x E [0/31
3.1 The expected number 5, of objects stored at a node
Suppose that node nd corresponding to a quad block B
with size , the expected number of objects stored at nd is Pm
. We divide pn into two parts, one corresponding to the
objects whose size is larger than 1/2"*! , the other part
corresponding to the else, and we use Pm1s fato represent
them, so , there is pn = pu + Pre
Because
ir“: 77
Pmi x im yz? p(a)da
yy
0
pa <} 7 pe
where 7 (z) is the probability of the objects with size z in-
tersecting with the lines which divide B into four equaling
sub blocks.
Under a model with equaling probability , it is easy to
deduce that 7 (x) << E — a? , So we have
3.2
sect '
spon
Bar
one :
mdm €
and
gm iS
who
ex]x
root
hav
ther
lis