Local coordinates based on the Voronoi diagram were introduced in
[Sibso80], and they have not been extended to generalized Voronoi diagrams
up to now except in [Anton98]. Local coordinates based on the Voronoi diagram have been
used in natural neighbour interpolation [Sibso81] (also studied in [Gold94] as
stolen area interpolation), to quantify the ``neighbourliness'' of
data sites. The properties of these local coordinates have been extensively
studied in [Farin90] and Piper [Piper93], who gave a formula for the gradient of the
volume stolen from neighbouring Voronoi regions due to the insertion
of a query point, obtained from two directional derivatives. The
natural neighbour or stolen area
interpolation technique has been
extended from ordinary Voronoi diagrams to Voronoi diagrams for sets
of points and line segments in [Anton98]. Anton et
al. [Anton98] extended
the results presented in Gold and Roos [Gold94], by providing
direct vectorial
formulas for the first order and second order derivatives for the
stolen area. The analysis presented in [Anton98] generalizes
the analysis
of Piper [Piper93] based on the formalism of partial derivatives, to the
formalism of derivatives of a function on a normed space.
Even though the Voronoi diagram for a set of points and oriented line segments has
never been defined formally (i.e. the meaning of oriented line segments), it has been used in Gold [Gold94]. The objects in this generalized
Voronoi diagram are either points or pairs of oriented line segments
(see section 2.7.2 in [Berge77a] and section 8.6.1 in [Berge77b] for the definition of
oriented lines).
The representation of line segments in Digital Terrain Modelling (DTM)
has been traditionnally done using constrained Delaunay triangulations
(see [Jones98,Fares95,Ding95,Li99]). In all these DTMs, the line segments were represented as
constrained edges in the Delaunay triangulation (dual of the ordinary
Voronoi diagram for a set of points), but their elevation could not be
taken into account for the interpolation, because the only objects
that had elevations were points (the end points of the line segments).
This research brings novelty in the modelisation of topographic artifacts
represented by line segments (e.g. thalwegs, crests, faults), because
in this interpolation technique, line segments are data objects that
have an elevation (in fact an elevation for each oriented line segment).
We extended the stolen area interpolation technique from the ordinary Voronoi diagram to the Voronoi diagram for a set of points and line segments. We extended their results [Sibso81,Sibso80] by providing direct vectorial formulas for the first order and second order derivatives for the stolen area. In this research work, we present the application of this extended natural neighbour interpolation to topographic modelling. In our case, the interpolant is the elevation. In spatial interpolation, local techniques have been used in order to get an interpolation continuous 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. We show an example of use of this extended interpolation technique for the modelling of linear vertical faults, dams or bridges.