중복 위치를 포함하는 점 집합의 삼각분할

MATLAB^®의 들로네(Delaunay) 알고리즘은 고유한 점 집합에서 삼각분할을 생성합니다. 삼각분할 함수나 클래스로 전달된 점들이 고유하지 않으면 중복 위치가 검색되고 중복 점은 무시됩니다. 이렇게 함으로써 원래 입력값에서 중복 점을 참조하지 않는 삼각분할이 생성됩니다. delaunay 함수와 delaunayn 함수를 사용하여 작업할 때 중복 점이 존재하는 것은 중요하지 않을 수 있습니다. 그러나, delaunayTriangulation 클래스에서 제공하는 쿼리 대부분은 인덱스 기반이므로 delaunayTriangulation은 고유한 데이터 세트를 사용하여 삼각분할하고 작업해야 합니다. 이러한 이유로 고유한 점 집합을 기반으로 하여 인덱싱하는 것이 이 알고리즘의 조건(Convention)이 됩니다. 점 데이터는 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: []

예를 들어, 들로네 삼각분할을 사용하여 컨벡스 헐(Convex Hull)을 계산하는 경우 껍질 상의 점에 대한 인덱스는 고유한 점 집합 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가 DT.Points가 아닌 P를 기준으로 인덱싱되었기 때문에 잘못된 플롯을 생성할 수 있습니다.

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