Alpha shape
Encyclopedia
In computational geometry
, an alpha shape, or α-shape, is a family of piecewise linear simple curves in the Euclidean plane associated with the shape of a finite set of points. They were first defined by . The alpha-shape associated with a set of points is a generalization of the concept of the convex hull
, i.e. every convex hull is an alpha-shape but not every alpha shape is a convex hull.
α, define the concept of a generalized disk of radius 1/α as follows:
Then an edge of the alpha-shape is drawn between two members of the finite point set whenever there exists a generalized disk of radius 1/α containing the entire point set and which has the property that the two points lie on its boundary.
If α = 0, then the alpha-shape associated with the finite point set is its ordinary convex hull.
of the point set.
Each edge or triangle of the Delaunay triangulation
may be associated with a characteristic radius, the radius of the smallest empty circle containing the edge or triangle. For each real number
α, the α-complex of the given set of points is the simplicial complex
formed by the set of edges and triangles whose radii are at most 1/α.
The union of the edges and triangles in the α-complex forms a shape closely resembling the α-shape; however it differs in that it has polygonal edges rather than edges formed from arcs of circles. More specifically, showed that the two shapes are homotopy equivalent. (In this later work, Edelsbrunner used the name "α-shape" to refer to the union of the cells in the α-complex, and instead called the related curvilinear shape an α-body.)
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
, an alpha shape, or α-shape, is a family of piecewise linear simple curves in the Euclidean plane associated with the shape of a finite set of points. They were first defined by . The alpha-shape associated with a set of points is a generalization of the concept of the convex hull
Convex hull
In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
, i.e. every convex hull is an alpha-shape but not every alpha shape is a convex hull.
Characterization
For each real numberReal number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
α, define the concept of a generalized disk of radius 1/α as follows:
- If α = 0, it is a closed half-plane;
- If α > 0, it is closed disk of radius 1/α;
- If α < 0, it is the closure of the complement of a disk of radius −1/α.
Then an edge of the alpha-shape is drawn between two members of the finite point set whenever there exists a generalized disk of radius 1/α containing the entire point set and which has the property that the two points lie on its boundary.
If α = 0, then the alpha-shape associated with the finite point set is its ordinary convex hull.
Alpha complex
Alpha shapes are closely related to alpha complexes, subcomplexes of the Delaunay triangulationDelaunay triangulation
In mathematics and computational geometry, a Delaunay triangulation for a set P of points in a plane is a triangulation DT such that no point in P is inside the circumcircle of any triangle in DT. Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the...
of the point set.
Each edge or triangle of the Delaunay triangulation
Delaunay triangulation
In mathematics and computational geometry, a Delaunay triangulation for a set P of points in a plane is a triangulation DT such that no point in P is inside the circumcircle of any triangle in DT. Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the...
may be associated with a characteristic radius, the radius of the smallest empty circle containing the edge or triangle. For each real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
α, the α-complex of the given set of points is the simplicial complex
Simplicial complex
In mathematics, a simplicial complex is a topological space of a certain kind, constructed by "gluing together" points, line segments, triangles, and their n-dimensional counterparts...
formed by the set of edges and triangles whose radii are at most 1/α.
The union of the edges and triangles in the α-complex forms a shape closely resembling the α-shape; however it differs in that it has polygonal edges rather than edges formed from arcs of circles. More specifically, showed that the two shapes are homotopy equivalent. (In this later work, Edelsbrunner used the name "α-shape" to refer to the union of the cells in the α-complex, and instead called the related curvilinear shape an α-body.)
External links
- Alpha Shapes in CGALCGALThe Computational Geometry Algorithms Library is a software library that aims to provide easy access to efficient and reliable algorithms in computational geometry. While primarily written in C++, Python and Scilab bindings are also available....
the Computational Geometry Algorithms Library - Description and implementation by Duke University
- Everything You Always Wanted to Know About Alpha Shapes But Were Afraid to Ask – with illustrations and interactive demonstration