Main Content

들로네 삼각분할(Delaunay Triangulation)로 작업하기

들로네 삼각분할 정의

들로네 삼각분할(Delaunay Triangulation)은 계산과학의 다양한 응용 분야에 널리 사용됩니다. 삼각분할 계산에 사용할 수 있는 알고리즘이 많이 있지만 들로네 삼각분할의 기하학적 특성을 사용하는 것이 유용합니다.

기본 특성은 들로네 기준(Delaunay criterion)입니다. 2차원 삼각분할의 경우, 이 특성을 종종 빈 외접원 기준(Empty Circumcircle Criterion)이라고 합니다. 2차원 점 집합의 경우, 점에 대한 들로네 삼각분할은 각 삼각형에 대한 외접원이 내부에 다른 점을 포함하지 않도록 해야 합니다. 이는 중요한 특성입니다. 아래 그림에서 T1에 대한 외접원은 비어 있습니다. 외접원의 내부에 점이 포함되어 있지 않습니다. T2에 대한 외접원도 비어 있습니다. 외접원의 내부에 점이 포함되어 있지 않습니다. 이 삼각분할은 들로네 삼각분할입니다.

Delaunay triangulation with circumcircles plotted.

아래에 나와 있는 삼각형은 다릅니다. T1에 대한 외접원이 비어 있지 않습니다. 이 외접원은 내부에 V3을 포함합니다. T2에 대한 외접원도 비어 있지 않습니다. 이 외접원은 내부에 V1을 포함합니다. 이 삼각분할은 들로네 삼각분할이 아닙니다.

Non-Delaunay triangulation with circumcircles plotted.

들로네 삼각형은 빈 외접원 특성을 충족하기 위하여 내각이 작은 삼각형 대신 내각이 큰 삼각형을 선택하므로 "형태가 좋은 것"으로 간주됩니다. 비 들로네 삼각분할의 삼각형은 꼭짓점 V2와 V4에서 예각을 가집니다. 모서리 {V2, V4}가 V1과 V3을 연결하는 모서리로 대체되면 최소 각도가 최대화되고 삼각분할은 들로네 삼각분할이 됩니다. 또한, 들로네 삼각분할은 최근접이웃 방식으로 점을 연결합니다. 이러한 두 가지 특성, 즉 형태가 좋은 삼각형과 최근접이웃 관계는 실제로 중요한 의미를 가지며, 산점 데이터 보간에서 들로네 삼각분할을 사용하게 되는 이유가 됩니다.

들로네 특성이 명확히 정의되어 있지만, 삼각분할의 위상은 퇴화된(Degenerate) 점 집합이 존재하는 경우 고유하지 않습니다. 2차원에서 4개 이상의 고유한 점이 동일한 원 내에 있을 경우 퇴화(Degeneracy)가 발생합니다. 예를 들어, 정사각형의 꼭짓점은 고유하지 않은 들로네 삼각분할을 가집니다.

Delaunay triangulation of the vertices of a square, for which two different valid Delaunay triangulations are possible.

들로네 삼각분할의 특성은 더 높은 차원으로 확장됩니다. 3차원 점 집합에 대한 삼각분할은 사면체로 구성됩니다. 다음 그림에서는 2개의 사면체로 구성된 단순한 3차원 들로네 삼각분할을 보여줍니다. 빈 외접구 기준(Empty Circumsphere Criterion)을 강조하기 위해 하나의 사면체에 대한 외접구가 표시되어 있습니다.

3-D Delaunay triangulation with circumsphere.

3차원 들로네 삼각분할은 빈 외접구 기준을 충족하는 사면체를 생성합니다.

들로네 삼각분할 만들기

MATLAB®은 들로네 삼각분할을 만드는 데 사용할 수 있는 다음과 같은 두 가지 방법을 제공합니다.

delaunay 함수를 사용하면 2차원 들로네 삼각분할과 3차원 들로네 삼각분할을 생성할 수 있습니다. delaunayn 함수를 사용하면 4차원 이상의 들로네 삼각분할을 생성할 수 있습니다.

팁

6차원이 넘는 차원에서 들로네 삼각분할을 만드는 작업은 필요한 메모리가 급격하게 증가하므로 중간 규모나 큰 규모의 점 집합에는 잘 사용되지 않습니다.

