International Archives of the Photogrammetry, Remote Sensing 
Delaunay triangulation) of the set of samples is computed using e , X 
an incremental algorithm based on the Quad-Edge data structure Liu did 
(see (Guibas and Stolfi, 1985) for an introduction to the Quad- j 
Edge data structure and the algorithms for the construction of the 2 
Voronoi diagram based on this data structure). 
o 
5 NATURAL NEIGHBOUR INTERPOLATION 3 
In this section we will make a brief introduction to the work 
for natural neighbour interpolation presented by Gold and Roos e / : 
(Gold and Roos, 1994). Consider a set of points 
Os Bis vi so Pak f | 
Consider what would be the Voronoi diagram V D(SU (x) after 0 \ 
the insertion of another point x € R? . The goal is to compute Toma 4 
the areas that x would steal to its neighbours if it was inserted in T 
the Voronoi diagram without actually inserting x 1n the Voronot 
diagram. 
a 
The Voronoi diagram of points in the plane forms a network of 
vertices and edges. The vertices are the points that have at least p ; 
three nearest neighbours while the edges are the loci of points es 
having at least two closest neighbours. 
j / 
o / -. / 
ey x i 2 
Let vi i+1(x) denote the Voronoi vertex whose nearest neigh- j ~~. 
bours are Pi, Pit: and x. Since Pj and Pj4,; are two nearest 
, + + 
neighbours of zx, 
it is clear that v; í41(x) lies on the bisector / 
D, i41 of the points P; and P. 
Bion : 
TI dl: 
PP. ve ; 
——— and 
Nii41 += 
\ : rd 3 | o 
Pia a e VO A 
( 3 BR TP. ra ” 
r= Pra 
o 
We can construct the parametric representation of the bisector 
(Gold and Roos, 1994) and we can compute the position of the 
Voronoi point vi,i+1 (7): 
[x he Piae € P. 
20s 1 Tix — Pj 
vVidai(T) = Mist + T il. 
Each site P; has a given height Ni. 
The height of the inserted 2 j t 
point x is determined by the weighted area (Gold and Roos, 1994) 
3 
isv(a)Nu(P;)#9 
hr): 
/ ii 
where v(_) denotes the Voronoi zone of . Figures 3, 4 and 5 . f 
show the construction of the Voronoi polygons. Both regions "i A 
v(x) A v(P;) and v(x) are convex and the corners of v(x) are a : 
Voronoi points in V D(S U {x}) and the corners of v(x) Nu(Pi) = 
are Voronoi points in V D(S) or VD(SU {x}). 
The arcas of the Voronoi zones can be computed as sums of tri- 
angles in the following way: let Pi, .... Px denote the Voronoi Se 
neighbours of x in counterclockwise order. The area of v(x) is s 
equal to the sum ofthe areas of the triangles A (x, vi, iai (x). Vig1.i+2(T) 
je: 
  
o 
=— Mii+r + HMi,i41 With ER, uk | 
o 
and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004 
ist 
al; 
Ge 
im 
int 
bo 
uo 
the 
of 
rio 
Th 
ext 
enc 
edg 
Vot 
crit 
edg 
  
The 
edg 
Vor 
do ı 
The 
sal « 
set. 
Vor 
| thei 
We 1 
cach 
and 
skele 
For ¢ 
set a1 
edge 
| In thi 
| 
that © 
Scan 
Thes 
The [ 
1 
area(v(x)) N^ 5 det[vi.i+1(2) — z,Vis1 ic2(0) — x] 
Figure 5: Area stolen by the new point 
| 
ure 
  
  
| 
| The b 
1180