Loading article…
計算幾何学において、ボウヤー・ワトソンアルゴリズムは、任意の次元における有限個の点のドロネー三角形分割を計算する手法である。このアルゴリズムは、ドロネー三角形分割の双対グラフであるボロノイ図を求めるためにも使用できる。
Bowyer–Watson アルゴリズムは増分アルゴリズムです。これは、目的の点のサブセットの有効な Delaunay 三角形分割に点を 1 つずつ追加することで機能します。挿入のたびに、外接円が新しい点を含む三角形はすべて削除され、星形の多角形の穴が残ります。この穴は、新しい点を使用して再三角形分割されます。三角形分割の接続性を使用して削除する三角形を効率的に特定することで、このアルゴリズムはN 個の点を三角形分割するのにO(N log N)の操作で済みますが、特殊な退化ケースではこれがO(N 2 )まで増加する場合があります。[ 1 ]
このアルゴリズムは、ボウヤーアルゴリズムまたはワトソンアルゴリズムと呼ばれることもあります。 エイドリアン・ボウヤーとデビッド・ワトソンは、それぞれ独立して同時期にこのアルゴリズムを考案し、同じ号の『ザ・コンピュータ・ジャーナル』にそれぞれ論文を発表しました（下記参照）。
以下の擬似コードは、ボウヤー・ワトソンアルゴリズムの基本的な実装を示しています。その時間計算量は効率はさまざまな方法で改善できます。たとえば、三角形の接続性を使用して、すべての三角形をチェックすることなく、新しい点を外接円内に含める三角形を特定できます。そうすることで、時間計算量を減らすことができます。外接円を事前に計算することで、メモリ使用量が増える代わりに時間を節約できます。また、点が均一に分布している場合は、挿入前に空間充填ヒルベルト曲線に沿って点をソートすることで、点の位置特定を高速化することもできます。[ 2 ]
function BowyerWatson ( pointList ) // pointList は、三角形分割する点を定義する座標のセットです。triangulation :=空の三角形メッシュデータ構造add super - triangle to triangulation // pointList のすべての点を完全に包含できるほど大きくなければなりませんfor each point in pointList do // すべての点を一度に 1 つずつ三角形分割に追加しますbadTriangles :=空のセットfor each triangle in triangulation do // まず、挿入によって無効になったすべての三角形を見つけますif point is inside circumcircle of triangle add triangle to badTriangles polygon :=空のセットfor each triangle in badTriangles do // 多角形の穴の境界を見つけますfor each edge in triangle do if edge is not shared by any other triangles in badTriangles add edge to polygon for each triangle in badTriangles do // データ構造から削除しますremove triangle from triangulation for each edge in polygon do // 多角形の穴を再三角形分割しますnewTri :=エッジからポイントまでの三角形を作成しますadd newTri to triangulation for each triangle in三角形分割// ポイントの挿入が完了したら、三角形に元のスーパー三角形の頂点が含まれている場合は、三角形分割から三角形を削除して、三角形分割を返します。