アルファシェイプ

計算幾何学において、 アルファシェイプ（alpha shape, α-shape）とは、ユークリッド平面上の有限の点群の形状に付随する、単純で区分線形な曲線の一群を指す。 にて初めて定義された。点群に付随するアルファシェイプは凸包の一般化であり、全ての凸包はアルファシェイプであるがその逆は言えない。

 特徴 
任意の実数に対し「半径  の一般化円板」を次のように定義する。
  のとき、閉半平面とする。
  のとき、半径  の閉円板とする。
  のとき、半径  の円板の補集合の閉包とする。
点群の相異なる二点に対し、ある半径  の一般化円板が存在して、円板内部が点群を含まずかつ円板の境界がその二点を含むときかつそのときに限り、その二点を結ぶアルファシェイプの辺が存在する。

 のとき、アルファシェイプは点群に付随する通常の凸包と一致する。

 アルファコンプレックス 
アルファシェイプは、点群のドロネー三角分割のサブコンプレックスであるアルファコンプレックスと密接に関連している。

ドロネー三角の各辺を特性半径、つまりその辺を含む最小の円の半径と関連づけることができる。実数  が与えられたとき、ある点群のアルファコンプレックスとはその辺の特性半径がたかだか  である辺の集合により構成される複体を指す。

アルファコンプレックスに含まれる辺と三角形の集合は、アルファシェイプに極めて似た形状を成す。ただし、アルファシェイプの辺が円弧から成るのに対して、アルファコンプレックスの辺は多角形の辺から成る点が異なる。より詳しくは、 にてこれら二つの形状はホモトピー同値であることが示されている（この最近の研究で、 Edelsbrunner は「アルファシェイプ」という名前をアルファコンプレックスのセルの和集合を表わすものとして用い、関連する曲線的形状は代わりにアルファボディという名前を用いている）。

 例 

 関連項目 

 参照文献 
 N. Akkiraju, H. Edelsbrunner, M. Facello, P. Fu, E. P. Mucke, and C. Varela. "Alpha shapes: definition and software". In Proc. Internat. Comput. Geom. Software Workshop 1995, Minneapolis.
 .
 .

 外部リンク 

 Alpha Shapes in CGAL the Computational Geometry Algorithms Library
 Alpha Complex in the GUDHI 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
 Implementation of the 3D alpha-shape for the reconstruction of 3D sets from a point cloud in R
 Description of the implementation details for alpha shapes - Lecture providing a description of the formal and intuitive aspects of alpha shape implementation
 Alpha Hulls, Shapes, and Weighted things - lecture slides by Robert Pless at the Washington University
Alpha Hulls, Shapes, and Weighted things - lecture slides by Robert Pless at the Washington University

Category:計算幾何学
Category:数学に関する記事