Biomedical Engineering Reference
In-Depth Information
Tabl e 1. 1
Duality between the
k
-simplices of the 3D Delaunay triangulation and the Voronoı
faces of dimension
3
− k
k
=0
Delaunay vertex
Vorono¨ıregion
Delaunay edge
Voronoı facet
k
=1
Delaunay triangle
Voronoı edge
k
=2
Delaunay tetrahedron
Vorono¨ıvertex
k
=3
a
b
c
a
4
a
4
a
4
a
5
a
5
a
5
t
1
a
3
a
3
a
7
a
3
t
1
a
7
a
7
a
6
a
6
a
t
2
6
t
2
a
2
a
1
a
2
a
2
a
1
a
1
Fig. 1.3
A fictitious 2D molecule with seven atoms. (
a
) The Voronoı diagram in
dashed-lines
and the dual Delaunay triangulation in
solid lines
. Note that the Delaunay triangulation contains
simplices of dimension zero (
points
), one (
line-segments
), and two (
grey triangles
). (
b
) The space-
filling diagram
F
is the region delimited by the two
blue curves
,andthe
α
-complex
K
α
contains
seven vertices, nine line-segments and two triangles. The restriction of the atom centered at
a
2
is
presented in
red
.(
c
) The same molecule whose atoms have been grown. Note that the
α
-complex
now contains all the triangles of the Delaunay triangulation, and that the void in the middle
vanished
For example, the 3D Delaunay (regular) triangulation of the Computational
Geometry Algorithms Library (CGAL), see
www.cgal.org
, handles about 10
5
points
per second on a desktop computer.
α
-complex: partition of the domain into restrictions.
Since selected Voronoı
regions are unbounded and our focus is on atoms, it is actually beneficial to
consider the
restriction
of an atom to its Voronoı region, that is
R
i
=
B
i
∩
Vo r(
B
i
)
(Fig.
1.3
b). An elementary property stipulates that the volume
F
of the molecule
and its boundary
∂F
decompose into the contributions of restrictions, namely:
F
=
∪
i
(Vo r (
S
i
)
∩ B
i
);
∂F
=
∪
i
(Vo r (
S
i
)
∩ S
i
)
.
(1.3)
In dealing with restrictions, it is convenient to consider balls whose radius is
a function of a scaling parameter, so as to facilitate multiscale studies. For a real
value
α
, define the grown ball
B
i
[
α
] as the ball whose squared radius has been
enlarged by
α
,thatis:
B
i
[
α
]=
B
i
(
a
i
,
r
i
+
α
)
.
(1.4)
Search WWH ::
Custom Search