들로네 삼각분할

편집 역사 토론
수치해석 컴퓨터 그래픽스 마지막 수정: 2026-07-11 04:23:33

1. 개요[편집]

들로네 삼각분할(Delaunay triangulation)은 평면(또는 공간)에 흩어진 점 집합을 삼각형(3차원에서는 사면체)들로 이어 붙이되, 어떤 삼각형의 외접원 안에도 다른 점이 들어가지 않도록 만드는 유일한 방식의 삼각화다. 1934년 보리스 들로네(Boris Delaunay)가 정의했으며1, “될 수 있는 한 뚱뚱한(살찐) 삼각형”을 만들어 주는 성질 덕분에 격자 생성, 지형 모델링, 유한요소 메시 만들기의 기초 알고리즘으로 자리 잡았다.

핵심 매력은 이렇다. 같은 점 집합을 삼각형으로 잇는 방법은 무수히 많은데, 그중 대부분은 길고 뾰족한 “가시 삼각형(sliver)“을 만들어 수치해석을 망친다. 들로네 삼각분할은 가능한 최소각을 최대화(max-min angle) — 즉 가장 못생긴 삼각형을 최대한 덜 못생기게 만드는 유일한 선택이다. 뾰족한 삼각형이 적으면 보간과 근사의 오차도 작아지고 강성행렬의 조건수도 좋아진다.

2. 빈 원 성질[편집]

들로네 삼각분할을 규정하는 단 하나의 조건은 빈 원 성질(empty circumcircle property)이다. 삼각화에 속한 모든 삼각형에 대해, 그 세 꼭짓점을 지나는 외접원의 내부에는 다른 어떤 점도 존재하지 않아야 한다.

이 조건을 판정하는 도구가 인서클 테스트(in-circle test)다. 점 A,B,CA, B, C가 이루는 원 안에 점 DD가 들어있는지는 다음 행렬식의 부호로 정확히 판별한다.

∣Ax−DxAy−Dy(Ax−Dx)2+(Ay−Dy)2Bx−DxBy−Dy(Bx−Dx)2+(By−Dy)2Cx−DxCy−Dy(Cx−Dx)2+(Cy−Dy)2∣>0\begin{vmatrix} A_x - D_x & A_y - D_y & (A_x-D_x)^2 + (A_y-D_y)^2 \\ B_x - D_x & B_y - D_y & (B_x-D_x)^2 + (B_y-D_y)^2 \\ C_x - D_x & C_y - D_y & (C_x-D_x)^2 + (C_y-D_y)^2 \end{vmatrix} > 0

행렬식이 양수면 DD가 원 안에 있다는 뜻이고, 그러면 그 삼각형은 들로네 조건을 위반한다. 이 판정을 부동소수점 연산으로 순진하게 계산하면 거의 한 원 위에 놓인(공원, cocircular) 네 점에서 부호가 뒤집혀 알고리즘이 폭발하기 때문에2, 실무 라이브러리는 정밀 정수 산술이나 적응적 정밀도(adaptive precision) 판정을 쓴다.

3. 보로노이 쌍대[편집]

들로네 삼각분할을 이야기하면서 보로노이 다이어그램을 빼놓을 수 없다. 둘은 동전의 양면, 정확히는 쌍대(dual) 관계다.

보로노이 다이어그램은 각 점을 “가장 가까운 씨앗”으로 하는 영역(cell)들로 평면을 나눈 것이다. 여기서 다음 대응이 성립한다.

  • 보로노이 셀(영역) ↔\leftrightarrow 들로네 꼭짓점(점)
  • 보로노이 간선(두 셀의 경계) ↔\leftrightarrow 들로네 간선(두 점을 잇는 변)
  • 보로노이 꼭짓점(세 셀이 만나는 점) ↔\leftrightarrow 들로네 삼각형

즉 두 점이 보로노이 셀을 맞대고 있으면(이웃이면) 들로네 삼각분할에서 변으로 연결된다. 실제로 들로네 삼각형의 외접원 중심이 바로 보로노이 꼭짓점이다. 그래서 한쪽을 계산하면 다른 쪽은 공짜로 따라 나온다.3 이 쌍대성은 FLIP/PIC 유체나 유한체적 셀 구성, 지리정보 시스템의 최근접 질의 등에서 두루 활용된다.

