$ 
onol 
ond 
ugh 
and 
ther 
ring 
ique 
this 
'elty 
pour 
nted 
ram 
tion 
| for 
ein 
ling 
nay 
)95, 
line 
nay 
tof 
the 
vere 
ngs 
| by 
in- 
> an 
ola- 
noi 
rect 
ves 
iral 
15€, 
of 
the interpolant is the elevation. In spatial interpolation, local 
techniques have been used in order to get an interpolation con- 
tinuous at data points, and smooth around data points. In these 
local techniques, the data points which influence the interpolant 
are the ones neighbouring the given interpolation point. 
2 THE VORONOI DIAGRAM FOR A SET OF POINTS 
AND ORIENTED LINE SEGMENTS 
Let us first introduce the definition of the Voronoi diagram for a 
set of sites (i.e. objects or subsets) in the Euclidean affine space 
of dimension n. 
Definition 1. Let O be a set of sites in Euclidean affine space of 
dimension n. For each site o of O, the Voronoi cell V (0) of o is 
the set of points that are closer to o than to other sites of O. The 
Voronoi diagram V (O) is the space partition induced by Voronoi 
cells. 
Then let us introduce the definition of the Delaunay triangulation 
of a set of sites (or objects) in the Euclidean space of dimension 
n. 
Definition 2. The Delaunay triangulation of Ó is the geometric 
dual of the Voronoi diagram of O: two sites of Ó are linked by 
an edge in the Delaunay triangulation if and only if their cells are 
incident in the Voronoi diagram of O. 
Let us now consider a set of points and line segments 
O-—(0O,,..., O;] in the Euclidean plane. The distance from a 
point M to’ an object ©; is defined as: either 
the Euclidean distance between the two points if the object is a 
point, or (M, O;) :— inf peo, d« (M, P) where d. denotes the 
Euclidean distance between two points, otherwise. The Voronoi 
cell V (O;) of Oj is the set of points that are closer (in the sense 
of the distance between a point and an object defined just above) 
to O; than to other sites O; : j # à of O. An example of Voronoi 
diagram for a set of points and line segments is shown in Figure 
d 
The Voronoi diagram for a set of points and oriented line seg- 
ments is a generalized Voronoi diagram. Let's now introduce 
the definition of a generalized Voronoi diagram (see (Okabe et 
al., 2000)), in order to be able to introduce the definition of the 
Voronoi diagram for a set of points and oriented line segments as 
a generalized Voronoi diagram. 
Let S be the space in which we place ourselves (typically R?). 
We consider a mapping ó : $x O — (0, 11 defined by (p, O;) — 
(p, O;) such that 
1,  ifpisassigned to O; 
ö(p,0i) = { 0, otherwise 
We call ó as defined above an assignment rule. Under an as- 
signment rule ó, we consider the set of points assigned to Oi, 
ie. V (O:) = fíp|ló(p,Oi-li.pec.Si!, and the set of points 
assigned to both O; and O;, with i. xj ie, e(0,0;) — 
Iplé(pQuz(QqQ0;jcipesSi. We. define. »the 
set V(O.S, SV (O1), V (On )} Now, let N°. (np) be the 
open ball with radius € centered at point p. 
We restrict the assignment rule ó to satisfy the two following con- 
ditions: every point in 5S is assigned to at least one element of O 
Le, Vp € S," ó(p,O;) 2 L and the set e(O;. O;) pet- 
tains to the boundary of V (O;), i.e., Ve » 0, Vp € e(Oi, Oj) : 
Ne (p)N[V (O:) \ e (0:, O;)] # 0 and N° (p)N[S \ V (O:)] # 
0. A set V (O, 0, S) such that the assignment rule ó satisfies the 
two preceeding conditions is a tessellation. Indeed, the first con- 
dition implies that the elements in Y (O, 9, S) are collectively 
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004 
MIS 
N 
  
A“ 
M e 
NC gd 
> ex 
x ee Co 
\ = A | ; 2 
X s N NE ! 2 rd 
UN 77 
\ e f 
\ NN y 
= / i 
X47 ; 
/ / Hm 
% / / ecu 
X lo 7 T | 
> 
Figure 1: The Voronoi diagram of a set of points and line seg- 
ments 
exhaustive ie. | Y (0,3 — 5. 
The definitions of V (O;) and of e (O;, O;) together with the sec- 
ond condition imply that the elements in Y (O, à, S) are mutually 
exclusive except for boundaries i.e., 
[V (O:) NV (0;)] \ e(0:,0;) = 0 foralli z j. We desig- 
nate this tessellation the generalized Voronoi diagram generated 
by the generator set O with assignment rule à in space S, and 
V (O;) the generalized Voronoi region associated with O;. We 
call the assignment rule ó that generates a generalized Voronoi 
diagram, the Voronoi generation assignment rule, or shortly the 
VV —assignment rule. The Voronoi diagram for a set of points 
and oriented line segments in the Euclidean plane is a general- 
ized Voronoi diagram where the space is the Euclidean plane, the 
generator set is comprised of points and/or pairs of oriented line 
segments in the Euclidean plane, and the generator assignement 
rule is as follows. 
If O; is a point, then 
So Oni 1, "dfd(p,O) « d(p, O7); 47 
0, otherwise 
If O; is an oriented line segment, then 
1, ifd(p,O) €d(p,Oj), Vj and 
n. Ou) = p is on the left of or on O; 
0, otherwise 
3 THE NATURAL NEIGHBOUR 
INTERPOLATION 
In this section, we will make a brief introduction to the natural 
neighbour interpolation work developed by Anton et al. (Anton 
et al, 1998). We have a set O = {O1,…, Os} of neighbour- 
ing data objects, at which we know the elevation, and we want 
to interpolate the elevation at some unknown location M in the 
convex hull of O. Ifthe object is a line segment, we know that the 
elevation varies linearly on each oriented line segment. In order 
to interpolate the elevation at M from the values at neighbouring 
data sites, we compute the local coordinates of M.