들로네 삼각분할 (Delaunay Triangulation)

개념 설명

---

임의의 점들을 삼각형의 형태로 연결하는 분할로, 각각의 삼각형의 내각 중 최대값이 최소값이 되도록 분할하는 방식이다.

해당 분할을 통해서 최대한 정삼각형에 가까운 삼각형의 형태로 삼각분할을 할 수 있어,

비교적 고른 형태(거리가 가까운 점들끼리 연결)로 점들을 연결할 수 있다.

 

각각의 삼각형에 외접하는 외접원은 삼각형에 해당하는 점들을 제외한 다른 임의점이 속하지 않는 특징을 가진다.

 

임의점들을 가지고 평면을 구성할 수 있기에 영상처리 기법에 많이 사용된다.

---

 

들로네 삼각분할 구현

---

 들로네 삼각분할을 구현하는 알고리즘에는 여러 가지 방법이 있다.

 

- Incremental 알고리즘

사각형을 삼각형으로 나누는 분할 2가지 중 한 가지는 무조건 들로네 삼각분할 법칙을 만족하는 특성을 이용

 

- Divide and Conquer 알고리즘

점들을 직선의 경계로 두 그룹으로 나누는 작업을 반복, 각 그룹에 속한 점의 개수가 3개 이하일 때까지 분할 반복, 분할을 완료한 그룹에서부터 삼각분할을 진행, 그룹들을 서로 합쳐가면서 삼각분할을 진행한다.

 

- Flip 알고리즘

- Sweephull 알고리즘

 

이 중에서 가장 대중적으로 사용중인 Incremental 알고리즘에 대해 자세히 알아봤다.

 

Incremental 알고리즘  [속도 : O(nlogn)]

기본적인 구조는 사각형을 삼각형으로 나누는 분할 2가지 중 한가지는 무조건 들로네 삼각분할 법칙을 만족하는 특성을 이용하여, 점을 이어 삼각형을 만들고, 들로네 삼각분할 조건이 맞는지를 확인하고 맞지 않는 경우 해당 삼각형을 다시 삼각분할 진행하는 방식이다.

 

1. 모든 임의점을 포함하는 가상의 SuperTriangle을 만든다.

 

Incremental 알고리즘은 들로네 삼각분할을 반복하면서 조건을 만족하지 않는 삼각형은 다시 쪼개는 과정을 반복하여 들로네 삼각분할을 완성하는 구조이다. 해당 구조를 시작하기 위해 삼각분할이 됐다 생각한 SuperTriangle을 만들어주어 루프를 시작한다.

 

2. 임의의 점을 하나씩 선택하며 들로네 삼각분할의 조건을 검사한다.

 

임의로 선택된 점이 상위 단계에서 분해되어 존재하는(첫 번째의 경우 SuperTriangle) 삼각형의 외접원 안에 존재하는지 여부를 확인한다. 만약 해당 점이 삼각형의 외접원 안에 존재한다면 들로네 삼각분할의 조건을 만족하지 않는 것이므로 다음 단계로 넘어간다.

 

외접원 안에 노란색 점이 존재하기 때문에 삼각분할 만족X

 

3. 외접원이 임의의 점을 포함하는 삼각형을 삭제하고 다시 분할을 진행한다.

 

들로네 삼각분할을 만족하지 않는 삼각형이 생겼기 때문에 해당 삼각형을 삭제하고 다시 분할을 진행한다. 지운 삼각형의 꼭지점으로부터 조건에 맞지 않았던 점에 선을 이어 새로운 삼각분할을 형성한다. (이때 주의할 점은 새로 분할된 삼각형의 외접원은 전에 이미 그렸던 점을 포함하지 않아야 한다.)

 

새로 이은 라인 - 파란색 선

 

4. 과정을 반복하여 모든 점에 대한 조건을 만족하는 삼각형 그룹을 형성한다.

 

위의 과정들을 반복하여 모든 점에 대한 조건을 만족하는 삼각형 그룹을 형성한다. 

2개의 삼각형이 삼각분할을 만족하지 못함

 

2개의 삼각형 삭제 후 꼭지점으로 선 연결

 

모든 점에 대한 과정 반복

 

5. SuperTriangle의 꼭지점 중 하나를 끝점으로 가지는 선을 모두 제거한다.

 

SuperTriangle은 해당 알고리즘을 시작하기 위해 생성한 가상의 삼각형이므로 해당 삼각형과 관련된 삼각분할들을 모두 제거한다. 제거하는 과정을 마치면 원하는 임의의 점에 관련된 삼각분할의 과정이 완료된다.

 

완료된 들로네 삼각분할