Loading article…
メッシュ生成において、ドロネー細分化とは、メッシュ化対象の入力ジオメトリにシュタイナー点を追加する原理に基づいたメッシュ生成アルゴリズムであり、拡張された入力のドロネー三角形分割または制約付きドロネー三角形分割がメッシュ生成アプリケーションの品質要件を満たすようにするものである。
計算流体力学などのコンピュータシミュレーションを行う場合、まず翼断面の2Dアウトラインなどのモデルから始めます。2D有限要素法への入力は、空間全体を埋め尽くす三角形の形式でなければならず、各三角形は1種類の材料（この例では「空気」または「翼」）で満たされている必要があります。細長い三角形は正確にシミュレーションできません。シミュレーション時間は一般的に三角形の数に比例するため、十分な精度で結果が得られるだけの三角形を使用しながら、三角形の数を最小限に抑えたいと考えます。これは通常、非構造格子を使用することによって行われます。コンピュータはメッシュ生成アルゴリズムを使用して、多角形モデルを有限要素法に適した三角形に変換します。
Chew の第 2 アルゴリズムは、区分的線形システム (PLS)を受け取り、三角形の最小角度によって定義される品質の三角形のみの制約付き Delaunay 三角形分割を返します。3 次元空間に埋め込まれたサーフェスのメッシュ生成のために L. Paul Chew によって開発された Chew の第 2 アルゴリズムは、特定のケースでRuppert のアルゴリズムよりも実用的な利点があるため、2 次元メッシュ生成器として採用されており、無料で利用できる Triangle パッケージに実装されているデフォルトの品質メッシュ生成器です。[ 2 ] Chew の第 2 アルゴリズムは、必ず終了し、最小角度が約 28.6 度までの局所的な特徴サイズ- 段階のメッシュを生成することが保証されています。 [ 3 ]
このアルゴリズムは、入力頂点の制約付きデローネ三角形分割から始まります。各ステップで、品質の低い三角形の外心は三角形分割に挿入されますが、例外が1つあります。外心が品質の低い三角形と同じ入力セグメントの反対側にある場合は、セグメントの中点が挿入されます。さらに、元のセグメントの直径球の内側（分割前）に既に挿入されている外心は、三角形分割から削除されます。品質の低い三角形がなくなるまで、外心の挿入が繰り返されます。
ルパートのアルゴリズムは、平面直線グラフ（または2次元を超える次元では区分的線形システム）を入力として受け取り、品質の高い三角形のみからなる適合するドロネー三角形分割を返します。三角形は、外接半径と最短辺の比率が規定の閾値よりも大きい場合、品質が低いとみなされます。1990年代初頭にジム・ルパートによって発見された[ 4 ] 「2次元品質メッシュ生成のためのルパートのアルゴリズムは、おそらく理論的に保証された、実際に満足できる 最初のメッシュ生成アルゴリズムである。」 [ 5 ]
このアルゴリズムは、入力頂点のドロネー三角形分割から始まり、その後、主に2つの操作から構成されます。
これらの操作は、質の低い三角形がなくなり、すべての線分が侵食されなくなるまで繰り返されます。
関数Ruppert( points , segments , threshold )はT := DelaunayTriangulation( points ) Q := 侵入したセグメントと低品質の三角形の集合です Qが空でない間： // メインループQにセグメントsが含まれている場合 ：s の中点をT に挿入する。そうでない場合、 Qには質の悪い三角形tが含まれる。t の外心が線分sに侵入する場合：Qにsを 追加する。 それ以外の場合：t の外心位置をT に挿入するend if end if Q を更新するend whilereturn T end Ruppert。
修正なしの場合、Ruppert のアルゴリズムは、鋭角でない入力と約 20.7 度未満の低品質しきい値に対して、終了して高品質のメッシュを生成することが保証されています。これらの制限を緩和するために、さまざまな小さな改善が行われてきました。入力角度が小さい場合の品質要件を緩和することで、アルゴリズムを任意の直線入力に対応できるように拡張できます。[ 6 ] 曲線入力も同様の手法でメッシュ化できます。[ 7 ] Ruppert のアルゴリズムは自然に 3 次元に拡張できますが、スライバー型の四面体のため、出力保証はやや弱くなります。
ルパートのアルゴリズムの2次元への拡張は、無料で利用できるTriangleパッケージに実装されています。このパッケージに含まれるルパートのアルゴリズムの2つのバリアントは、約26.5度の低品質閾値で確実に終了することが保証されています。[ 8 ] 実際には、これらのアルゴリズムは30度を超える低品質閾値でも成功します。ただし、29.06度を超える閾値でアルゴリズムが失敗する例も知られています。[ 9 ]
{{cite web}}: CS1 maint: bot: 元の URL の状態が不明です (リンク)