3D Alpha Shapes

Alpha shapes definition is based on an underlying triangulation that may be a Delaunay triangulation in case of basic alpha shapes or a regular triangulation (cf. ) in case of weighted alpha shapes.

Let us consider the basic case with a Delaunay triangulation.
We first define the alpha complex of the set of points $$*S*.
The alpha complex is a subcomplex
of the Delaunay triangulation.
For a given value of $$, the alpha complex includes
all the simplices in the Delaunay triangulation which have
an empty circumsphere with squared radius equal or smaller than $$.
Here ``empty'' means that the open sphere
do not include any points of $$*S*.
The alpha shape is then simply the domain covered by the simplices
of the alpha complex (see [EM94]).

In general, an alpha complex is a non-connected and non-pure complex.
This means in particular that the alpha complex may have
singular faces. For $$*0 k d-1*,
a $$*k*-simplex of the alpha complex is said to be
singular if it is not a facet of a $$*(k+1)*-simplex of the complex
CGAL provides two versions of the alpha shapes. In the general mode,
the alpha shapes correspond strictly to the above definition.
The regularized mode provides a regularized version of the alpha shapes
corresponding to the domain covered by a regularized version
of the alpha complex where singular faces are removed.

The alpha shapes of a set of points
$$*S* form a discrete family, even though they
are defined for all real numbers $$.
The entire family of alpha shapes can be represented
through the underlying triangulation of $$*S*. In this representation
each $$*k*-simplex of the underlying triangulation is associated with an
interval that specifies for which values of $$ the $$*k*-simplex
belongs to the alpha complex. Relying on this fact, the family of
alpha shapes can be computed efficiently and relatively
easily. Furthermore, we can select the optimal value
of $$ to get an alpha shape including all data points
and having less than a given number of connected components.

The definition is analog in the case of weigthed alpha shapes.
The input set is now a set of weighted points (which can be regarded
as spheres) and the underlying triangulation
is the regular triangulation of this set.
Two spheres, or two weighted points , with centers $$*C _{1}, C_{2}*
and radii $$

*AlphaShapeTraits_3*

*WeightedAlphaShapeTraits_3*

*AlphaShapeCell_3*

*AlphaShapeVertex_3*

Next chapter: 2D Segment Voronoi Diagrams

The CGAL Project .
Tue, December 21, 2004 .