들로네 삼각분할(Delaunay triangulation) & 보로노이 다이어그램(Voronoi diagram)

들로네 삼각분할(Delaunay Triangulation)과 보로노이 다이어그램(Voronoi diagram)이 무엇인지? 어디에 쓰이는지? 그리고 어떻게 구하는지에 대한 글입니다.

1. 참고 문헌(자료)

참고한 주요 자료들입니다.

[1] 위키피디아(Wikipedia): Delaunay triangulation, Voronoi diagram

[2] Steve Oudot의 그래픽스 강의자료: Delaunay Triangulation I & II (강추)

[3] O'Reilly, Learning OpenCV

2. 용어

Delaunay triangulation은 들로네 삼각분할, 들로네 삼각망, 들로네 삼각형 등으로 불리며 Voronoi diagram(보로노이 다이어그램)은 Voronoi tessellation(보로노이 테셀레이션), Voronoi decomposition, Voronoi partition라고도 불립니다.

3. 들로네 삼각분할(Delaunay triangulation)이란?

들로네 삼각분할은 평면위의 점들을 삼각형으로 연결하여 공간을 분할할 때, 이 삼각형들의 내각의 최소값이 최대가 되도록 하는 분할을 말합니다.

<그림 1>

예를 들어, 위 그림 (a)와 같이 점들이 있을 때 이 점들을 연결하여 삼각형을 만드는 방법은 (b), (c)와 같이 다양합니다. 들로네 삼각분할은 이러한 여러 삼각분할 중에서 (b)와 같이 각각의 삼각형들이 최대한 정삼각형에 가까운 즉, (c)와 같이 길쭉하고 홀쭉한 삼각형이 나오지 않도록 하는 분할을 말합니다.

들로네 삼각분할의 가장 중요한 특징중 하나는, "어떤 삼각형의 외접원도 그 삼각형의 세 꼭지점을 제외한 다른 어떤 점도 포함하지 않는다" 입니다 (이를 empty circumcircle property라고 부릅니다). 삼각형이 홀쭉하고 길수록 외접원도 커짐을 생각하면 됩니다. 위 그림에서 (b)는 이 조건을 만족하고 (c)는 만족하지 않음을 쉽게 확인할 수 있습니다.

4. 보로노이 다이어그램(Voronoi Diagram)이란?

보로노이 다이어그램은 어떤 시드 점(seed point)들과의 거리에 따라서 평면을 분할한 그림으로서, 평면위에 주어진 시드 점 p1, p2, ..., pn에 대한 보로노이 다이어그램은 평면위의 점들이 어떤 pi와 가장 가까운지에 따라서 영역을 분할한 다이어그램을 말합니다.

예를 들어, 아래 왼쪽 그림과 같은 사각형 공간에 10개의 시드 점 (검은색 점들)을 주면 오른쪽 그림과 같은 보로노이 다이어그램이 나옵니다.

<그림 2> 그림출처: 위키피디아[1]

쉽게 생각하면 어떤 주어진 땅이 있고 그 땅 위에 있는 10개의 국가간의 국경선을 나눈다고 했을 때, 각 지역이 어떤 나라와 가장 가까운지에 따라서 영토를 나눈 것이 보로노이 다이어그램입니다. 이러한 관점에서 보면 각각의 보로노이 영역은 각 시드 점의 세력권을 나타낸다고 볼 수 있으며 그 경계선은 힘과 힘의, 세력과 세력의 균형점을 나타낸다고 볼 수 있습니다.

5. 들로네 삼각분할과 보로노이 다이어그램의 관계

들로네 삼각분할과 보로노이 다이어그램은 서로 듀얼 이미지(dual image) 관계에 있으며 어느 하나를 알면 다른 하나도 곧바로 구할 수 있습니다.

[들로네->보로노이]

보로노이 다이어그램의 각 seed 점들을 가지고 들로네 삼각분할을 구한 후에, 구해진 삼각형들의 외접원들의 중심을 연결하면 보로노이 다이어그램이 나옵니다.

좀더 상세하게 말하면, 어떤 점을 공통의 꼭지점으로 하는 들로네 삼각형들의 외접원들의 중심을 순서대로 연결하면 이 공통점을 seed로 하는 보로노이 영역이 나옵니다.

[보로노이->들로네]

