[Geometry] 1. Voronoi diagram

What is Voronoi diagram?

Wikipedia - 보로노이 다이어그램

위키피디아에 의하면, Voronoi Diagram은 평면을 특정 점까지의 거리가 가장 가까운 점의 집합으로 분할한 것이다. 

평면들에 있는 점(seed point)들 중 가장 가까운 점 2개를 모두 연결하고, 그 선들의 수직이등분선을 그어서 분할되는 것들이 보로노이 다각형(서로 다른 색으로 칠해져있는 다각형들)이다. 과정은 아래와 같은데, 여기서 점들을 연결하는 방법을 Delaunay triangulation(들로네 삼각분할)을 사용한다. 이에 대해서는 아래 section에서 설명하도록 하겠다. 

보르노이 다이어그램은, proximity information을 담고 있다. 예를 들어, 각 seed point를 도시 하나에 분포하고 있는 가게(shop)라고 하면, 이 다이어그램을 통해 "주어진 point X와 가장 가까운 가게는 어디인가?"와 같은 문제를 풀 수 있다.

 

What is Delaunay triangulation?

Wiki : Delaunay triangulation 

Delaunay triangulation(들로네 삼각분할)은, 다음의 조건을 만족하는 삼각형들의 집합을 만드는 분할이다.

• 평면위의 점들을 삼각형(simplex. 2D에서 그냥 triangle로 지칭함)으로 연결하여 공간을 분할할 때, 이 삼각형들의 내각의 최소값이 최대가 되도록 하는 분할을 말한다.

(b) O    (c) X

즉, (a)와 같이 점들이 있을 때, 이 점들을 연결하여 삼각형을 만드는 방법들이 (b), (c)와 같이 다양한데, (b)와 같이 최대한 정삼각형에 가깝도록 분할하는 기법이다. 

• 삼각형으로 이루어지는 circumsphere(외접원)의 내부에 삼각형을 이루는 세 point 외의 다른 point가 존재하지 않아야 한다. 

 

Voronoi diagram and Delaunay triangulation

보로노이 다이어그램과 들로네 삼각분할은 서로 dual image 관계에 있다. (= 하나를 알면 다른 하나도 바로 알 수 있음)

• Voronoi diagram -> Delaunay triangulation

     서로 인접한 보로노이 다이어그램의 seed point들을 연결하면 들로네 삼각분할들이 얻어진다. 

• Delaunay triangulation -> Voronoi diagram

     들로네 삼각분할로 구한 삼각형들의 외접원들의 중심을 연결해보면 보로노이 다이어그램이 나온다. 

black point : seed points,   red point : center of the circumcircle

 

https://darkpgmr.tistory.com/96 참고

 

Applications

• Convex Hull 구하기

Convex Hull이란 2차원 평면상에 점이 여러 개가 있을 때, 이 점들 중 일부를 골라서 나머지 점들을 모두 포함하는 볼록 다각형을 만드는 것을 말한다. 

(b) is the convex hull of inputs of (a)

Delaunay triangulation을 이용하여 convex hull을 구하기 위해서는, 원래의 input들의 집합에 외부의 점 3개를 추가하여 Delaunay triangulation을 구한 후 어떤 점들이 새로 추가된 외부의 점과 삼각형을 이루었는지를 조사하면 된다. 그 후, 새로 추가한 외부의 점과 삼각형을 형성한 점들을 연결하면 원래 점들에 대한 convex hell을 구할 수 있다. 

 

• 로봇 내비게이션

로봇이 길을 찾아 목적지까지 이동할 때, 주변 장애물과 부딪히지 않고 안전한 길을 찾아야 한다. 보로노이 다이어그램을 통해 이동경로를 생성하면, 공간의 가장 빈 곳을 따라 이동하기 때문에 안정성을 확보할 수 있다.

 

• OpenCV와 함께 사용한 프로젝트

https://learnopencv.com/delaunay-triangulation-and-voronoi-diagram-using-opencv-c-python/

위의 그림은 미국 전 대통령 오바마의 사진을 openCV library(Dlib)를 통해 얼굴의 특징점(Facial landmarks)이 되는 점을 찾은 것이다. 순서대로, 가운데 이미지는 이 점들을 seed point로 두고 Delauny triangulation을 구한 것이다. 오른쪽 이미지는 이에 상응하는 보로노이 다이어그램이다. Subdiv2D를 통해 Delauny triangulation이나 보로노이 다이어그램은 쉽게 구할 수 있다.