凸包を計算

MATLAB^® では、凸包の計算にいくつかの方法が提供されています。

• MATLAB の関数 convhull と convhulln を使用します。

• delaunayTriangulation クラスが提供する convexHull メソッドを使用します。

• アルファ半径が Inf である関数 alphaShape を使用します。

関数 convhull は、2 次元と 3 次元の凸包の計算をサポートします。関数 convhulln は、N 次元の凸包の計算をサポートします (N ≥ 2)。関数 convhull は、ロバスト性と性能がより優れているため、2 次元または 3 次元の計算に推奨されます。

delaunayTriangulation クラスは、Delaunay 三角形分割による凸包の 2 次元および 3 次元の計算をサポートします。この計算は、専用の関数 convhull と関数 convhulln ほど効率的ではありません。ただし、delaunayTriangulation の点集合があり、凸包が必要な場合は、convexHull メソッドを使用して既存の三角形分割から凸包をより効率的に計算することができます。

また、関数 alphaShape はアルファ半径入力パラメーターを Inf に設定することにより、凸包の 2 次元および 3 次元の計算をサポートします。ただし、delaunayTriangulation と同様、alphaShape を使用した凸包の計算は、convhull または convhulln を直接使用するより効率が劣ります。例外は、既に作成されているアルファ形状オブジェクトを使用する場合です。

convhull と convhulln 使って、凸包を計算

関数 convhull と関数 convhulln は、点集合を取得し、凸包の境界上にある点のインデックスを出力します。凸包の点インデックス ベースの表現は、プロットと便利なデータ アクセスをサポートします。次の例は、凸包の計算と表現を説明しています。

最初の例では、関数 convhull の入力に、seamount データセットからの 2 次元の点集合を使用します。

データを読み込みます。

load seamount

点集合の凸包を計算します。

K = convhull(x,y);

K は、凸包の周りを、反時計回りのサイクルで配置されている点のインデックスを表します。

データとその凸包をプロットします。

plot(x,y,'.','markersize',12)
xlabel('Longitude')
ylabel('Latitude')
hold on

plot(x(K),y(K),'r')

凸包上の点に点ラベルを追加して、K の構造を確認します。

[K,A] = convhull(x,y);

convhull は、2 次元と 3 次元両方の点集合の凸包を計算することができます。seamount データセットを再使用して、3 次元の凸包の計算を説明しています。

seamount z 座標データの高度を含めます。

close(gcf)
K = convhull(x,y,z);

凸包の 3 次元の境界で、K は、三角形分割で表されます。これは、点配列に関してインデックス化された行列形式の三角面の集合です。行列 K の各行は、三角形を表します。

凸包の境界が三角形分割として表されているので、三角形分割プロット関数 trisurf を使用することができます。

trisurf(K,x,y,z,'Facecolor','cyan')

3 次元の凸包で囲まれたボリュームは、convhull により、オプションで返すことができます。構文は以下のようになります。

[K,V] = convhull(x,y,z);

関数 convhull は、また、領域またはボリュームに貢献しない頂点を削除することで凸包の表現を簡潔にするオプションを提供します。たとえば、凸包の境界の小平面が、同一線上または共面点にある場合、それらをマージして、より簡潔な表現にできます。次の例では、このオプションの使用を説明します。

[x,y,z] = meshgrid(-2:1:2,-2:1:2,-2:1:2);
x = x(:);
y = y(:); 
z = z(:);

K1 = convhull(x,y,z);
subplot(1,2,1)
defaultFaceColor  = [0.6875 0.8750 0.8984];
trisurf(K1,x,y,z,'Facecolor',defaultFaceColor)
axis equal
title(sprintf('Convex hull with simplify\nset to false'))

K2 = convhull(x,y,z,'simplify',true);
subplot(1,2,2)
trisurf(K2,x,y,z,'Facecolor',defaultFaceColor)
axis equal
title(sprintf('Convex hull with simplify\nset to true'))

MATLAB は、関数 convhulln を提供し、高次元の凸包およびハイパーボリュームの計算をサポートします。convhulln は、N 次元をサポートしますが、10 次元を超える問題では、必要なメモリ量が急激に増えることが課題となります。

関数 convhull は、よりロバストで、性能を向上させるため、2 次元や 3 次元の convhulln より優れています。

delaunayTriangulation クラスを使用する凸包の計算

この例では、2 次元の点集合の Delaunay 三角形分割とその点集合の凸包の関係を説明します。

delaunayTriangulation クラスは、2 次元空間と 3 次元空間の Delaunay 三角形分割の計算をサポートしています。またこのクラスは、convexHull メソッドを提供して、三角形分割から凸包を導きます。

2 次元で点集合の Delaunay 三角形分割を作成します。

X = [-1.5 3.2; 1.8 3.3; -3.7 1.5; -1.5 1.3; 0.8 1.2; ...
      3.3 1.5; -4.0 -1.0; -2.3 -0.7; 0 -0.5; 2.0 -1.5; ...
      3.7 -0.8; -3.5 -2.9; -0.9 -3.9; 2.0 -3.5; 3.5 -2.25];

dt = delaunayTriangulation(X);

三角形分割をプロットし、1 つの三角形のみで共有されるエッジを強調表示して、凸包を示します。

triplot(dt)

fe = freeBoundary(dt)';
hold on
plot(X(fe,1), X(fe,2), '-r', 'LineWidth',2)
hold off

3 次元では、1 つの四面体のみで共有される三角形分割の面は、凸包の境界を示します。

専用の関数 convhull は、convexHull メソッドに基づく計算よりも通常はより効率的です。ただし、三角形分割に基づくアプローチは、以下の場合に適切です。

• 既に点集合の delaunayTriangulation があり、凸包も必要な場合。

• 集合から点を徐々に加えたり、削除する必要があり、点を編集した後に凸包を頻繁に再計算する必要がある場合。

alphaShape を使用した凸包の計算

この例では、関数 alphaShape を使って 2 次元点集合の凸包を計算する方法を説明します。

alphaShape は 2 次元または 3 次元の点集合から正規化されたアルファ形状を計算します。アルファ半径を指定することで、アルファ形状がどれだけ厳密にまたは緩やかに点集合を包み込むかを設定できます。アルファ半径を Inf に設定して得られる結果のアルファ形状が、点集合の凸包です。

2 次元の点の集合を作成します。

X = [-1.5 3.2; 1.8 3.3; -3.7 1.5; -1.5 1.3; 0.8 1.2; ...
      3.3 1.5; -4.0 -1.0; -2.3 -0.7; 0 -0.5; 2.0 -1.5; ...
      3.7 -0.8; -3.5 -2.9; -0.9 -3.9; 2.0 -3.5; 3.5 -2.25];

アルファ半径を Inf に等しく設定したアルファ形状を使用して、点集合の凸包を計算し、プロットします。

shp = alphaShape(X,Inf);
plot(shp)

参考

convhull | convhulln | convexHull | delaunayTriangulation | alphaShape

関連するトピック

• Delaunay 三角形分割の使用