このページの内容は最新ではありません。最新版の英語を参照するには、ここをクリックします。

Delaunay 三角形分割の使用

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 三角形分割は、空の外接球の基準を満たす四面体を作成します。

Delaunay 三角形分割の作成

MATLAB^® には Delaunay 三角形分割を作成する 2 つの方法があります。

• 関数 delaunay および関数 delaunayn

• delaunayTriangulation クラス

関数 delaunay は 2 次元および 3 次元の Delaunay 三角形分割をサポートします。関数 delaunayn は、4 次元以上の Delaunay 三角形分割の作成をサポートします。

ヒント

6 次元より大きい Delaunay 三角形分割の作成は、必要となるメモリが指数関数に増加するために、通常、中程度から大きな点集合に関しては実用的ではありません。

delaunayTriangulation クラスは 2 次元および 3 次元での Delaunay 三角形分割の作成をサポートしており、三角形分割に基づくアルゴリズムの開発に有用な多くのメソッドをもっています。これらのクラス メソッドは関数と似ていますが、delaunayTriangulation を使用して作成した三角形分割のみに適用できます。また、delaunayTriangulation クラスは、凸包とボロノイ線図などの関連するコンストラクターの作成をサポートしています。さらに、制約付き Delaunay 三角形分割の作成をサポートします。

概要

• 関数 delaunay は基本的な三角形分割データのみが必要で、そのデータがその用途に十分対応できる場合には便利です。

• delaunayTriangulation クラスを使用すると、三角形分割に基づくアプリケーションの開発でさらに多くの機能が利用できます。これは、三角形分割が必要で、さらに次のいずれかの操作を実行する場合に便利です。

  • クエリ点を囲む三角形または四面体の三角形分割を探索する。

  • 三角形分割を使って最近傍探索を実行する。

  • 三角形分割の位相学的隣接または幾何学的な性質にクエリを行う。

  • 三角形分割を変更して、点を挿入または削除する。

  • 三角形分割のエッジを制限する。これは制約付き Delaunay 三角形分割と呼ばれる。

  • 多角形を三角形分割し、オプションで領域の外側にある三角形を削除する。

  • Delaunay 三角形分割を使って、凸包またはボロノイ線図を計算する。

関数 delaunay および delaunayn の使用

関数 delaunay および delaunayn は点集合を取り、行列形式で三角形分割を作成します。このデータ構造体に関する情報は、三角形分割の行列形式を参照してください。2 次元において関数 delaunay は、散布データ点の集合によって定義される表面のプロットに利用可能な三角形分割の作成によく使われます。この用途では、このアプローチは面が一価である場合にのみ使用できることに注意してください。たとえば、単一の (x、y) 座標に対応する 2 つの z 値がある場合、球面をプロットするのに使用できません。簡単な例で、関数 delaunay でサンプル データセットを表す面をプロットするための使用方法を示します。

MATLAB には関数 delaunayn があり、4 次元以上の Delaunay 三角形分割の作成をサポートします。2 つの相補関数 tsearchn と dsearchn は、N 次元の三角形分割を空間的に探索するサポートも行います。三角形分割ベースの探索に関する詳細は、空間探索 を参照してください。

delaunayTriangulation クラスの使用

MATLAB で Delaunay 三角形分割を作成するためのもう 1 つの方法として、delaunayTriangulation クラスが提供されています。delaunay と delaunayTriangulation は同じアルゴリズムに基づいて同じ三角形分割を作成しますが、delaunayTriangulation は Delaunay ベースのアルゴリズムの開発に役立つ補完的なメソッドを提供します。これらのメソッドは、三角形分割データと共にクラスと呼ばれるコンテナーにパッケージされた関数と同様です。すべてのものをクラスにまとめて保存しておくと、使いやすさを向上させるよりまとまった設定になります。点の位置および最近傍のような三角形分割ベースの探索の性能も向上します。delaunayTriangulation は、Delaunay 三角形分割のインクリメンタルな編集をサポートします。2 次元においてエッジの制約を課すこともできます。