4. 대표 알고리즘[편집]

점 집합으로부터 들로네 삼각분할을 실제로 구성하는 알고리즘은 여러 갈래가 있다.

  • 점진적 삽입(incremental insertion): 점을 하나씩 넣으면서, 새 점의 외접원 조건을 깨는 삼각형들을 지우고 다시 잇는다. 바워-왓슨(Bowyer–Watson) 알고리즘이 대표적이며 구현이 직관적이다.
  • 엣지 플립(edge flipping): 일단 아무렇게나 삼각화한 뒤, 인서클 테스트를 위반하는 인접 삼각형 쌍의 공유 변을 뒤집는(flip) 연산을 더 이상 뒤집을 게 없을 때까지 반복한다.
  • 분할 정복(divide and conquer): 점들을 반씩 나눠 각각 삼각화한 뒤 봉합한다. 이론적으로 O(nlog⁡n)O(n \log n)으로 가장 빠른 축에 속한다.
  • 스위프라인(sweepline): 포춘(Fortune)의 알고리즘이 보로노이를 훑으며 만들고, 쌍대로 들로네를 얻는다.

계산기하 라이브러리 CGAL, 삼각화 도구 Triangle, 그리고 3차원 사면체 격자기 TetGen 등이 이 알고리즘들을 산업 강도로 구현해 두었다. 대부분 앞서 말한 강건한 판정(robust predicate) 문제를 정밀 산술로 우회한다.

5. 메시 생성에서의 역할[편집]

들로네 삼각분할이 진짜 밥값을 하는 곳은 유한요소법과 전산유체역학의 격자 생성이다. 하지만 점만 던져서 얻은 순수 들로네 삼각분할을 그대로 해석에 쓰기엔 두 가지 문제가 있다.

첫째, 순수 들로네는 입력 경계(도메인 형상의 변)를 반드시 격자 변으로 포함한다는 보장이 없다. 그래서 경계를 강제로 살리는 제약 들로네 삼각분할(Constrained Delaunay Triangulation, CDT)을 쓴다. 둘째, 뚱뚱한 삼각형을 만들어도 점 배치가 나쁘면 여전히 슬리버가 남는다. 이때는 들로네 세분화(Delaunay refinement) — 루퍼트(Ruppert)나 셰추크(Shewchuk)의 알고리즘 — 로 각도와 크기 기준을 만족할 때까지 점을 추가한다.4

3차원으로 넘어가면 이야기가 더 험해진다. 3D 들로네 사면체화에는 부피가 거의 0인 슬리버 사면체가 악명 높게 끼어드는데, 이는 2D와 달리 최소각 최대화 성질이 사면체에서는 성립하지 않기 때문이다. 보간과 근사의 정확도와 강성행렬의 조건수를 지키려면 별도의 슬리버 제거 후처리가 필수다. 그럼에도 오늘날 자동 메시 생성기의 심장에는 거의 예외 없이 들로네가 뛰고 있다.

6. 관련 문서[편집]

7. Footnotes[편집]

  1. 러시아식으로는 델로네(Делоне). 프랑스 위그노 후손이라 이름 표기가 들로네/델로네/드로네로 중구난방인데, 정작 본인은 등산가로도 유명해서 파미르 고원의 봉우리에 이름이 붙어 있다. ↩

  2. “거의 한 원 위의 네 점”은 계산기하학의 대표적 지뢰다. 부동소수점이 부호를 헷갈리는 순간 삼각화가 겹치거나 구멍이 뚫린다. 이래서 계산기하 하는 사람들이 정수 산술에 집착한다. ↩

  3. 그래서 “보로노이 그렸어?”라고 물으면 계산기하학자는 “들로네 그렸으니 보로노이도 있지”라고 답한다. 하나 사면 하나 딸려오는 1+1 자료구조. ↩

  4. 셰추크는 이 Triangle 코드로 계산기하학계의 소프트웨어 상을 받았다. 학위 논문 부산물로 만든 도구가 20년 넘게 전 세계 메시 생성의 표준이 된, 대학원생의 로망 같은 사례다. ↩