Antonio Ruiz 
occupation was close to 0.4 times the leaf capacity (figure 3), independently of the chosen threshold value(Ruiz et 3] 
1995). 
  
0.6 r 
Average occupation (points/leaf capacity ) 
  
  
X 1 L 1 il A 1 E 1 1 Li 
1 10 100 1000 10000 
Number of points 
  
Figure 3: Average occupation versus number of points in the quadtree for different leaf capacities: 4, 16, 64, 256 and 
1024 points 
We need variable length lists to store the vertices in a leaf. Nelson and Samet (Nelson and Samet, 1986) found that the 
average occupation would be a half of the threshold value. They described the effects of aging and phasing of the leaves. 
Aging means that the older leaves use to hold a larger amount of points than younger ones. Phasing appears when points 
belonging to a uniform data distribution are inserted. 
33 Algorithms for the CDT computation 
Bernal presented algorithms for the incremental construction of the CDT (Bernal, 1988). 
The algorithms we have programmed are those published by de Floriani and Puppo for a triangulation represented in 
DCEL structure ((de Floriani and Puppo, 1992)). We only have changed the criterion to retriangulate the polygons Q that 
appear when a required edge / is inserted in the triangulation and the crossing edges are removed. 
Figure 4: Retriangulation of Q after insertion of required edge / 
De Floriani and Puppo chose the vertex closer to / to build the first triangle joining / origin O and destination D. We have 
changed this criteria and choose the vertex P whose subtended angle ( )PD is larger. By the definition of CDT the vertex 
we choose is more appropriate than the vertex closer to /. Our vertex can be further from / but no other vertex P' will lay 
in the circumcircle of (O, P, D) to this side of the required edge / or otherwise the angle OPD cannot be maximal. The 
search for the maximum angle can be done without computing trigonometric functions. Instead of searching for max(a) 
we look for max( f (o)) which is equivalent in the interval o € [0, 7) 
fo) { sin“ a if cosa > 0 () 
. €9 . 
2 — sin“ a otherwise 
and sina is found by vector product computations. 
  
788 International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 
  
  
34 
Durii 
accul 
a pol 
case, 
The « 
its th 
four | 
sign « 
We d 
close 
numb 
error. 
35 
We hi 
ated n 
edge, 
right 
the ne 
that a 
interic 
one ac 
of its | 
by coi 
been 1 
With 
the po 
triang 
edge | 
height 
for the 
and th 
We ca 
the ki 
also tl 
the su 
triangi 
In this 
Them 
belons 
Stored 
the TI 
—