들로네 삼각분할

들로네 삼각분할(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®은 들로네 삼각분할을 만드는 데 사용할 수 있는 다음과 같은 두 가지 방법을 제공합니다.

  • delaunayTriangulation은 특수한 종류의 triangulation 객체를 생성합니다. 데이터에 대해 모든 들로네 쿼리뿐만 아니라 모든 삼각분할 쿼리를 수행할 수 있습니다. 더 공식적인 MATLAB 언어의 용어로 설명하면, delaunayTriangulation은 triangulation의 서브클래스입니다.

  • delaunay와 delaunayn은 기본 들로네 삼각분할 표현을 만듭니다. delaunay 함수를 사용하면 2차원 들로네 삼각분할과 3차원 들로네 삼각분할을 생성할 수 있습니다. delaunayn 함수를 사용하면 4차원 이상의 들로네 삼각분할을 생성할 수 있습니다.

팁

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

delaunayTriangulation 클래스를 사용하면 2차원과 3차원에서 들로네 삼각분할을 생성할 수 있습니다. 이 클래스는 삼각분할 기반 알고리즘을 개발하는 데 유용한 많은 메서드를 제공합니다. 이러한 클래스 메서드는 함수와 비슷하지만, delaunayTriangulation을 사용하여 생성된 삼각분할에만 사용됩니다.

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

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

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

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

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

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

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

  • 들로네 삼각분할을 사용하여 컨벡스 헐이나 보로노이 다이어그램을 구합니다.