Alpha-Shapes

Introduction

This chapter presents a framework for alpha shapes. The description is based on the articles [EM94, Ede92]. Alpha shapes are the generalization of the convex hull of a point set. Let $$S be a finite set of points in $$ ^d, $$d = 2,3 and $$ a parameter with $$0 . For $$= , the $$-shape is the convex hull of $$S. As $$ decreases, the $$-shape shrinks and develops cavities, as soon as a sphere of radius $$sqrt() can be put inside. Finally, for $$= 0, the $$-shape is the set $$S itself.

We distinguish two versions of alpha shapes, one is based on the Delaunay triangulation and the other on its generalization, the regular triangulation, replacing the natural distance by the power to weighted points. The metric used determines an underlying triangulation of the alpha shape and thus, the version computed. In one hand, there is the classic alpha shapes (cf. ) associated with the Delaunay triangulations (cf. ), in the other hand, the weighted alpha shapes (cf. ) associated with the regular triangulations (cf. ).

There is a close connection between alpha shapes and the underlying triangulations. More precisely, the $$-complex of $$S is a subcomplex of this triangulation of $$S, containing the $$-exposed $$k-simplices, $$0 k d. A simplex is $$-exposed, if there is an open disk (resp. ball) of radius $$sqrt() through the vertices of the simplex that does not contain any other point of $$S, for the metric used in the computation of the underlying triangulation. The corresponding $$-shape is defined as the underlying interior space of the $$-complex.

In general, an $$-complex is a non-connected and non-pure polytope, it means, that one $$k-simplice, $$0 k d-1 is not necessary adjacent to a $$(k+1)-simplice.

The $$-shapes of $$S form a discrete family, even though they are defined for all real numbers $$ with $$0 . Thus, we can represent the entire family of $$-shapes of $$S by 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 $$-shape. Relying on this result, the family of $$-shapes can be computed efficiently and relatively easily. Furthermore, we can select an appropriate $$-shape from a finite number of different $$-shapes and corresponding $$-values.

Main Application

Alpha shapes can be used for shape reconstruction from a dense unorganized set of data points. Indeed, an $$-shape is demarcated by a frontier, which is a linear approximation of the original contour, under conditions described for the classic version, in [BB97].

Generic Alpha-Shapes of Points in a Plane

• Class declaration of Alpha_shape_2<Dt>.

Implementation

The cross links between the intervals and the $$k-dimensional faces of the triangulation are actually realized using methods in the $$k-dimensional faces themselves. By this way, you can decide if you want to store or re-compute any of these informations.

A.alpha find uses linear search, while A.alpha lower bound and A.alpha upper bound use binary search. A.number solid components performs a graph traversal and takes time linear in the number of faces of the underlying triangulation. A.find optimal alpha uses binary search and takes time $$O( n $$ log$$ n $$ ), where $$n is the number of points.

The Underlying Triangulation

For the Dt class, you have to choose between a Delaunay or a regular triangulation, depending the version of alpha shapes, you want.

The class Dt must be parameterized with a special alpha shape traits class and a simple triangulation data structure, with no more requirements as for a simple triangulation class, but parameterized by a special vertex base class and a special face base class.

The Alpha-Shape Traits Class (Gt)

Requirements for the Alpha-Shape Traits Class

First, this traits class has the same requirements as the triangulation traits class, for the Dt triangulation, you opted. The following requirement catalog lists the primitives that must be defined additionally.

• Class declaration of Gt.

Triangulation Data Structure Class (Tds) for an Alpha-Shape

The underlying triangulation Dt is parameterized with her triangulation data structure class Tds, that has no additional requirements. In fact, the requirements are on the Tds parameters.

She requires to be templated by special Alpha_shape_vertex_base and Alpha_shape_face_base<Df>, to store the alpha values associated. Thus, we need to define the requirements of such Alpha_shape_vertex_base and Alpha_shape_face_base<Df> classes.

Requirements for the Vertex_base Class of an Alpha-Shape

The information about the alpha values associated are accessible by the vertices of the alpha shape. Thus the nested Alpha_shape_vertex_base type of an alpha shape offers additional functionalities to deal with these methods.

This additional functionalities related to the alpha shape are requirements which have to be fulfilled by the base vertex for an alpha shape, in addition to the functionalities required for a simple triangulation vertex. They are listed below as such.

Inherits From

Triangulation_vertex_base

• Class declaration of Alpha_shape_vertex_base.

Requirements for the Face_base Class of an Alpha-Shape

