Triangulation of Point Sets Containing Duplicate Locations

The Delaunay algorithms in MATLAB^® construct a triangulation from a unique set of points. If the points passed to the triangulation function, or class, are not unique, the duplicate locations are detected and the duplicate point is ignored. This produces a triangulation that does not reference some points in the original input, namely the duplicate points. When you work with the delaunay and delaunayn functions, the presence of duplicates may be of little consequence. However, since many of the queries provided by the delaunayTriangulation class are index based, it is important to understand that delaunayTriangulation triangulates and works with the unique data set. Therefore, indexing based on the unique point set is the convention. This data is maintained by the Points property of delaunayTriangulation.

The following example illustrates the importance of referencing the unique data set stored within the Points property when working with delaunayTriangulation:

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

When the triangulation is created, MATLAB issues a warning. The Points property shows that the duplicate points have been removed from the data.

DT = 

  delaunayTriangulation with properties:

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

If for example, the Delaunay triangulation is used to compute the convex hull, the indices of the points on the hull are indices with respect to the unique point set, DT.Points. Therefore, use the following code to compute and plot the convex hull:

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

If the original data set containing the duplicates were used in conjunction with the indices provided by delaunayTriangulation, then the result would be incorrect. The delaunayTriangulation works with indices that are based on the unique data set DT.Points. For example, the following would produce an incorrect plot, because K is indexed with respect to DT.Points and not P:

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

It’s often more convenient to create a unique data set by removing duplicates prior to creating the delaunayTriangulation. Doing this eliminates the potential for confusion. This can be accomplished using the unique function as follows:

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