서로 인접한 보로노이 영역들간의 seed 점들을 연결하면 이 seed 점들에 대한 들로네 삼각분할이 얻어집니다.

<그림 3> 그림출처: 참고문헌 [3]

이와 같이 Delaunay triangulation과 Voronoi diagram은 서로 dual 관계에 있으며 어느 하나를 알면 다른 하나를 곧바로 구할 수 있기에 그 응용이나 계산 알고리즘도 거의 같은 거라고 생각하면 됩니다.

보로노이 다이어그램을 정의한 Voronoi와 들로네 삼각형을 고안한(1934) Delaunay 두 사람 모두 러시아 수학자입니다. 

<그림 4> 그림출처: 참고문헌 [2]

6. 자연에 존재하는 Delaunay triangulation / Voronoi diagram 예

<그림 5> 그림출처: 참고문헌 [2]

7. 응용

[데이터 클러스터링]

주어진 데이터 분포에서 유의미한 클러스터(cluster)를 뽑아내는 것은 data mining, classification 등에서 매우 어려운 문제 중 하나입니다 (특히 클러스터의 개수를 모르고 있을 때).

<그림 6> 그림출처: "an adaptive spatial clustering algorithm based on delaunay triangulation", CEUS 2011.

들로네 triangulation을 이용하면 이러한 클러스터링을 효과적으로 할 수 있는데, 먼저 데이터 점들을 Delaunay triangulation으로 연결한 후에 일정한 길이 이상의 긴 변들을 제거하고 남은 연결된 성분들을 구하면 됩니다.

[데이터 분포 밀도]

평면에 흩뿌려진 점들의 밀도를 수치화하는 용도로 사용되는 경우

<그림 7> DTFE(그림출처: 위키피디아[1])

그 방법은 어떤 점 p에서의 밀도를 점 p를 꼭지점으로 하는 주변 Delaunay 삼각형들의 면적의 합의 역수(밀도 = c/(s1+s2+...+sk))로 정의합니다. 그리고 이들 점에서의 밀도값을 보간(interpolation)함으로써 또한 공간 전체에서 밀도를 수치화하는 것입니다. 이러한 분포 밀도 수치화 방법을 Delaunay tessellation field estimator (DTFE)라고 하며, 주 응용은 우주 천체를 분석하는 용도라 합니다만 자세한 건 잘 모릅니다.

구체적인 예는 떠오르지 않지만 컴퓨터 비전에서도 나름 유용하게 활용될 수 있을 거라는 느낌이 듭니다.

[도로망 설계]

도시와 도시를 연결하는 도로망을 설계할 때, Delaunay triangulation이 하나의 참조모델로 활용될 수 있습니다.

<그림 8> 고대 로마의 도로망 (그림출처: 네이버 지식백과)

만일 n개의 도시가 있을 때 모든 도시와 도시를 직접 직선도로로 연결할 경우에는 총 nC2 = n(n-1)/2개의 도로가 필요합니다. 하지만, 모든 도시를 서로서로 직접 연결하는 것은 너무 비효율적이기 때문에 실제로는 일부 도로만을 연결하여 전체 도시들이 연결되도록 해야 할 것입니다.

이 경우 도시 A에서 도시 B로 이동할 때 직접 연결된 도로가 없다면 다른 도시들을 우회해서 이동해야 할 것입니다. 그런데, 이 때 중요한 점은 도시 A에서 도시 B로 이동하기 위해 이동한(우회한) 총 이동거리가 A-B 사이의 직선거리에 비해 최소화되도록 도로망을 설계하는 것일 것입니다.

만일 삼각분할 형태로 도로망을 설계한다고 했을 때, 들로네 삼각화를 이용하여 도로를 연결하면 우회에 따른 이동거리의 증가를 최소화할 수 있습니다.

[Minimum Spanning Tree(MST)]

Minimum Spanning Tree (MST)는 n개의 지점을 모든 점들이 서로 도달 가능하면서 전체 거리의 합이 최소가 되도록 연결한 트리 구조의 그래프입니다. MST는 주어진 지점들을 연결하는 최소 비용의 네트워크 회선망이나 파이프 망을 찾을 때 활용될 수 있습니다. 또한 잘 알려진 TSP (Traveling Salesman Problem 즉, n개의 도시를 최단 거리로 순회할 수 있는 방문 경로를 찾는 문제)도 MST를 활용하면 최적해 길이의 2배 이내에서의 근사해를 찾을 수 있습니다.

