Main Content

삼각분할 표현(Triangulation Representation)

2차원 영역과 3차원 영역

삼각분할은 컴퓨터 그래픽스, 물리 모델링, 지리 정보 시스템, 의료 영상 처리 등의 응용 분야에서 2차원 기하학 영역과 3차원 기하학 영역을 나타내는 데 주로 사용됩니다. 여기에 나와 있는 지도 다각형은

Plot of land mass with a rough border.

아래에 나와 있는 지도처럼 삼각분할로 표현될 수 있습니다.

Plot of a land mass with a rough border that has triangles of various sizes superimposed.

삼각분할은 복잡한 다각형을 보다 단순한 삼각 다각형 모음으로 분해합니다. 기하학 기반 알고리즘이나 그래픽스 애플리케이션을 개발하는 데 이들 다각형을 사용할 수 있습니다.

마찬가지로, 삼각분할을 사용하여 3차원 기하학 영역의 경계를 나타낼 수 있습니다. 아래 그림은 점 집합의 볼록 껍질(Convex Hull)을 3차원 공간에 보여줍니다. 껍질의 각 패싯은 삼각형입니다.

Plot of 3-D shape boundary formed by triangles of various sizes.

삼각분할 행렬 형식

MATLAB®은 행렬 형식을 사용하여 삼각분할을 나타냅니다. 이 형식은 두 부분으로 구성됩니다.

  • 꼭짓점을 나타내는 행렬. 행렬의 각 행이 삼각분할의 점 좌표를 나타냅니다.

  • 삼각분할 연결을 나타내는 행렬. 행렬의 각 행이 삼각형이나 사면체를 정의합니다.

다음 그림은 단순한 2차원 삼각분할을 보여줍니다.

Plot of triangulation consisting of six vertices and four triangles, with each vertex and triangle labeled.

다음 표에는 꼭짓점 정보가 나와 있습니다.

꼭짓점
꼭짓점 IDx좌표y좌표
V12.58.0
V26.58.0
V32.55.0
V46.55.0
V51.06.5
V68.06.5

위 표에 나와 있는 데이터는 MATLAB 환경에서 행렬로 저장됩니다. 꼭짓점 ID는 특정 꼭짓점을 식별하기 위해 사용되는 레이블입니다. 이 데이터는 꼭짓점 ID의 개념을 설명하기 위해 여기에 나와 있지만, 명시적으로 저장되지는 않습니다. 대신, 행렬의 행 번호가 꼭짓점 ID로 사용됩니다.

아래 표에는 삼각분할 연결 데이터가 나와 있습니다.

연결
삼각형 ID경계 꼭짓점의 ID
T1531
T2321
T3342
T4462

이 표에 나와 있는 데이터는 MATLAB 환경에서 행렬로 저장됩니다. 삼각형 ID는 특정 삼각형을 식별하는 데 사용되는 레이블입니다. 이 데이터는 삼각형 ID의 개념을 설명하기 위해 여기에 나와 있지만, 명시적으로 저장되지는 않습니다. 대신, 행렬의 행 번호가 삼각형 ID로 사용됩니다.

삼각형 T1이 3개의 꼭짓점 {V5, V3, V1}로 정의된 것을 볼 수 있습니다. 이와 유사하게, T4는 꼭짓점 {V4, V6, V2}로 정의됩니다. 이 형식은 더 높은 차원에도 적용되며 필요한 데이터 열이 자연스럽게 추가됩니다. 예를 들어, 3차원 공간의 사면체는 각각 3개의 좌표(x, y, z)를 가지는 4개의 꼭짓점으로 정의됩니다.

MATLAB을 사용하여 다음과 같은 삼각분할 유형을 나타내고 쿼리할 수 있습니다.

  • 꼭짓점과 모서리로 경계가 지정된 삼각형으로 구성된 2차원 삼각분할

  • 꼭짓점과 모서리로 경계가 지정된 삼각형으로 구성된 3차원 곡면 삼각분할

  • 꼭짓점, 모서리, 면으로 경계가 지정된 사면체로 구성된 3차원 삼각분할

삼각분할 클래스를 사용하여 삼각분할 쿼리하기

행렬 형식은 삼각분할에 대한 로우 레벨, 배열 기반의 간결한 표현을 제공합니다. 삼각분할을 사용하여 알고리즘을 개발할 때에는 기하학적 특성, 위상, 인접성 정보에 대해 추가 정보가 필요할 수 있습니다.

