These local coordinates are defined as follows: uy (M zx
An (M) sre / iq are: ^ > 1 srsecti ^ 1
FE where A; (M) is the area of the intersection (region
marked as V on Figure 2) of the “old” tile of Ox and the “new”
tile of M.
+ 3
O4»
e O2
Figure 2: Natural neighbour interpolation
The vectorial expression for the Voronoi vertex (circumcentre) of
Oi, Oj, and M is:
O:;+1 M - OM 2
E EUER EE 41.
— ————
Uiil = Mii+1L +
€ = 7 ^ 4
D idm : OM
where mi,;..1 is the middle point of [O;O;, 1], and n;,;,1 is de-
Quz 0:2
where O_
Our Om $
designates the x coordinate of the object O_ and O_ designates
the y coordinate of the object O_.
fined as follows: n; 11 =
From this expression, we get that the Voronoi vertex is defined,
continuous and differentiable except at data sites, and its deriva-
tive at the point M is:
1M no id
DELTIUM pet teniM
— Ti i+1.
Th rl O; M
Even though, the Voronoi vertex is not continuous at data points,
its continuity can be extended at data points since the limit of the
Voronoi vertex when the interpolation point goes towards a data
point is the point at infinity in the direction of the bisector.
In order to determine A (M), we decompose the corresponding
area in triangles (see Figure 3): v 1,4, Ux i1, Cx, 1 and vy 1,4,
Ck, j; Ch, j41, where C, j is the i'^ Voronoi vertex of VV (Og) in
the counterclockwise orientation from vg _; rug r+: and we get
the following result:
2A. (M) — det (veces vei C)
JE
+ > det (ires Cuni)
$51
Therefore, the local coordinates are defined, continuous, and dif-
ferentiable everywhere except at data sites, and we get:
— Tum
2DA, (M) — det ( auci C viai) +
——
det (aue UK Kk ) .
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXX V, Part B3. Istanbul 2004
Figure 3: Decomposition into triangles
Even though, the local coordinates are not continuous at data
points, their continuity can be extended at data points since the
limit of the local coordinate when the interpolation point goes
towards a data point is 1.
By the chain rule (see (Cartan, 1967)) DA, (M)SVA, (M)-dM,
we get the direct formula for the gradient of the area stolen to Oy,
by M.
We extend the local coordinates to line segments, by considering
that in the computation of the area stolen by M, we integrate
the areas stolen by M, to each portion of length dA of the line
segment.
* » Os
4
\ ; 04e
X v5 va
\ Vs {Vas vas
*
rct V;
m = M
vi V v5 Os»
\
+ \ ‘vi
\
e À e O2
i
À
\
\
\
1
\
$
Figure 4: The area stolen to an oriented line segment
The circumcircle corresponding to M, P; and P;,, (two points
on the line O;, separated by dA) is: 1; ;41 = P; 4 LAL BM 5 |
P,M Ti where 7 is a unit vector orthogonal to Oy, and directed
from O;, towards M. Its derivative at M is: Div; iii (M) =
dM-w; i41 M
TPM : : à
on the nature (i.e. point or oriented line segment) of the objects
Ox—; and Ok. For neighbouring objects that are points, we
get:
7. The formula for the area stolen by M depends
Ak OM) =
cde "
e RT CER Sfar vas 31^c,
^ (PoOr—1 ; PyO, 1) ~ 22 (7. PoOr_ 1) x | kd
o
A UK 1,k
ZA OP AS it ay 31
ee (A (PM - Fg) — 22 (7. Padi) + A) LI
27 - Po M | (Fo oM) ( ES
Api be
Aa SS o AL A3 ]^vy pa]
pr ^ 009KR+1 PoOr+1) um (1 : PoOR+1) + à :
27 PHOR+1 S eni
1 RSS PES 2f m A3 ok kei
~ ole A (PoM - PoM) — 22 (7 - RAM) + A debile
277 - Pg M :
^11
Internat
In order
cates an
(i.e. Del
segment
given pc
vertex (
If this is
points, «
vation a
In the s
take bot
tions at
is not tl
respond
point w
triangul
launay |
(Guibas
lation a
and vis
rithm te
terpolat
the inte
Stolfi, 1
of safe
safe, th
the clo
(Guiba:
nation |
tion (th
1985))
algoritl
order, :
the cou
by the
circula
Once t
by the
terpola
of inte
bours |
dividec
of the
Edge «
n is th
O (log
In Fig
natura
a set €
discon
faults
elling
on the
ented
functi:
surfac
polati
on th
u, (A
altime
of the
