アルファシェイプ

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

特徴

任意の実数に対し「半径 $1/ α$ の一般化円板」を次のように定義する。

$α = 0$ のとき、閉半平面とする。
$α > 0$ のとき、半径 $1/ α$ の閉円板とする。
$α < 0$ のとき、半径 $-1/ α$ の円板の補集合の閉包とする。

点群の相異なる二点に対し、ある半径 $1/ α$ の一般化円板が存在して、円板内部が点群を含まずかつ円板の境界がその二点を含むときかつそのときに限り、その二点を結ぶアルファシェイプの辺が存在する。

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

アルファコンプレックス

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

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

アルファコンプレックスに含まれる辺と三角形の集合は、アルファシェイプに極めて似た形状を成す。ただし、アルファシェイプの辺が円弧から成るのに対して、アルファコンプレックスの辺は多角形の辺から成る点が異なる。より詳しくは、Edelsbrunner 1995 にてこれら二つの形状はホモトピー同値であることが示されている（この最近の研究で、 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.
Edelsbrunner, Herbert (1995), “Smooth surfaces for multi-scale shape representation”, Foundations of software technology and theoretical computer science (Bangalore, 1995), Lecture Notes in Comput. Sci., 1026, Berlin: Springer, pp. 391–412, MR 1458090 .
Edelsbrunner, Herbert; Kirkpatrick, David G.; Seidel, Raimund (1983), “On the shape of a set of points in the plane”, IEEE Transactions on Information Theory 29 (4): 551–559, doi:10.1109/TIT.1983.1056714 .

外部リンク

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

特徴

アルファコンプレックス

例

関連項目

参照文献

外部リンク