delaunayTriangulation 클래스를 사용하면 2차원과 3차원에서 들로네 삼각분할을 생성할 수 있습니다. 이 클래스는 삼각분할 기반 알고리즘을 개발하는 데 유용한 많은 메서드를 제공합니다. 이러한 클래스 메서드는 함수와 비슷하지만, delaunayTriangulation을 사용하여 생성된 삼각분할에만 사용됩니다. delaunayTriangulation 클래스로는 연관 구조인 볼록 껍질과 보로노이 다이어그램도 생성할 수 있습니다. 또한, 제약 조건이 적용되는 들로네 삼각분할에 대한 생성도 지원합니다.

요약하면 다음과 같습니다.

  • delaunay 함수는, 기본 삼각분할 데이터만 필요로 하고 응용 사례에 이 데이터만으로 충분히 완벽한 경우에 유용합니다.

  • delaunayTriangulation 클래스는 삼각분할 기반 응용 사례를 개발하는 데 사용할 수 있는 더 많은 기능을 제공합니다. 이 클래스는 삼각분할이 필요하고 다음 작업을 수행하려는 경우에 유용합니다.

    • 쿼리 점을 포함하는 삼각형이나 사면체에 대한 삼각분할을 탐색합니다.

    • 삼각분할을 사용하여 최근접이웃 점을 탐색합니다.

    • 삼각분할의 위상적 인접성이나 기하학적 특성을 쿼리합니다.

    • 삼각분할을 수정하여 점을 삽입하거나 제거합니다.

    • 삼각분할에서 모서리에 제약 조건을 적용합니다. 이를 제약 조건이 적용되는 들로네 삼각분할(Constrained Delaunay Triangulation)이라고 합니다.

    • 다각형을 삼각분할하고, 선택적으로 영역 외부에 있는 삼각형을 제거합니다.

    • 들로네 삼각분할을 사용하여 볼록 껍질이나 보로노이 다이어그램을 구합니다.

delaunay 함수와 delaunayn 함수 사용하기

delaunay 함수와 delaunayn 함수는 점 집합을 인수로 받아 행렬 형식으로 삼각분할을 생성합니다. 이 데이터 구조에 대한 자세한 내용은 삼각분할 행렬 형식 항목을 참조하십시오. 2차원에서 delaunay 함수는 주로 산점 데이터 세트의 곡면을 플로팅하는 데 필요한 삼각분할을 생성합니다. 이 응용 사례에서는 곡면이 단일 값으로 구성된 경우에만 이 접근 방식을 사용할 수 있다는 점에 유의해야 합니다. 예를 들어, 하나의 (x, y) 좌표에 2개의 z 값이 대응되는 구면(Spherical Surface)을 플로팅하는 데는 사용할 수 없습니다. delaunay 함수를 사용하여 샘플링된 데이터 세트를 곡면으로 플로팅하여 보여주는 간단한 예를 들어보겠습니다.

이 예제에서는 delaunay 함수를 사용하여 seamount 데이터 세트로 2차원 들로네 삼각분할을 만드는 방법을 보여줍니다. seamount는 해저산을 의미합니다. 이 데이터 세트는 일련의 경도(x) 및 위도(y)의 위치값과, 이러한 좌표에서 측정된 대응하는 해저산 고도값(z)으로 구성되어 있습니다.

seamount 데이터 세트를 불러오고 (x, y) 데이터를 산점도 플롯으로 표시합니다.

load seamount
plot(x,y,'.','markersize',12)
xlabel('Longitude'), ylabel('Latitude')
grid on

Figure contains an axes object. The axes object with xlabel Longitude, ylabel Latitude contains a line object which displays its values using only markers.

이 점 집합에서 들로네 삼각분할을 생성하고 triplot을 사용하여 기존 Figure에 이 삼각분할을 플로팅합니다.

tri = delaunay(x,y);
hold on, triplot(tri,x,y), hold off

Figure contains an axes object. The axes object with xlabel Longitude, ylabel Latitude contains 2 objects of type line. One or more of the lines displays its values using only markers

seamount의 깊이 데이터(z)를 추가하여 꼭짓점을 위로 올리고 곡면을 만듭니다. 새 Figure를 만든 다음 trimesh를 사용하여 곡면을 와이어프레임 모드로 플로팅합니다.

figure
hidden on
trimesh(tri,x,y,z)
xlabel('Longitude'),ylabel('Latitude'),zlabel('Depth in Feet');