예를 들어, 아래에 나와 있는 주석이 있는 삼각분할을 플로팅하기 전에 삼각형 내심을 계산해야 할 수 있습니다. 이 경우, 내심을 사용하여 각 삼각형 내에서 삼각형 레이블(T1, T2 등)을 표시합니다. 경계를 빨간색으로 플로팅하려면 하나의 삼각형에서만 참조되는 모서리를 확인해야 합니다.

Triangulation consisting of six vertices and four triangles, with the outer border outlined in red.

triangulation 클래스

triangulation을 사용하여 2차원 또는 3차원 삼각분할 데이터의 메모리 내 표현(In-memory Representation)을 만들 수 있습니다. 이 표현은 delaunay 함수나 기타 소프트웨어 툴이 반환하는 행렬 출력값과 같은 행렬 형식을 가집니다. triangulation으로 데이터가 표현되면 기하학 알고리즘을 개발하는 데 사용할 수 있는 위상 쿼리와 기하학 쿼리를 수행할 수 있습니다. 예를 들어, 모서리, 외심, 기타 특징을 공유하는, 꼭짓점에 연결되는 삼각형이나 사면체를 구할 수 있습니다.

다음 두 가지 방법 중 하나로 triangulation을 만들 수 있습니다.

  • 행렬 형식으로 가지고 있는 기존 데이터를 triangulation에 전달합니다. 이 데이터는 delaunayconvhull과 같은 MATLAB 함수의 출력값일 수 있습니다. 또한 다른 소프트웨어 애플리케이션에서 만든 삼각분할 데이터를 가져올 수도 있습니다. 가져온 데이터를 사용하여 작업할 경우, 연결 데이터는 0 기반 인덱싱이 아닌 1부터 시작하는 인덱싱을 사용하여 꼭짓점 배열을 참조해야 합니다.

  • 점 집합을 delaunayTriangulation에 전달합니다. 결과로 생성되는 들로네 삼각분할은 특수한 종류의 triangulation입니다. 즉, 데이터에 대해 모든 triangulation 쿼리뿐만 아니라 모든 들로네 쿼리를 수행할 수 있습니다. MATLAB 언어 측면에서 보면, delaunayTriangulationtriangulation의 서브클래스입니다.

행렬 데이터에서 삼각분할 생성하기

이 예제에서는 삼각분할 행렬 데이터를 사용하여 삼각분할을 만들고, 삼각분할이 무엇인지 살펴보고, 삼각분할이 수행할 수 있는 작업을 살펴보는 방법을 보여줍니다.

꼭짓점 데이터를 포함하는 행렬 P를 만듭니다.

P = [ 2.5    8.0
      6.5    8.0
      2.5    5.0
      6.5    5.0
      1.0    6.5
      8.0    6.5];

연결 T를 정의합니다.

T = [5  3  1;
     3  2  1;
     3  4  2;
     4  6  2];

이 데이터에서 triangulation을 만듭니다.

TR = triangulation(T,P)
TR = 
  triangulation with properties:

              Points: [6x2 double]
    ConnectivityList: [4x3 double]

struct의 필드에 액세스하는 것과 동일한 방법으로 triangulation의 속성에 액세스합니다. 예를 들어, 꼭짓점 좌표가 들어 있는 Points 속성을 검토합니다.

TR.Points
ans = 6×2

    2.5000    8.0000
    6.5000    8.0000
    2.5000    5.0000
    6.5000    5.0000
    1.0000    6.5000
    8.0000    6.5000

다음으로, 연결을 검토합니다.

TR.ConnectivityList
ans = 4×3

     5     3     1
     3     2     1
     3     4     2
     4     6     2

Points 속성과 ConnectivityList 속성은 삼각분할의 행렬 데이터를 정의합니다.

triangulation 클래스는 행렬 데이터에 대한 래퍼입니다. 실제 이점은 triangulation 클래스 메서드의 유용성입니다. 이 메서드는 triangulation과 기타 관련 입력 데이터를 받는 함수와 유사합니다.

triangulation 클래스는 ConnectivityList 속성 행렬의 요소를 참조할 수 있는 쉬운 방법을 제공합니다. 삼각분할의 첫 번째 삼각형에 액세스합니다.

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

     5     3     1

첫 번째 삼각형에 액세스할 수 있는 또 다른 방법은 TR(1,:)입니다.

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

TR(1,1)
ans = 5

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

TR(1,2)
ans = 3

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

TR(:,:)
ans = 4×3

     5     3     1
     3     2     1
     3     4     2
     4     6     2

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

