Delaunay Triangulation / Tetrahedralization

This explanation is currently available in Japanese.

ひとことで

ばらばらに置いた点を三角形でつなぐとき、どの三角形の外接円（3 つの頂点を通る円）の中にも、ほかの点が入らないようにつなぐ方法です。この条件を満たすつなぎ方は、三角形のいちばん小さい角が最も大きくなる、つまり細長い三角形が最も少ない分け方になります。3 次元では、外接球の中に点がない四面体に分けます。

ゲームでの使いどころ

• ダンジョンの通路：部屋の中心をドロネー分割して「近い部屋どうしの候補の辺」を作り、最小全域木で全部の部屋をつなぎ、いくつか辺を足して輪を作る（TinyKeep などで知られる手順）。
• ナビゲーションメッシュ：歩ける領域を三角形に分けてナビゲーションメッシュを作る。細長い三角形が少ないので、経路が自然になる。
• 地形・点群のメッシュ化：まばらな高さの標本点から地形のメッシュを作る。
• ボロノイ図：ドロネー分割の双対（外接円の中心どうしを結んだ図）がボロノイ図になる。ボロノイ破砕や領土の区分けに使う。

しくみ

よく使われるのはボウヤー・ワトソン法です。

1. すべての点を囲む大きな三角形（スーパー三角形）を 1 つ置きます。
2. 点を 1 つずつ加えます。新しい点 $p$ を外接円の中に含んでしまう三角形をすべて探して取り除きます。
3. 取り除いた領域は、$p$ から見て全体が見える多角形の穴になります。穴のふちの各辺と $p$ を結んで、新しい三角形を作ります。
4. すべての点を加え終えたら、スーパー三角形の頂点につながる三角形を取り除きます。

点 $p$ が三角形 $abc$（反時計回り）の外接円の内側にあるかは、次の行列式が正かどうかで判定できます。

実装のポイント

• 速くするには：単純な実装は、点ごとに全部の三角形を調べるので $O(n^2)$ です。新しい点を含む三角形から隣をたどって探す、点をランダムな順に加える、などの工夫で $O(n \log n)$ に近づきます。大量の点には、実績のあるライブラリ（Delaunator など）を使うのが確実です。
• 数値の誤差：4 点がほぼ同じ円の上にあると、判定が揺れて三角形が重なったり抜けたりします。厳密な判定式（Shewchuk の robust predicates）を使うと安全です。
• 制約付きドロネー分割：壁や道のように「必ず辺として残したい線分」がある場合は、制約付きドロネー分割（CDT）を使います。ナビゲーションメッシュではこちらが必要になります。

つまずきやすい点

• 外側の細い三角形：点の集まりの外周（凸包）の近くには、どうしても細い三角形が残ります。デモの「いちばん小さい角」がとても小さいのはこのためです。
• スーパー三角形が小さすぎる：大きさが足りないと、外周の三角形が正しく作れません。点の範囲より十分大きくします。
• 重複した点：まったく同じ位置の点があると、三角形がつぶれて破綻します。事前に取り除きます。

デモで試すこと

1. 三角形の上にポインターを置くと、その三角形の外接円（黄色）が出ます。どの三角形でも、円の中にほかの点が入っていないことを確かめてください。
2. 点をドラッグすると、条件が崩れた所だけ辺がつなぎ変わります（辺のフリップ）。
3. 「ボロノイ図を重ねる」で、隣り合う三角形の外接円の中心を結んだ青い線が、各点の「なわばり」を分けていることがわかります。
4. 「1 点ずつ追加」では、新しい点（赤）の外接円に入られた三角形が取り除かれ、穴のふち（黄色）とつなぎ直される手順が再生されます。
5. 「ダンジョンの通路」で、部屋の中心のドロネー分割から、最小全域木（緑）と少しの輪（点線）で通路が作られます。「点を並べ直す」で別の配置を試せます。