計算幾何学において、ボウヤー・ワトソン法は、任意の次元における有限点集合のドロネー三角形分割を計算する手法である。このアルゴリズムは、ドロネー三角形分割の双対グラフであるボロノイ図を求めるためにも用いられる。
説明
ボウヤー・ワトソンアルゴリズムは増分アルゴリズムである。これは、有効なドロネー三角形分割（Delaunay triangulation）に、必要な点のサブセットを1つずつ点として追加していくことで機能する。追加するたびに、その点の外接円に新しい点が含まれる三角形が削除され、星型の多角形の穴が残る。この穴は、新しい点を用いて再三角形分割される。三角形分割の連結性を利用して削除する三角形を効率的に特定することで、このアルゴリズムはN点の三角形分割にO(N log N)回の演算で済む。ただし、特殊な退化ケースでは、この演算回数はO(N 2 )回まで増加する。[1]
-
最初のステップ: 囲む「スーパー」三角形にノードを挿入する
-
2番目のノードを挿入
-
3番目のノードを挿入
-
4番目のノードを挿入
-
5番目（最後）のノードを挿入する
-
スーパー三角形の極値を持つエッジを削除する
歴史
このアルゴリズムは、ボウヤーアルゴリズムまたはワトソンアルゴリズムと呼ばれることもあります。 エイドリアン・ボウヤーとデイビッド・ワトソンはそれぞれ独立してこのアルゴリズムを考案し、それぞれが『The Computer Journal』誌の同じ号に論文を発表しました（下記参照）。
擬似コード
以下の擬似コードは、Bowyer-Watsonアルゴリズムの基本的な実装を示しています。その時間計算量は です。効率はいくつかの方法で改善できます。例えば、三角形の連結性を利用することで、新しい点を外接円内に含む三角形を特定できます。この方法では、すべての三角形をチェックする必要はありません。これにより、時間計算量を まで削減できます。外接円を事前に計算しておくことで、メモリ使用量は増加しますが、時間を節約できます。また、点が均一に分布している場合は、挿入前に空間充填ヒルベルト曲線に沿って点をソートすることで、点の特定を高速化できます。[2]
function BowyerWatson ( pointList ) // pointList は、三角形分割される点を定義する座標のセットです。triangulation :=空の三角形メッシュデータ構造。triangulationにsuper - triangleを追加します。 // pointList内のすべての点を完全に含むのに十分な大きさである必要があります。 pointList内の各点に対して、次の操作を行います。 // すべての点を 1 つずつ三角形分割に追加します。badTriangles := triangulation内の各三角形に対して、空のセットを実行します。// 最初に、挿入によって有効ではなくなったすべての三角形を検索します。点が三角形の外接円の内側にある場合は、badTrianglesに三角形を追加します。 polygon := badTriangles内の各三角形に対して、空のセットを実行します。// 多角形の穴の境界を検索します。triangle内の各エッジに対して、次の操作を行います。badTriangles内の他の三角形によってエッジが共有されていない場合は、 polygonにエッジを追加します。 badTriangles内の各三角形に対して、次の操作を行います。// それらをデータ構造から削除します。 triangulationからtriangle を削除します。polygon内の各エッジに対して、次の操作を行います。// 多角形の穴を再三角形分割します。newTri :=エッジから点まで三角形を形成します。 triangulationに各三角形に対して、newTri を追加します。三角形分割で// ポイントの挿入が完了しました。三角形に元のスーパー三角形の頂点が含まれている場合はクリーンアップします。三角形分割から三角形を削除します。三角形分割を返します。
参考文献
- ^ Rebay, S. Delaunay三角形分割とBowyer-Watsonアルゴリズムによる効率的な非構造メッシュ生成. Journal of Computational Physics第106巻第1号、1993年5月、p. 127.
- ^ Liu, Yuanxin, Jack Snoeyink. 「3D Delaunay tessellation の 5 つの実装の比較」Combinatorial and Computational Geometry 52 (2005): 439-458.
さらに読む
- ボウヤー、エイドリアン(1981). 「ディリクレ分割の計算」. Comput. J. 24 (2): 162– 166. doi : 10.1093/comjnl/24.2.162 .
- Watson, David F. (1981). 「n次元ドロネー分割の計算とボロノイ多面体への応用」. Comput. J. 24 (2): 167– 172. doi :10.1093/comjnl/24.2.167.
- 地形モデリングに適した効率的な三角測量アルゴリズムの一般的な説明と複数の言語でのソース コード例。
外部リンク
