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

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