델로네 삼각분할(Delaunay Triangulation)

Delaunay triangulation

평면상의 점 집합에 대해, 어떤 삼각형의 외접원(Circumcircle) 내부에도 다른 점이 존재하지 않도록 하는 삼각 분할입니다.

<aside> <img src="/icons/dialogue_blue.svg" alt="/icons/dialogue_blue.svg" width="40px" />

외접원(Circumcircle)이란?

• 삼각형의 세 꼭짓점을 모두 지나는 원을 그 삼각형의 외접원이라고 합니다. </aside>

보웬-왓슨(Bowyer-Watson) 알고리즘

1. 초기화
   • 전체 도메인을 포함하는 초대형 삼각형(super triangle) 생성합니다.
2. 점 추가 및 삼각형 분할
   • 각 점을 순차적으로 추가합니다.
   • 점이 포함된 삼각형을 3개의 새로운 삼각형으로 분할합니다.
3. 외접원 검사 및 대각선 교환
   • 새로 생성된 삼각형의 외접원 내부에 다른 점이 있는지 확인합니다.
   • 조건을 위반하는 경우, 대각선을 교환하여 삼각형 재구성합니다.
   • 모든 삼각형이 델로네 조건을 만족할 때까지 반복합니다.
4. 반복
   • 모든 점에 대해 반복 처리합니다.
5. 마무리
   • 초대형 삼각형과 연결된 삼각형들 제거합니다.
   • 델로네 삼각분할이 완료되면, 외곽 삼각형들의 외부 경계가 자동으로 컨벡스 헐(Convex Hull )을 형성합니다.

아이디어

델로네 삼각화는 각 삼각형의 외접원 내부에 다른 점이 없다는 특성을 통해, 최대한 정삼각형에 가까운 형태로 메시가 생성됩니다.