<그림 9> MST (그림출처: 위키피디아[1])

MST를 구하는데 들로네 triangulation을 활용하는 방법은, 먼저 주어진 점들에 대한 들로네 triangulation을 구하고 그 결과 그래프를 MST 구하는 알고리즘의 입력으로 사용하는 것입니다. 이렇게 하면 fully linked graph에서 직접 MST를 구하는 것보다 훨씬 효율적으로 MST를 구할 수 있게 됩니다. 단, 이는 들로네 triangulation이 항상 MST를 포함함을 전제로 하고 있는데 그 증명은 위키피디아를 참조하시기 바랍니다.

[Convex Hull 구하기]

어떤 점들의 집합에 대한 Convex Hull 이란 쉽게 생각하면 그 점들을 실로 팽팽하게 둘러쌌을 때 생기는 볼록(convex) 다각형입니다 (아래 그림에서 주황색 도형).

<그림 10>

Delaunay triangulation을 이용해서 convex hull을 구하는 방법은, 원래의 점들의 집합에 외부의 점 3개를 추가하여 들로네 삼각분할을 구한 후 어떤 점들이 새로 추가된 외부의 점과 삼각형을 이루었는지를 조사하면 됩니다. 그래서 새로 추가한 외부의 점과 삼각형을 형성한 점들을 연결하면 원래 점들에 대한 convex hull이 나옵니다. 단, 외부의 점을 잡을 때에는 원래 점들이 외부 점들을 잊는 삼각형에 모두 포함될 수 있도록 멀리 떨어진 점들로 잡아야 합니다.

[Nearest Neighbor 구하기]

어떤 점들의 집합에 대한 들로네 삼각분할이 있으면 nearest neighbor를 곧바로 구할 수 있게 됩니다. 예를 들어, 아래 그림에서 p의 nearest neighbor를 구하고 싶으면 점 p와 연결된 edge들만 조사하면 이들 중에 nearest neighbor가 존재하게 됩니다.

<그림 11> 그림출처: 참고문헌[2]

즉, 원래는 모든 점들과 일일히 거리를 비교해 봐야 하겠지만 들로네 삼각분할이 있으면 그 점과 연결된 점들과의 거리만 조사하면 된다는 의미입니다.

또한 k-nearest neighbor를 구할 때에도 들로네 삼각망에서 직접 연결된 점들로부터 시작해서 tree 형태로 점차 탐색범위를 확장해가면 됩니다.

[Reconstruction]

포인트 클라우드(point cloud)로부터 물체의 3D 입체를 모델링하여 복원할 때에도 Delaunay triangulation이 활용될 수 있습니다. 하지만 이 경우에는 삼각형은 사면체로, 원은 구로 확장된 버전의 Delaunay triangulation을 이용해야 합니다.

<그림 12> 그림출처: 참고문헌 [2]

[물체에 대한 polygon mesh 생성]

들로네 삼각분할의 본연(?)의 응용이라 볼 수 있습니다. 3D 입체 물체의 표면을 폴리곤으로 모델링할 때 들로네 triangulation을 이용하면 표면위의 점들의 집합으로부터 nice(?)한 폴리곤 메쉬를 얻을 수 있습니다. 3D 입체 표면을 폴리곤으로 모델링하는 이유는 빠른 랜더링(rendering)이 가능하기 때문입니다.

<그림 13> 그림출처: N. Aghdaii et. al., "5-6-7 Meshes," Proc. of Graphics Interface, 2012.

[3D 일러스트레이션]