Figure contains an axes object. The axes object with xlabel Longitude, ylabel Latitude contains an object of type patch.

곡면을 음영 모드로 플로팅하려면 trimesh 대신 trisurf를 사용하십시오.

delaunay 함수를 사용하여 3차원 들로네 삼각분할을 만들 수도 있습니다. 이 삼각분할은 사면체로 구성됩니다.

이 예제에서는 랜덤 데이터 세트의 3차원 들로네 삼각분할을 만드는 방법을 보여줍니다. tetramesh를 사용하여 삼각분할을 플로팅하고, FaceAlpha 옵션으로 플롯에 투명도를 추가합니다.

rng('default')
X = rand([30 3]);
tet = delaunay(X);
faceColor  = [0.6875 0.8750 0.8984];
tetramesh(tet,X,'FaceColor', faceColor,'FaceAlpha',0.3);

Figure contains an axes object. The axes object contains 102 objects of type patch.

MATLAB에서는 delaunayn 함수를 사용하여 4차원 이상에서 들로네 삼각분할을 생성할 수 있습니다. N차원 삼각분할에 대한 공간 탐색에는 2개의 함수 tsearchn과 dsearchn을 사용할 수 있습니다. 삼각분할 기반 탐색에 대한 자세한 내용은 공간 탐색 항목을 참조하십시오.

delaunayTriangulation 클래스 사용하기

delaunayTriangulation 클래스는 MATLAB에서 들로네 삼각분할을 만들 수 있는 또 다른 방법을 제공합니다. delaunay와 delaunayTriangulation은 동일한 기본 알고리즘을 사용하고 동일한 삼각분할을 생성하지만 delaunayTriangulation은 들로네 기반 알고리즘을 개발하는 데 유용한 상호 보완적인 메서드를 제공합니다. 이러한 메서드는 삼각분할 데이터와 함께 클래스(일종의 컨테이너)에 패키징된 것으로 함수와 같습니다. 모든 요소를 하나의 클래스에 함께 유지하면 사용 편의성을 향상시키는 더욱 체계적인 설정이 구현됩니다. 또한, 점위치(Point-Location) 탐색과 최근접이웃 탐색 같은 삼각분할 기반 탐색의 성능도 향상됩니다. delaunayTriangulation은 들로네 삼각분할의 증분 편집도 지원합니다. 또한, 2차원에서 모서리 제약 조건도 적용할 수 있도록 합니다.

삼각분할 표현(Triangulation Representation)에 2차원 삼각분할과 3차원 삼각분할을 위한 위상 쿼리와 기하학 쿼리를 지원하는 triangulation 클래스가 소개되어 있습니다. delaunayTriangulation은 특수한 종류의 triangulation입니다. 즉, delaunayTriangulation에 대해 들로네 쿼리뿐만 아니라 모든 triangulation 쿼리를 수행할 수 있습니다. MATLAB 언어 측면에서 보면, delaunayTriangulation은 triangulation의 서브클래스입니다.

이 예제에서는 delaunayTriangulation을 사용하여 seamount 데이터로 들로네 삼각분할을 만들고, 삼각분할을 쿼리하고 편집하는 방법을 보여줍니다. seamount 데이터 세트에는 seamount의 곡면을 정의하는 (x, y) 위치값과 대응하는 고도값(z)이 포함되어 있습니다.

(x, y) 데이터를 불러온 후 삼각분할합니다.

load seamount
DT = delaunayTriangulation(x,y)
DT = 
  delaunayTriangulation with properties:

              Points: [294x2 double]
    ConnectivityList: [566x3 double]
         Constraints: []

적용된 모서리 제약 조건이 없으므로 Constraints 속성은 비어 있습니다. Points 속성은 꼭짓점의 좌표를 나타내고, ConnectivityList 속성은 삼각형을 나타냅니다. 이 두 속성이 함께 삼각분할의 행렬 데이터를 정의합니다.

delaunayTriangulation 클래스는 행렬 데이터를 감싸는 래퍼이며, 일련의 상호 보완적인 메서드를 제공합니다. 구조체의 필드에 액세스하는 것과 같은 방법으로 delaunayTriangulation의 속성에 액세스합니다.

꼭짓점 데이터에 액세스합니다.

DT.Points;

연결 데이터에 액세스합니다.

DT.ConnectivityList;

ConnectivityList 속성의 첫 번째 삼각형에 액세스합니다.