figure
triplot(TR)
axis equal

Figure contains an axes object. The axes object contains an object of type line.

triangulation 메서드 freeBoundary를 사용하여 자유 경계를 쿼리하고 플롯에서 이를 강조 표시합니다. 이 메서드는 하나의 삼각형에서만 공유되는 삼각분할의 모서리를 반환합니다. 반환되는 모서리는 꼭짓점 ID로 표현됩니다.

boundaryedges = freeBoundary(TR)';

이제, 경계 모서리를 빨간색 선으로 플로팅합니다.

hold on 
plot(P(boundaryedges,1),P(boundaryedges,2),'-r','LineWidth',2)
hold off

Figure contains an axes object. The axes object contains 2 objects of type line.

freeBoundary 메서드를 사용하여 삼각분할을 검증할 수 있습니다. 예를 들어, 삼각분할 내부에서 빨간색 모서리를 관찰한 경우 이는 삼각형이 연결된 방식에 문제가 있음을 나타낼 수 있습니다.

delaunayTriangulation을 사용하여 삼각분할 만들기

이 예제에서는 delaunayTriangulation을 사용하여 들로네 삼각분할을 만드는 방법을 보여줍니다.

delaunayTriangulation 클래스는 triangulation의 서브클래스이므로 delaunayTriangulation 클래스를 사용하여 들로네 삼각분할을 만들면 triangulation 메서드에 대한 액세스 권한이 자동으로 부여됩니다.

점 집합에서 delaunayTriangulation을 만듭니다.

P = [ 2.5    8.0
      6.5    8.0
      2.5    5.0
      6.5    5.0
      1.0    6.5
      8.0    6.5];

DT = delaunayTriangulation(P)
DT = 
  delaunayTriangulation with properties:

              Points: [6x2 double]
    ConnectivityList: [4x3 double]
         Constraints: []

결과로 생성되는 delaunayTriangulation 객체는 triangulation 객체와 마찬가지로 속성 PointsConnectivityList를 가집니다.

triangulation과 같이 직접 인덱싱을 사용하여 삼각분할에 액세스할 수 있습니다. 예를 들어, 첫 번째 삼각형의 연결을 검토합니다.

DT(1,:)
ans = 1×3

     5     3     1

다음으로, 전체 삼각분할의 연결을 검토합니다.

DT(:,:)
ans = 4×3

     5     3     1
     3     4     1
     1     4     2
     2     4     6

triplot 함수를 사용하여 삼각분할을 플로팅합니다.

triplot(DT)
axis equal

Figure contains an axes object. The axes object contains an object of type line.

부모 클래스 triangulation은 각 삼각형의 내심을 구하는 incenter 메서드를 제공합니다.

IC = incenter(DT)
IC = 4×2

    1.8787    6.5000
    3.5000    6.0000
    5.5000    7.0000
    7.1213    6.5000

반환된 값 IC는 삼각형의 내심을 나타내는 좌표로 구성된 배열입니다.

이제, 내심을 사용하여 플롯에 삼각형 레이블을 배치할 위치를 찾습니다.

hold on
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

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

delaunayTriangulation을 사용하여 들로네 삼각분할을 만드는 대신, delaunay 함수를 사용하여 삼각분할 연결 데이터를 만들고 이 연결 데이터를 triangulation에 전달할 수 있습니다. 예를 들면 다음과 같습니다.

P = [ 2.5    8.0
      6.5    8.0
      2.5    5.0
      6.5    5.0
      1.0    6.5
      8.0    6.5];

T = delaunay(P);
TR = triangulation(T,P);
IC = incenter(TR);

두 접근 방식 모두 이 예제에서 유효하지만, 들로네 삼각분할을 만들고 이에 대한 쿼리를 수행하려는 경우에는 delaunayTriangulation을 사용해야 합니다. 그 이유는 다음과 같습니다.

  • delaunayTriangulation 클래스는 삼각분할 작업에 유용한 추가 메서드를 제공합니다. 예를 들어, 최근접이웃 탐색과 PIT(Point-In-Triangle) 탐색을 수행할 수 있습니다.

  • 이 클래스를 사용하면 삼각분할을 편집하여 점을 추가, 이동, 제거할 수 있습니다.

  • 이 클래스를 사용하면 제약 조건이 적용되는 들로네 삼각분할을 만들 수 있습니다. 또한, 2차원 영역 삼각분할을 만들 수 있습니다.

참고 항목

| | | |

관련 항목