Jonathan Puckey라는 사람이 2008년도에 개발한 방법으로 Delaunay Raster라는 그래픽 툴이 있습니다. 이 기법은 Delaunay triangulation을 이용하여 입력 사진으로부터 입체감을 갖는 3D 일러스트를 생성하는 것으로서, 사용자가 사진위에 입력한 점들로부터 들로네 삼각분할을 이용한 폴리곤 메쉬를 생성하고 그 색상값을 삼각형 내의 평균 색상으로 설정하는 방법입니다 (관련 URL: http://jonathanpuckey.com/projects/delaunay-raster/)

<그림 14> 그림출처: http://jonathanpuckey.com/projects/delaunay-raster/

[로봇 네비게이션]

로봇이 길을 찾고 목적지까지 이동할 때, 주변 장애물과 부딪히지 않고 안전한 길을 찾는 것이 무엇보다도 중요합니다. 보로노이 다이어그램을 이용하여 이동경로를 생성하면 공간의 가장 빈 곳을 따라서 이동하기 때문에 안전성을 확보할 수 있습니다.

<그림 15> 그림출처: 참고문헌 [2]

8. 들로네 삼각분할 알고리즘

들로네 삼각분할을 구하는 알고리즘은 크게 incremental 알고리즘과 divide and conquer 알고리즘으로 나눌 수 있습니다. 두 알고리즘의 속도는 O(n log n)이라고 합니다.

Incremental 알고리즘은 점들을 하나씩 추가해 가면서 점진적으로 분할을 완성하는 방식이고, divide & conquer 방식은 입력 점들을 recursive하게 두 그룹으로 나누고 각각의 그룹에 대한 들로네 삼각분할을 얻은 후에 다시 두 그룹을 합치는 방식입니다.

Divide & conquer 방식이 들로네 삼각분할 알고리즘 중 가장 빠른 방식이라고 합니다. 하지만 사용자와 인터렉티브하게 mesh 작업을 할 때에는 incremental 방식이 보다 적합할 것입니다.

8.1 Incremental 알고리즘

incremental 알고리즘을 이해하기 위해서는 먼저 flipping에 대해 알아야 합니다. 어떤 사각형을 대각선을 따라 두개의 삼각형으로 나누는 방법은 2가지가 있습니다. 이 때, 만일 어느 한 분할이 Delaunay 조건을 만족하지 않는다면 다른 대각선 방향으로의 분할은 반드시 Delaunay 조건을 만족하게 됩니다. 이와 같이 분할 방향을 바꾸어서 Delaunay 조건을 만족시켜 나가는 것을 flipping이라고 합니다.

<그림 16> 그림출처: 위키피디아[1]

가장 기본적인 incremental 알고리즘은 앞서 설명한 Convex Hull 구하기 응용에서처럼 먼저 원래 점들로부터 무한히 멀리 떨어진 외부의 3 점(아래 그림의 녹색 점들)을 설정한 후에, 하나씩 원래 점들을 추가하면서 Delaunay triangulation 조건을 만족하도록 삼각분할을 조정하는 형식으로 진행합니다.

<그림 16>

먼저, 현재 새로 추가된 점을 포함하는 삼각형의 세 꼭지점과 새로 추가된 점을 연결하여 새로운 분할을 만듭니다 (그림의 오렌지 색). 이후 새로 추가된 삼각형들과 맞닿은 삼각형들에 대해 차례로 flip 알고리즘을 적용하여 모든 삼각형들이 Delaunay 조건을 만족하도록 합니다 (empty circumcircle condition). 예를 들어, 위 그림에서 ABCD에 대해 조건을 검사해서 만족하지 않는다면 분할 방향을 BD에서 AC로 바꾸어 줍니다. 분할 방향이 변경된 경우에만 변경된 삼각형들과 인접한 삼각형들에 대해서 flipping 검사가 전파됩니다.

8.2 Divide and Conquer 알고리즘

Divide and conquer 방식은 원래의 입력 점들을 하나의 직선을 경계로 두 그룹으로 나누고, 각각의 그룹은 또 다른 직선으로 다시 세부 그룹으로 나누는 방식으로 recursive하게 그룹을 나누되, 각 그룹에 속한 점의 개수가 3개 이하일 때까지 분항을 진행합니다.

<그림 17> 그림출처: 참고문헌 [2]

이후, 각 그룹에서 들로네 삼각분할을 구한 후, 그룹들을 다시 합쳐나가면서 전체적으로 들로네 조건을 만족하도록 분할을 구하는 방식입니다. 두 그룹의 Delaunay 삼각분할을 합치는 세부적인 내용에 대해서는 관련 논문 등을 참고하시기 바랍니다.

☞ 참고로 저는 그래픽스 쪽 전공이 아니며 이 글에 있는 내용 이상은 잘 알지 못합니다. 한 방문자분의 요청의 의해 작성한 글로서 관련 내용이 흥미로운 점이 많아서 저도 같이 공부를 할 겸해서 작성한 글입니다.

by 다크 프로그래머