DT.ConnectivityList(1,:)
ans = 1×3

   230   205   152

delaunayTriangulation은 ConnectivityList 속성 행렬의 요소를 참조할 수 있는 쉬운 방법을 제공합니다.

첫 번째 삼각형에 액세스합니다.

DT(1,:)
ans = 1×3

   230   205   152

첫 번째 삼각형의 첫 번째 꼭짓점을 검토합니다.

DT(1,1)
ans = 230

삼각분할의 모든 삼각형을 검토합니다.

DT(:,:);

delaunayTriangulation 출력 인수 DT의 요소를 참조하는 것은 delaunay의 삼각분할 배열 출력값의 요소를 참조하는 것과 같은 방식으로 동작합니다. 이 두 인덱싱의 차이점은 DT에서 호출할 수 있는 추가 메서드(예: nearestNeighbor와 pointLocation)에 있습니다.

triplot을 사용하여 delaunayTriangulation을 플로팅합니다. triplot 함수는 delaunayTriangulation 메서드가 아니지만, delaunayTriangulation을 받고 이를 플로팅할 수 있습니다.

triplot(DT); 
axis equal
xlabel('Longitude'), ylabel('Latitude')
grid on

Figure contains an axes object. The axes object with xlabel Longitude, ylabel Latitude contains an object of type line.

또는 triplot(DT(:,:), DT.Points(:,1), DT.Points(:,2));를 사용하여 동일한 플롯을 얻을 수도 있습니다.

delaunayTriangulation 메서드인 convexHull을 사용하여 볼록 껍질을 계산하고 이를 플롯에 추가합니다. 이미 들로네 삼각분할이 있으므로, 이 메서드를 사용하면 convhull을 사용하여 전체를 계산하는 것보다 더 효율적으로 볼록 껍질을 도출할 수 있습니다.

hold on
k = convexHull(DT);
xHull = DT.Points(k,1);
yHull = DT.Points(k,2);
plot(xHull,yHull,'r','LineWidth',2); 
hold off

Figure contains an axes object. The axes object with xlabel Longitude, ylabel Latitude contains 2 objects of type line.

delaunayTriangulation을 점진적으로 편집하여 점을 추가하거나 제거할 수 있습니다. 기존 삼각분할에 점을 추가해야 하는 경우, 늘어난 점 집합을 완전히 다시 삼각분할하는 것보다 점을 점진적으로 추가하는 것이 더 빠릅니다. 제거할 점의 개수가 기존의 점 개수에 비해 상대적으로 적을 경우에는 점을 점진적으로 제거하는 것이 더 효율적입니다.

삼각분할을 편집하여 이전 계산에서 볼록 껍질 상의 점들을 제거합니다.

figure
plot(xHull,yHull,'r','LineWidth',2); 
axis equal
xlabel('Longitude'),ylabel('Latitude')
grid on

% The convex hull topology duplicates the start and end vertex.
% Remove the duplicate entry.
k(end) = [];

% Now remove the points on the convex hull.
DT.Points(k,:) = []
DT = 
  delaunayTriangulation with properties:

              Points: [274x2 double]
    ConnectivityList: [528x3 double]
         Constraints: []


% Plot the new triangulation.
hold on
triplot(DT); 
hold off

Figure contains an axes object. The axes object with xlabel Longitude, ylabel Latitude contains 2 objects of type line.

볼록 껍질의 경계 바로 안쪽에 제거되지 않은 꼭짓점 한 개가 있습니다. Figure에서 확대 툴을 사용하여 이 꼭짓점이 볼록 껍질의 안쪽에 있음을 확인할 수 있습니다. 꼭짓점 레이블을 플로팅하여 이 꼭짓점의 인덱스를 확인한 후 삼각분할에서 제거할 수 있습니다. 또는 nearestNeighbor 메서드를 사용하여 인덱스를 더 쉽게 식별할 수도 있습니다.

이 점은 위치 (211.6, -48.15)에 근접해 있습니다. nearestNeighbor 메서드를 사용하여 가장 가까이 있는 꼭짓점을 찾습니다.

vertexId = nearestNeighbor(DT, 211.6, -48.15)
vertexId = 50

이제 삼각분할에서 이 꼭짓점을 제거합니다.

DT.Points(vertexId,:) = []
DT = 
  delaunayTriangulation with properties:

              Points: [273x2 double]
    ConnectivityList: [525x3 double]
         Constraints: []