The information about the alpha values, associated to the face herself and the incident edges, are accessible by the faces of the alpha shape. Thus the nested Alpha_shape_face_base<Df> type of an alpha shape offers additional functionalities to deal with these methods.

Df has to be choosed as the face base for the underlying triangulation.

This additional functionalities related to the alpha shape are requirements which have to be fulfilled by the base face for an alpha shape, in addition to the functionalities required by an underlying triangulation face Df. They are listed below as such.

Inherits From

Df

• Class declaration of Alpha_shape_face_base<Df>.

Classic Version of Alpha-Shapes

The Underlying Triangulation : a Delaunay Triangulation

For a simple alpha shape, you have to choose a Delaunay triangulation as underlying triangulation Dt and follow the requirements listed above.

#include <CGAL/Delaunay_triangulation_2.h>

Predefined Geometric Traits Class (Gt)

Of course, CGAL provides a default Alpha_shape_traits class in this case, with an implementation of the appropriate predicate and constructions. The class Alpha_shape_euclidean_traits_2<Rp> simply derived from Triangulation_euclidean_traits_2<Rp>.

#include <CGAL/Alpha_shape_euclidean_traits_2.h>

Predefined Vertex_base Class

CGAL provides a default Vertex_base class for the Alpha Shape. The class Alpha_shape_vertex_base_2<Gt> simply derived from Triangulation_vertex_base_2<Gt>.

#include <CGAL/Alpha_shape_vertex_base_2.h>

Predefined Face_base Class

CGAL provides a default Face_base class for the Alpha Shape. The class Alpha_shape_face_base_2<Gt,Df> simply derived from Df, which can be instantiated with Triangulation_face_base_2<Gt>.

#include <CGAL/Triangulation_face_base_2.h>

#include <CGAL/Alpha_shape_face_base_2.h>

To Do a Classic Alpha-Shape

Example

typedef CGAL::Cartesian<double> Rp;
typedef CGAL::Alpha_shape_euclidean_traits_2<Rp> Gt;
typedef CGAL::Alpha_shape_vertex_base_2<Gt> Vb;
typedef CGAL::Triangulation_face_base_2<Gt> Df;
typedef CGAL::Alpha_shape_face_base_2<Gt,Df> Fb;
typedef CGAL::Triangulation_default_data_structure_2<Gt,Vb,Fb> Tds;
typedef CGAL::Delaunay_triangulation_2<Gt,Tds> Dt;
typedef CGAL::Alpha_shape_2<Dt> Alpha_shape_2;

Weighted Version of Alpha-Shapes

The Underlying Triangulation : a Regular Triangulation

For a weighted alpha shape, you have to choose a regular triangulation as underlying triangulation Dt and follow the requirements listed above.

#include <CGAL/Regular_triangulation_2.h>

Predefined Geometric Traits Class (Gt)

Of course, CGAL provides a default Alpha_shape_traits class in this case, with an implementation of the appropriate predicate and constructions. The class Weighted_alpha_shape_euclidean_traits_2<Rp> simply derived from Regular_triangulation_euclidean_traits_2<Rp>.

#include <CGAL/Weighted_alpha_shape_euclidean_traits_2.h>

Predefined Vertex_base Class

CGAL provides a default Vertex_base class for the Alpha Shape. The class Alpha_shape_vertex_base_2<Gt> simply derived from Triangulation_vertex_base_2<Gt>.

#include <CGAL/Alpha_shape_vertex_base_2.h>

Predefined Face_base Class

CGAL provides a default Face_base class for the Alpha Shape. The class Alpha_shape_face_base_2<Gt,Df> simply derived from Df, which can be instantiated with Regular_triangulation_face_base_2<Gt>.

#include <CGAL/Regular_triangulation_face_base_2.h>

#include <CGAL/Alpha_shape_face_base_2.h>

To Do a Weighted Alpha-Shape

Example

typedef CGAL::Cartesian<double> Rp;
typedef CGAL::Weighted_alpha_shape_euclidean_traits_2<Rp> Gt;
typedef CGAL::Alpha_shape_vertex_base_2<Gt> Vb;
typedef CGAL::Regular_triangulation_face_base_2<Gt> Rf;
typedef CGAL::Alpha_shape_face_base_2<Gt,Rf>  Fb;
typedef CGAL::Triangulation_default_data_structure_2<Gt,Vb,Fb> Tds;
typedef CGAL::Regular_triangulation_2<Gt,Tds> Rt;
typedef CGAL::Alpha_shape_2<Rt> Alpha_shape_2;