Delaunay 三角形分割
Delaunay 三角形分割は、 さまざまな用途の科学技術計算で幅広く使用されています。三角形分割の計算には非常に多くのアルゴリズムがありますが、中でも Delaunay 三角形分割の幾何学的な性質は非常に便利です。
基本的な特性は Delaunay 基準です。2 次元の三角形分割の場合は、空の外接円と呼ぶことがあります。2 次元の点集合では、これらの点の Delaunay 三角形分割は各三角形の外接円が内部に他の点を含まないようにします。このプロパティは重要です。下図に示すように、T1 の外接円は空です。内部に点が含まれていません。T2 の外接円は空です。内部に点が含まれていません。この三角形分割は Delaunay 三角形分割です。
下の三角形は異なります。T1 の外接円は空ではありません。内部に V3 が含まれています。T2 の外接円は空ではありません。内部に V1 が含まれています。この三角形分割は Delaunay 三角形分割では "ありません"。
空の外接円の性質を満たす時に、小さな内部角度をもつ三角形より、大きな内部角度をもつ三角形がより多く選択されるので、ドローネ三角形は “形が整っている” と言われます。非 Delaunay 三角形分割の三角形は、頂点 V2 と頂点 V4 は鋭角です。エッジ {V2, V4} が V1 と V3 が連結したエッジに置き換えられた場合には、最小角度は最大化され、Delaunay 三角形分割になります。また、Delaunay 三角形分割は最近傍の点を接続します。これら 2 つの、形が整った三角形および最近傍関係という特性は、実際面において重要な意味をもつことから、散布データの内挿には Delaunay 三角形分割が使用されます。
Delaunay プロパティを適切に設定していても三角形分割の位相幾何は、退化した点集合が存在する場合は一意ではありません。2 次元では 4 個以上の一意でない点が同一円内にある場合、退化が現れます。たとえば正方形の頂点に対する Delaunay 三角形分割は一意ではありません。
Delaunay 三角形分割の性質は、より高次元に拡張します。3 次元の点集合の三角形分割は四面体で構成されます。次の図は、2 つの四面体で構成された単純な 3 次元の Delaunay 三角形分割を示します。1 つの四面体の外接球は、空の外接球の基準を強調表示されています。
3 次元の Delaunay 三角形分割は、空の外接球の基準を満たす四面体を作成します。
MATLAB® には Delaunay 三角形分割を作成する 2 つの方法があります。
delaunayTriangulationは、特別な種類のtriangulationオブジェクトを作成します。Delaunay 固有のクエリだけではなく、任意の三角形分割クエリをデータに対して実行できます。より正式な MATLAB 言語の用語では、delaunayTriangulationはtriangulationのサブクラスです。delaunayとdelaunaynは基本的な Delaunay 三角形分割の表現を作成します。関数delaunayは 2 次元および 3 次元の Delaunay 三角形分割をサポートします。関数delaunaynは、4 次元以上の Delaunay 三角形分割の作成をサポートします。
ヒント
6 次元より大きい Delaunay 三角形分割の作成は、必要となるメモリが指数関数に増加するために、通常、中程度から大きな点集合に関しては実用的ではありません。
delaunayTriangulation クラスは 2 次元および 3 次元での Delaunay 三角形分割の作成をサポートしており、三角形分割に基づくアルゴリズムの開発に有用な多くのメソッドをもっています。これらのクラス メソッドは関数と似ていますが、delaunayTriangulation を使用して作成した三角形分割のみに適用できます。
delaunayTriangulation クラスを使用すると、三角形分割に基づくアプリケーションの開発でさらに多くの機能が利用できます。これは、三角形分割が必要で、さらに次のいずれかの操作を実行する場合に便利です。
クエリ点を囲む三角形または四面体の三角形分割を探索する。
三角形分割を使って最近傍探索を実行する。
三角形分割の位相学的隣接または幾何学的な性質にクエリを行う。
三角形分割を変更して、点を挿入または削除する。
三角形分割のエッジを制限する。これは制約付き Delaunay 三角形分割と呼ばれる。
多角形を三角形分割し、オプションで領域の外側にある三角形を削除する。
Delaunay 三角形分割を使って、凸包またはボロノイ線図を計算する。