새로운 삼각분할을 플로팅합니다.

figure
plot(xHull,yHull,'r','LineWidth',2); 
axis equal
xlabel('Longitude'),ylabel('Latitude')
grid on
hold on
triplot(DT); 
hold off

Figure contains an axes object. The axes object with xlabel Longitude, ylabel Latitude contains 2 objects of type line.

기존 삼각분할에 점을 추가합니다. 삼각분할 둘레에 사각형을 형성하도록 4개의 점을 추가합니다.

Padditional = [210.9 -48.5; 211.6 -48.5; ...
     211.6 -47.9; 210.9 -47.9];
DT.Points(end+(1:4),:) = Padditional
DT = 
  delaunayTriangulation with properties:

              Points: [277x2 double]
    ConnectivityList: [548x3 double]
         Constraints: []

기존 Figure를 모두 닫습니다.

close all

새로운 삼각분할을 플로팅합니다.

figure
plot(xHull,yHull,'r','LineWidth',2); 
axis equal
xlabel('Longitude'),ylabel('Latitude')
grid on
hold on
triplot(DT); 
hold off

Figure contains an axes object. The axes object with xlabel Longitude, ylabel Latitude contains 2 objects of type line.

삼각분할의 점을 편집하여 새 위치로 이동할 수 있습니다. 추가된 점 집합의 첫 번째 점(꼭짓점 ID 274)을 편집합니다.

DT.Points(274,:) = [211 -48.4];

기존 Figure를 모두 닫습니다.

close all

새로운 삼각분할을 플로팅합니다.

figure
plot(xHull,yHull,'r','LineWidth',2); 
axis equal
xlabel('Longitude'),ylabel('Latitude')
grid on
hold on
triplot(DT); 
hold off

Figure contains an axes object. The axes object with xlabel Longitude, ylabel Latitude contains 2 objects of type line.

triangulation 클래스의 메서드인 vertexAttachments를 사용하여 꼭짓점에 연결된 삼각형을 찾습니다. 꼭짓점에 연결된 삼각형의 개수는 가변적이므로, 이 메서드는 연결된 삼각형 ID를 셀형 배열로 반환합니다. 내용을 추출하려면 중괄호가 필요합니다.

attTris = vertexAttachments(DT,274);
hold on
triplot(DT(attTris{:},:),DT.Points(:,1),DT.Points(:,2),'g')
hold off

Figure contains an axes object. The axes object with xlabel Longitude, ylabel Latitude contains 3 objects of type line.

delaunayTriangulation을 사용하여 3차원 공간의 점을 삼각분할할 수도 있습니다. 결과로 생성되는 삼각분할은 사면체로 구성됩니다.

이 예제에서는 delaunayTriangulation을 사용하여 3차원 점의 삼각분할을 만들고 플로팅하는 방법을 보여줍니다.

rng('default')
P = rand(30,3);
DT = delaunayTriangulation(P)
DT = 
  delaunayTriangulation with properties:

              Points: [30x3 double]
    ConnectivityList: [102x4 double]
         Constraints: []


faceColor  = [0.6875 0.8750 0.8984];
tetramesh(DT,'FaceColor', faceColor,'FaceAlpha',0.3);

Figure contains an axes object. The axes object contains 102 objects of type patch.

tetramesh 함수는 삼각분할의 내부 면과 외부 면을 모두 플로팅합니다. 큰 3차원 삼각분할의 경우에는 내부 면을 플로팅하는 것이 불필요하게 리소스를 사용하는 것이 될 수 있습니다. 이때는 경계를 플로팅하는 것이 더 적절할 수 있습니다. freeBoundary 메서드를 사용하면 경계 삼각분할을 행렬 형식으로 가져올 수 있습니다. 그런 다음 이 결과값을 trimesh나 trisurf에 전달합니다.

제약 조건이 적용되는 들로네 삼각분할(Constrained Delaunay Triangulation)

delaunayTriangulation 클래스를 사용하면 2차원 삼각분할에서 모서리에 제약 조건을 적용할 수 있습니다. 즉, 삼각분할에서 한 쌍의 점을 선택하고 이들 점을 연결하도록 모서리에 제약 조건을 적용할 수 있습니다. 이 작업은 여러 쌍의 점을 잇는 모서리를 "강제"하는 것으로 간주할 수 있습니다. 다음 예제에서는 모서리 제약 조건이 삼각분할에 영향을 미칠 수 있는 방법을 보여줍니다.

