델로네 삼각분할
- 세 개 이상의 주어진 점의 개수 만큼 회색면 위에 무작위로 점이 만들어진다.
- 이 때, 모든 점을 둘러싸는 가장 작은 볼록 다각형이 있다. 이 다각형은 점들의 볼록 껍질(Convex hull)이다.
- 그리고, 모든 점을 삼각형의 꼭짓점으로 하여 볼록 껍질을 삼각형으로 나눌 수 있다.
- 이것을 점 집합 삼각분할(Point-set triangulation)이라 부른다.
- 특히, 삼각분할된 모든 삼각형의 각 외접원 내부에 주어진 어떤 점도 없는 경우, 그러한 다각형 삼각분할을 델로네 삼각분할(Delaunay triangulation)이라고 부른다.
알고리즘
아래의 과정을 거쳐 델로네 삼각분할을 찾는다.
- 주어진 점 중에서 세 점을 고르는 모든 경우마다 외심을 구하고 기록한다.
- 각 경우 마다 외접원 위에 있는 세 점을 제외한 다른 점과 외심까지의 거리를 재고 그 거리가 원의 반지름의 길이보다 작으면, 그 경우의 외심을 버린다.
- 남은 경우에 대하여 삼각형과 외접원을 그린다.