Biomedical Engineering Reference
In-Depth Information
Fig. 3.7
a Initial Voronoï diagram. b Delaunay triangulation. c Natural neighbour circumcircle
<
:
u
10
x
þ
v
10
y
þ
w
10
z
ð
u
10
x
1
þ
v
10
y
1
þ
w
10
z
1
Þ
u
20
x
þ
v
20
y
þ
w
20
z
ð
u
20
x
2
þ
v
20
y
2
þ
w
20
z
2
Þ
.
u
60
x
þ
v
60
y
þ
w
60
z
ð
u
60
x
6
þ
v
60
y
6
þ
w
60
z
6
Þ
ð
3
:
7
Þ
By definition, only the nodes on the perimeter of the obtained final domain, V
0
,
are considered as neighbour nodes, Fig.
3.6
d. The Voronoï cell V
0
is determined as
Fig.
3.6
e indicates. As it is possible to visualize the Voronoï cell V
0
is the ho-
mothetic form of the auxiliary domain V
0
, being
d
0i
¼
d
0i
2
¼
jj
x
0
x
i
jj
ð
3
:
8
Þ
2
A similar procedure is applied in order to obtain the remaining Voronoï cells,
Fig.
3.6
f. The presented procedure can easily be extrapolated to any d-dimensional
Euclidian space
d
.
The Delaunay triangulation is the geometrical dual of the Voronoï diagram and
it is constructed by connecting the nodes whose Voronoï cells have common
boundaries. The duality between the Voronoï diagram and the Delaunay triangu-
lation implies that a Delaunay edge exists between two nodes in the plane if and
only if their Voronoï cells share a common edge. An important property of the
Delaunay triangles is the ''empty circumcircle criterion [
17
]. If a set of nodes
N
t
¼
f
n
j
n
k
n
l
g2
N forms a Delaunay triangle then the circumcircle formed by the
triangle N
t
contains no other nodes of the global nodal set N. In the context of the
natural neighbour interpolation these circles are known as ''natural neighbour
circumcircles'' [
18
]. The centre of the natural neighbour circumcircle is the vertex
of the respective Voronoï cell. These features are presented in Fig.
3.7
.
In the NNRPIM the Voronoï diagram is used to create the ''influence-cells'',
which enforce the connectivity between the nodes discretizing the problem
domain, N. On the other hand the duality between the Voronoï cells and the
Delaunay triangles is used in order to construct a nodal dependent background
integration mesh.
R
