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

**ドロネー三角形分割ジェネレーター**は、任意の2D点集合を、最小の内角を最大化する一意の三角形分割に変換します。これは、地形モデリング、有限要素法メッシュ生成、最近傍補間、および計算幾何学の教室におけるゴールドスタンダード（世界標準）です。座標を貼り付ける（またはクイックスタートパターンを選択する）だけで、このツールはサーバーサイドでBowyer-Watsonアルゴリズムを実行し、各三角形をその品質に応じて着色し、必要に応じて空の外接円特性、凸包、およびボロノイデュアルを表示します。

生成されたメッシュの読み方

何がこのドロネー三角形分割ジェネレーターを特別にするのか

ドロネー三角形分割とは何ですか？

2Dの点集合が与えられた場合、それらを接続して三角形分割（重なりや隙間のない三角形による凸包の完全なタイリング）を行う方法は通常たくさんあります。ロシアの数学者ボリス・ドロネー（Boris Delaunay、1934年）にちなんで名付けられたドロネー三角形分割は、*空の外接円特性*を満たすものです。すなわち、メッシュ内のすべての三角形について、その3つの頂点を通る円には他の入力点が含まれません。この単一の特性には驚くべき結果があります。同じ点集合のすべての三角形分割の中で、ドロネー三角形分割は最小の内角を最大化します。分かりやすく言えば、可能な限り最も「太く」、「バランスの取れた」三角形を生成します。

Bowyer-Watsonアルゴリズムの仕組み

1. 全ての入力点を非常に大きなスーパー三角形で囲みます。
2. 入力点を1つずつ挿入します。新しい点ごとに、その外接円に新しい点が含まれる既存のすべての三角形（これらは「不適合な」三角形です）を見つけます。
3. 不適合な三角形を削除します。それらが残した穴は多角形の境界を持ちます。
4. 新しい点をその境界のすべてのエッジに接続し、新しい三角形を形成します。
5. すべての点が挿入された後、スーパー三角形の頂点にまだ接触している三角形を削除します。残ったものが元の点集合のドロネー三角形分割です。

ドロネー三角形分割が使用される場所

• 地形モデリング（GIS）: 標高サンプル（通常、地形観測点のように不規則な間隔）が、標高クエリ、シェーディング、および3D可視化のために不規則三角網（TIN）に接続されます。
• 有限要素法解析: 形状の整ったドロネー三角形は、力学、熱伝達、および電磁気学における偏微分方程式に対して安定した数値解をもたらします。
• コンピュータグラフィックス: レンダリング、キャラクターリギング、およびプロシージャル地形のためのメッシュ生成 — ドロネーの「細長い三角形を作らない」保証により、テクスチャの引き伸ばしによるアーティファクトが回避されます。
• 自然近傍補間: ボロノイデュアルを介して各クエリ点の自然近傍を計算することにより、散在するサンプルから滑らかな曲面が再構成されます。
• 計算幾何学のクラス: 凸包、ボロノイ図、点位置決定、および分割統治法と深い関連を持つ標準的なアルゴリズム。
• 3DプリントスライサーおよびCNCツールパス: 2Dドロネー（およびその3Dの従兄弟であるドロネー四面体分割）は、多くのスライシングおよびインフィル戦略の基礎となっています。

ドロネー対ボロノイ：表裏一体の関係

ボロノイ図は平面を入力点ごとに1つのセルに分割し、各セルにはその点に最も近いすべての領域が含まれます。セルが境界を共有する点同士を接続すると、まさにドロネー三角形分割が得られます。逆に、隣接するドロネー三角形の外心を線分で結ぶと、ボロノイのエッジが形成されます。このツールで「ボロノイデュアル」を切り替えて、同じチャート上にオレンジ色の破線が重ねて表示されるのを確認してください。すべてのドロネーのエッジは、正確に1つのボロノイのエッジと直角に交差します。

品質、細長い三角形、およびメッシュの細分化

ドロネーは全域的な最小内角を最大化しますが、根本的に悪い点分布を修正することはできません。入力点がほぼ同一点線上にあるか、密集しているか、あるいは大きな空白領域を残している場合、一部の三角形は依然として細長くなります（最小内角が20°未満）。その修正方法は**スタイナー点（Steiner点）の挿入**です。RuppertのアルゴリズムやChewの第2アルゴリズムなどのアルゴリズムは、細長い三角形の外心に新しい点を反復的に追加し、すべての三角形が目標とする品質境界を満たすまでその都度再三角形分割を行います。このジェネレーターはどの三角形が細長いかを表示するため、より細かいメッシュが必要な場合にどこにスタイナー点を追加すべきかがわかります。

具体的な例

「円と中心」プリセットをクリックしてください。ツールは円の周囲に18個の点、中心に1個の点を配置し、それらを三角形分割します。結果は、中心（ハブ）で交わる18個の完璧な二等辺三角形のファン（扇形）になります。各三角形は、外周で10°、中心で80°–80°の角度を持ちます。最悪の最小内角は10°であり、すべての三角形が細長いとフラグが立てられ、ヒストグラムはすべて0°–10°のビンに表示されます。この例は優れた教材です。入力がそれを強制する場合、ドロネー最適化された三角形分割であっても細長い三角形を持つことがあります。次に「ランダムな点群」をクリックしてください。点が均一に分散しているため、同じアルゴリズムが形状の整った三角形を生成し、ヒストグラムは右側にシフトします。

よくある誤解

• 「ドロネー三角形分割は一意である」: 通常はイエスですが、4つの入力点が同一円周上にある場合、そのグループには2つの有効なドロネー三角形分割が存在します。このジェネレーターは一貫していずれか一方を選択します。
• 「点が多いほど常に品質が向上する」: 配置の悪い点を追加すると、新しい細長い三角形が導入される可能性があります。スタイナー点アルゴリズムは、外心に慎重に新しい点を配置するため、品質の向上が保証されます。
• 「ドロネーは凸包と同じである」: いいえ。凸包は外側の境界であり、ドロネー三角形分割は内部を三角形で埋めます。
• 「すべての三角形分割はほぼ同じに見える」: 違いは劇的です。ドロネーのエッジから1回「フリップ（反転）」するだけで、25°の三角形が5°の三角形に変わることがあります。このツールの品質ヒートマップにより、その違いが可視化されます。

よくある質問