Delaunay三角分割 — CAE用語解説

FEMメッシュ生成の核心アルゴリズムのひとつだ。Delaunay三角分割とは「任意の三角形の外接円の内部に他の点が含まれない」という条件（外接円条件）を満たす三角形分割で、与えられた点集合に対して一意に定まる（縮退を除いて）。この分割は最小角度が最大化されるという性質があり、扁平な三角形（スリバー要素）が少なくなる。FEM精度には要素の形状比が重要なのでDelaunay条件を満たすメッシュは精度・安定性ともに優れる。

代表的なアルゴリズムはインクリメンタル挿入法だ。点を一つずつ追加して外接円条件が破れた三角形をflip（辺交換）で修復する。実装はBowyer-WatsonアルゴリズムやIncremental Flip法が広く使われている。三角形（2D）の拡張が四面体（3D）のDelaunay分割で、Tetgen（OSS）やNetgenはこれを実装している。ただし複雑な境界形状（鋭い角や細いスリット）ではConstrained Delaunayとして境界エッジを強制保持する拡張が必要になる。

Delaunay分割は外接円条件は満たすが、要素の均一性は保証しない。そこでRuppertアルゴリズム（2D）やChewアルゴリズムなど品質リファインメント手法を重ねる。最小角度がしきい値（例：20度）未満の三角形に新しい点（Steiner点）を追加して外接円条件を再適用する処理を繰り返す。3Dでは「スリバー四面体（扁平な四面体）」の除去が難しく、最適化ベースのスムージング（Laplacian、ODT最適化）を組み合わせることが多い。

深い双対関係がある。Voronoiダイアグラムは各点に「最も近い点の領域」を割り当てた図で、点集合と同じ情報から構築される。Delaunay三角分割のすべての三角形の外接円の中心を結ぶとVoronoiダイアグラムになる——これが双対性だ。有限体積法（FVM）のセル中心法ではVoronoiセルがコントロールボリュームとして使われる。さらにVoronoiメッシュは多面体セルを生成するので、OpenFOAMのsnappyHexMeshのような多面体メッシャーでも活用されている。