[3D CV] Delaunay triangulation

Delaunay Triangulation Youtube Explanation

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

들로네 삼각분할은 이러한 여러 삼각분할 중에서 각각의 삼각형들이 최대한 정삼각형에 가까운 즉, 길쭉하고 홀쭉한 삼각형이 나오지 않도록 하는 분할을 말합니다.

Delaunay triangulation is used for creating triangular meshes given a set of points.

들로네 삼각분할 활용

Nearest Neighbor 구하기

어떤 점들의 집합에 대한 들로네 삼각분할이 있으면 nearest neighbor를 곧바로 구할 수 있게 됩니다.

예를 들어, 아래 그림에서 p의 nearest neighbor를 구하고 싶으면 점 p와 연결된 edge들만 조사하면 이들 중에 nearest neighbor가 존재하게 됩니다.

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

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

Reconstruction

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

---

들로네 삼각분할 조건

들로네 삼각분할에서는 삼각형의 외접원(삼각형을 포함하는 원, Circumcircle) 안에 다른 삼각형의 꼭짓점이 위치하지 않아야 하는 조건이 있습니다.

Computing Delaunay Triangulations

One way to compute the triangualation is the Bowyer-Watson algorithm.

최종적으로 아래와 같은 결과를 얻습니다. (자세한 알고리즘은 포스트 상단 유튜브 영상을 참고하세요.)