デローニー分割法

デローニー分割法 †

デローニー(Delaunay )分割法は、入力された点群に基づいて、２次元空間を３角形に、３次元空間を４面体に分割するときによく使用されます。

実用的には、３次元空間内にある物体の形状（一般には非凸多面体形状）の中に四面体を埋めるのに使用さます。しかし、デローニー分割は凸包を作るため、表面形状を出すためには多面体形状でこの凸包を切り取る必要があります。これを行う手法を制限付きデローニー分割(Constrained Delaunay triangulation)と呼びます。

また、非凸の多面体形状にそのまま四面体を埋めても、四面体の品質が悪いため、解析で使用することはできません。そのため、多面体形状の内部に新規に点を挿入することにより、四面体の品質を向上させるのが普通です。（そもそも、３次元の非凸多面体に、新たに点を挿入することなしに四面体分割できるかという問題は、NP困難であることが知られています。）

デローニー分割法は、メッシュの生成速度はアドバンシングフロント法などに比べて、高速な手法です。

入力となる形状は、点群かnon-mafilodや自己交差を含まない（いわゆる、ウォータータイトな）三角形面が必要とされます。したがって、不完全な表面メッシュ形状を入力にすると４面体の生成に失敗することがあるため、頑健な手法ではありません。

デローニー分割法の例 †

下図は、航空機の胴体周りにデローニー分割法で四面体を作成し、境界層にプリズムメッシュを入れた例です。

点の追加 †

シュナイダー点 †