아래에 나와 있는 삼각분할은 빈 외접원 기준(Empty Circumcircle Criterion)을 따르므로 들로네 삼각분할입니다.

Delaunay triangulation with circumcircles plotted.

꼭짓점 V1과 V3 사이에 모서리 제약 조건이 지정된 점 집합을 삼각분할합니다.

점 집합을 정의합니다.

P = [2 4; 6 1; 9 4; 6 7];

V1과 V3 사이의 제약 조건 C를 정의합니다.

C = [1 3];
DT = delaunayTriangulation(P,C);

삼각분할을 플로팅하고 주석을 추가합니다.

triplot(DT)

% Label the vertices.
hold on
numvx = size(P,1);
vxlabels = arrayfun(@(n) {sprintf('V%d', n)}, (1:numvx)');
Hpl = text(P(:,1)+0.2, P(:,2)+0.2, vxlabels, 'FontWeight', ...
  'bold', 'HorizontalAlignment','center', 'BackgroundColor', ...
  'none');
hold off


% Use the incenters to find the positions for placing triangle labels on the plot.
hold on
IC = incenter(DT);
numtri = size(DT,1);
trilabels = arrayfun(@(P) {sprintf('T%d', P)}, (1:numtri)');
Htl = text(IC(:,1),IC(:,2),trilabels,'FontWeight','bold', ...
'HorizontalAlignment','center','Color','blue');
hold off

% Plot the circumcircle associated with the triangle, T1.
hold on
[CC,r] = circumcenter(DT);
theta = 0:pi/50:2*pi;
xunit = r(1)*cos(theta) + CC(1,1);
yunit = r(1)*sin(theta) + CC(1,2);
plot(xunit,yunit,'g');
axis equal
hold off

Figure contains an axes object. The axes object contains 8 objects of type line, text.

꼭짓점 (V1, V3) 사이의 제약 조건이 적용된 반면 들로네 기준은 무효화되었습니다. 이 경우 들로네 삼각분할에 내재하는 최근접이웃 관계도 무효화됩니다. 즉, 삼각분할에 제약 조건이 있는 경우에는 delaunayTriangulation에서 제공하는 nearestNeighbor 탐색 메서드가 지원되지 않는다는 의미입니다.

일반적인 응용 사례에서, 삼각분할이 많은 점들로 구성되어 있고 상대적으로 적은 수의 모서리에 제약 조건이 적용되었을 수 있습니다. 이러한 삼각분할은 국소적으로 들로네 삼각분할이 아닌 것으로 간주됩니다. 왜냐하면 이 삼각분할의 많은 삼각형들은 들로네 기준을 따르는 반면 국소적으로 이 기준을 따르지 않는 삼각형도 일부 있을 수 있기 때문입니다. 많은 응용 사례에서 빈 외접원 특성이 국소적으로 완화되는 것은 문제가 되지 않습니다.

제약 조건이 적용된 삼각분할은 일반적으로 비볼록 다각형을 삼각분할하는 데 사용됩니다. 제약 조건을 통해 다각형 모서리와 삼각분할 모서리를 일치시킬 수 있습니다. 이 관계를 사용하여 다각형 영역을 나타내는 삼각분할을 추출할 수 있습니다. 다음 예제에서는 제약 조건이 적용된 delaunayTriangulation을 사용하여 비볼록 다각형을 삼각분할하는 방법을 보여줍니다.

다각형을 정의하고 플로팅합니다.

figure()
axis([-1 17 -1 6]);
axis equal
P = [0 0; 16 0; 16 2; 2 2; 2 3; 8 3; 8 5; 0 5];
patch(P(:,1),P(:,2),'-r','LineWidth',2,'FaceColor',...
     'none','EdgeColor','r');
 
% Label the points.
hold on
numvx = size(P,1);
vxlabels = arrayfun(@(n) {sprintf('P%d', n)}, (1:numvx)');
Hpl = text(P(:,1)+0.2, P(:,2)+0.2, vxlabels, 'FontWeight', ...
  'bold', 'HorizontalAlignment','center', 'BackgroundColor', ...
  'none');
hold off

Figure contains an axes object. The axes object contains 9 objects of type patch, text.

삼각분할을 만들고 다각형 경계와 함께 플로팅합니다.

figure()
subplot(2,1,1);
axis([-1 17 -1 6]);
axis equal

P = [0 0; 16 0; 16 2; 2 2; 2 3; 8 3; 8 5; 0 5];
DT = delaunayTriangulation(P);
triplot(DT)
hold on; 
patch(P(:,1),P(:,2),'-r','LineWidth',2,'FaceColor',...
     'none','EdgeColor','r');
hold off

% Plot the standalone triangulation in a subplot.
subplot(2,1,2);
axis([-1 17 -1 6]);
axis equal
triplot(DT)

Figure contains 2 axes objects. Axes object 1 contains 2 objects of type line, patch. Axes object 2 contains an object of type line.

일부 삼각형이 다각형 경계를 가로지르기 때문에 이 삼각분할을 사용해서는 다각형 영역을 나타낼 수 없습니다. 삼각분할 모서리에 의해 잘리는 모서리에 제약 조건을 적용해야 합니다. 모든 모서리를 유지해야 하므로 모든 모서리에 제약 조건을 적용해야 합니다. 아래 단계에서는 모든 모서리에 제약 조건을 적용하는 방법을 보여줍니다.

제약 조건이 적용되는 모서리 정의를 입력합니다. 주석이 있는 Figure에서 제약 조건이 필요한 위치를 살펴봅니다((V1, V2) 사이, (V2, V3) 사이 등).

C = [1 2; 2 3; 3 4; 4 5; 5 6; 6 7; 7 8; 8 1];

일반적으로, 다각형 경계를 정의하는 연속적인 N개의 점이 있는 경우 제약 조건은 C = [(1:(N-1))' (2:N)'; N 1];로 표현할 수 있습니다.

delaunayTriangulation을 만들 때 제약 조건을 지정합니다.

DT = delaunayTriangulation(P,C);

또는 Constraints 속성을 설정(DT.Constraints = C;)하여 기존 삼각분할에 제약 조건을 적용할 수도 있습니다.

삼각분할과 다각형을 플로팅합니다.

figure('Color','white')
subplot(2,1,1);
axis([-1 17 -1 6]);
axis equal
triplot(DT)
hold on; 
patch(P(:,1),P(:,2),'-r','LineWidth',2, ...
     'FaceColor','none','EdgeColor','r'); 
hold off

% Plot the standalone triangulation in a subplot.
subplot(2,1,2);
axis([-1 17 -1 6]);
axis equal
triplot(DT)

Figure contains 2 axes objects. Axes object 1 contains 2 objects of type line, patch. Axes object 2 contains an object of type line.

위 플롯을 보면 삼각분할의 모서리가 다각형의 경계를 따르고 있습니다. 그러나 삼각분할은 다각형의 오목한 부분을 채우고 있습니다. 우리에게 필요한 것은 다각형 영역을 나타내는 삼각분할입니다. delaunayTriangulation 방법인 isInterior를 사용하여 다각형 내에 있는 삼각형을 추출할 수 있습니다. 이 메서드는 삼각형이 경계가 지정된 기하학 영역 내에 있는지 여부를 나타내는 true 값과 false 값으로 구성된 논리형 배열을 반환합니다. 이 분석은 조르당 곡선 정리(Jordan Curve Theorem)를 기반으로 하며, 모서리 제약 조건에 의해 경계가 정의됩니다. 삼각분할의 i번째 삼각형은 i번째 논리형 플래그가 true인 경우 영역 안에 있는 것으로 간주되고, 그렇지 않으면 영역 밖에 있는 것으로 간주됩니다.

이제, isInterior 메서드를 사용하여 영역 내의 삼각형들을 계산하고 플로팅합니다.

% Plot the constrained edges in red.
figure('Color','white')
subplot(2,1,1);
plot(P(C'),P(C'+size(P,1)),'-r','LineWidth', 2);
axis([-1 17 -1 6]);

% Compute the in/out status.
IO = isInterior(DT);
subplot(2,1,2);
hold on;
axis([-1 17 -1 6]);

% Use triplot to plot the triangles that are inside.
% Uses logical indexing and dt(i,j) shorthand
% format to access the triangulation.
triplot(DT(IO, :),DT.Points(:,1), DT.Points(:,2),'LineWidth', 2)
hold off;

Figure contains 2 axes objects. Axes object 1 contains 8 objects of type line. Axes object 2 contains an object of type line.

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

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

관련 항목