三角形分割表現で紹介されている triangulation クラスは、2 次元と 3 次元の三角形分割に関する幾何学的なクエリと位相幾何学的なクエリをサポートしています。delaunayTriangulation は特殊な triangulation です。つまり、Delaunay 固有のクエリだけではなく、どのような triangulation クエリでも delaunayTriangulation に実行できることを意味します。より正式な MATLAB 言語の用語では、delaunayTriangulation は triangulation のサブクラスです。

制約付き Delaunay 三角形分割

delaunayTriangulation クラスでは 2 次元の三角形分割のエッジに制約を付けることができます。これは、三角形分割で点のペアを選択し、これらの点を連結するようエッジを制約できるということです。1 つ以上のペアの点間にエッジを強制的にプロットするようなイメージです。以下の例は、エッジの制約が三角形分割にどのような影響を与えるかを示しています。

空の外接円の基準を満たすため、以下の三角形分割は Delaunay 三角形分割となっています。

重複する位置を含む点集合の三角形分割

MATLAB の Delaunay アルゴリズムは、固有の点集合から三角形分割を作成します。三角形分割関数またはクラスに渡された点が固有なものでない場合、重複する位置は検出され、重複する点は無視されます。これにより、オリジナルの入力の一部の点、すなわち重複する点を参照しない三角形分割が作成されます。関数 delaunay と delaunayn を操作する場合、重複の存在は重要でなくなります。ただし、delaunayTriangulation クラスにより提供される多くのクエリはインデックス ベースであるため、delaunayTriangulation では固有のデータセットを使用して、三角形分割とデータの操作が行われることに注意してください。このため、通常は固有の点集合に基づいてインデックスを指定します。このデータは delaunayTriangulation の Points プロパティにより保持されます。

次の例は、delaunayTriangulation を使用する際に、Points プロパティに格納されている固有のデータセットを参照することの重要性を示しています。

rng('default')
P = rand([25 2]);
P(18,:) = P(8,:)
P(16,:) = P(6,:)
P(12,:) = P(2,:)

DT = delaunayTriangulation(P)

この三角形分割が作成される際に、MATLAB では警告が表示されます。Points プロパティに、重複する点がデータから削除されていることが表示されます。

DT = 

  delaunayTriangulation with properties:

              Points: [22x2 double]
    ConnectivityList: [31x3 double]
         Constraints: []

たとえば、Delaunay 三角形分割が凸包を計算するために使用される場合、包の点のインデックスは固有の点集合 DT.Points に対するインデックスです。したがって、次のコードを使用して凸包の計算とプロットを行います。

K = DT.convexHull();
plot(DT.Points(:,1),DT.Points(:,2),'.');
hold on
plot(DT.Points(K,1),DT.Points(K,2),'-r');

delaunayTriangulation により提供されたインデックスと共に重複を含む元のデータセットを使用すると、結果が不正確になることがあります。delaunayTriangulation は、固有のデータセット DT.Points に基づくインデックスを使用します。たとえば、K は P に関してではなく、DT.Points に関してインデックス付けされているので、以下は不正確なプロットを作成することになります。

K = DT.convexHull();
plot(P(:,1),P(:,2),'.');
hold on
plot(P(K,1),P(K,2),'-r');

通常は delaunayTriangulation を作成する前に重複を削除して、固有のデータセットを作成した方が便利です。これを行うと混乱を避けることができます。これは、関数 unique を使用して、次のように実行することができます。

rng('default')
P = rand([25 2]);
P(18,:) = P(8,:)
P(16,:) = P(6,:)
P(12,:) = P(2,:)

[~, I, ~] = unique(P,'first','rows');
I = sort(I);
P = P(I,:);
DT = delaunayTriangulation(P)  % The point set is unique

関連するトピック

• 空間探索