the i-th bucket:
As for region-shaped objects ,the blocks they over-
lap fall into two classes. The first class of blocks
are completely overlapped by the objects, we call
this class of blocks inner blocks. Another class of
blocks are partly occupied by the objects , we call
them edge blocks. In figure 4, the shaded blocks
are inner blocks. Obviously, there is no need to
subdivide inner blocks further. No feature infor-
mation are needed for inner objects. However, we
have to subdivide edge blocks further. The parti-
tion method of edge blocks and the extraction ap-
proach of feature information of the objects are the
same as that of line-shaped objects.
sso {Gi oss]
| Bk[1]
Bk[i] — | 065 | — Obis [ -d- Obj, ES
Bk[j] — Objs | + Obj, | + .… | obi |A
ui.
Figure 3:The basic structure of Ladex
Figure 4:Inner and edge blocks of a
region-shaped object
3 Operations and Algorithms for Ladex
Insertion, deletion, modification and search are
typical operations for Ladex, each of these opera-
tion can be discussed in three cases: Point case,
line case and region case. Every operation case has
a relevant algorithm.
3. ] Insertion
This operation is to insert a new spatial object's in-
dex information in the Ladex structure. Let M,xN,
be the i-th level partition (i€ {1,2,3}), and a,, b,
are the length and width of the i-th level block re-
spectively.
Point Insertion Algorithm.
Input: Point (x,y) and Spldx.
Output: Spldx with object identifier and feature
information of the point-shaped object inserted.
PII. B,<(y div b;) * M+ (x div aj);
x2;*-x mod a,;
Y2<y mod by;
PI2. B;«-(y;div by) * M;-d- (x, div ay);
X34*-x, mod a;;
ÿ3<=y2 mod b;;
932
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
PI3. B4«ys * az - x3; (A third level block can not
be partitioned further)
PI4. If the identifier of Point (x,y)has been in the
bucket BK [B, ] » then step to PI6,otherwise
allocate a néw node and insert the identifier
and the feature information of Point (x,y) in-
to it;
PIS. Put the new node into the node list in the cor-
responding bucket.BK [B, ] with feature infor-
mation "B,+B;".
PI6. Return.
Line Insertion Algorithm :
Input: Line {(x1>Y,)» (X25Y2)»+ + + » CXhs Ya) } and
Spldx.
Output: Spldx with the index information of the
line-shaped object inserted.
Suppose the points on the inputted line is not dis-
tributed sparsely, i.e. , for Y i€ {1,2,...,n—1},
we have |xi —xu4l&l and |yi—yi4 [<1
LIL i<l1;
LI2. Ifi=n+1,then step to LI5;
LI3. Call the Point Insertion Algorithm with the
parameter Point (x,y);
LI4. iÆi+1,go to step LI2;
LIS. Return.
Region Insertion Algorithm :
Input: Region {(x,,ÿ;) » (X25Y2) 5. «+
Spldx.
Output: Spldx with the index information of the
region-shaped object inserted.
A region can be described by its edge. Suppose the
points on the edge is dense, i. e. , for ViC€ (1,
2,...,n—2}, we have Ixi— Xia I<1 and | Yi Yn
|<1, in addition,x,=x, and yy=y,» it is a closed
edge.
RII. i«1;
RI2. If i=n, then step to RI5;
R13. Call the Point Insertion Algorithm with the
parameter Point (x,y);
RI4. i<i+1, go to step RIZ;
RI5. Compute the set of inner blocks: {Bı,
B;,... ,B4), represented as IN SET ;
RI6. If IN SET =, then go to step RI9;
RIT. Fetch an element B, in IN SET , insert its i-
dentifier and feature information in a new
node, and then put the node in the list relat-
ed to bucket BK[B,];
RI8. IN SET «IN SET — (B) , jump to RI6;
RI9. Return.
3. 2 Deletion
, (x, 22) and
In spatial databases, if an object has been deleted,
its information in spatial index should also be
deleted , so we can keep the consistency between
database and index structure.
Deletion Algorithm :
Suppose the object to be deleted is Obj,» and the
set of first level lattice blocks is B Set(Obj,).
Input: Obj, and SpIdx.
Output: SpIdx.
Dl. Compute the set B Set (Obj, ) ;
D2.
D3.
D4.
Ou!
tha
PR
PR
Lin
Des
line
Inp
siot
Out
sati
LR!
