📐 ドロネー三角形分割ジェネレーター

点集合のドロネー三角形分割とは、どの三角形の外接円の内部にも他の点が入らない三角形分割です。この空外接円の性質により、すべての三角形にわたって最小角が最大化され、他の三角形分割が生む細長い三角形を避けられます。1934年にこれを提唱したロシアの数学者ボリス・ドロネーにちなんで名付けられ、形の良い三角形が求められる場面で定番の三角形分割です。

ドロネー三角形分割はボロノイ図の双対です。ボロノイ・セルが辺を共有する点の組をすべて結ぶと、ちょうどドロネー三角形分割になります。つまり各ドロネー辺は1本のボロノイ辺と交差し、各三角形はその外心にあるボロノイ頂点に対応します。ボロノイ重ね表示をオンにして両方の構造を一緒に描き、セルと三角形がどう対応するかを確かめてみましょう。

ドロネー三角形分割は科学や工学の各所で登場します。地図やゲームのための地形・メッシュ生成、条件の良い三角形がシミュレーションを安定させる有限要素法、散らばったデータの空間補間、点群を曲面に変換するコンピュータグラフィックスや3D再構成などです。品質保証の性質から、散らばった点を使えるメッシュに変える際の既定の選択肢となっています。