점 구름을 삼각형으로 덮는 두 철학 — Bowyer–Watson과 전진 프론트

1934년, 소련의 수학자 보리스 델로네(Boris Delaunay)는 자신의 스승 게오르기 보로노이의 이름을 붙인 다이어그램에서 쌍대(dual)를 하나 뽑아냈다. 평면에 흩어진 점들을 삼각형으로 잇되, 어느 삼각형의 외접원 안에도 다른 점이 들어가지 않도록 하는 방법. 90년이 지난 지금, 이 규칙은 CFD 격자 생성기의 심장에 그대로 박혀 있다.

이 글은 비정렬 삼각형 격자를 만드는 두 가지 철학을 다룬다. 하나는 점을 하나씩 밀어 넣는 Bowyer–Watson 증분 Delaunay 알고리즘. 다른 하나는 경계에서부터 요소를 탐욕적으로 쌓아 올리는 전진 프론트 기법(AFT). 외접원 판정을 Python으로 짜서 격자가 자라는 과정을 직접 보고, 두 방법을 언제 나눠 쓰는지까지 정리한다.

점 구름을 삼각형으로 덮는 두 철학#

같은 점 집합을 삼각형으로 잇는 방법은 무수히 많다. 문제는 "어떤 삼각화가 좋은가"이다. CFD에서 좋은 격자란 가늘고 뾰족한 삼각형이 적은 격자다. 납작한 삼각형은 수치 미분의 오차를 키우고 선형계의 조건수를 망친다.

Delaunay 삼각화는 이 요구에 정면으로 답한다. 가능한 삼각화 중에서 최소 내각을 최대화한다. 즉, 가장 뾰족한 삼각형의 각도를 가능한 한 크게 만든다. 점 위치만 주어지면 유일한 답이 나온다는 것도 매력이다.

전진 프론트는 정반대 순서로 접근한다. 점을 먼저 뿌리지 않는다. 경계선을 출발점으로 삼아, 안쪽으로 삼각형을 한 개씩 붙이며 새 점을 그때그때 만든다. 매 순간 가장 좋은 요소를 고르는 지역 탐욕(greedy)이다.

빈 외접원 — Delaunay를 정의하는 성질#

Delaunay 삼각화를 규정하는 문장은 딱 하나다. 어떤 삼각형의 외접원도 내부에 다른 정점을 품지 않는다. 이를 빈 외접원 조건(empty circumcircle)이라 부른다.

판정은 행렬식 하나로 끝난다. 점 $d$ 가 삼각형 $abc$ 의 외접원 내부에 있는지 보려면, $abc$ 를 반시계 방향으로 두고 다음을 계산한다.

\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

여기서 $a,b,c$ 는 삼각형 세 정점, $d$ 는 검사할 점이다. 행렬식이 양수면 $d$ 는 외접원 안, 음수면 밖, 0이면 원 위에 정확히 놓인다. 나눗셈도 제곱근도 없다. 부호만 보면 되니 부동소수점 오차에도 비교적 안전하다.

네 점이 하나의 사각형을 이룰 때, 대각선을 어느 쪽으로 긋느냐는 이 판정 하나로 갈린다. 아래에서 위쪽 정점을 위아래로 끌어보자. 공유 에지를 넘는 순간 대각선이 뒤집힌다.

Drag vertex T through the shared edge. When T enters the circumcircle of the lower triangle, the diagonal snaps from LR to BT — a single Lawson flip restoring the empty-circumcircle rule.

정점 T를 아래 삼각형의 외접원 안으로 밀면 대각선이 LR에서 BT로 바뀐다. 이 한 번의 뒤집기가 바로 로슨 플립(Lawson flip)이다. 국소적으로 빈 외접원 조건을 회복하는 최소 연산이다.

Bowyer–Watson: 공동을 파고 다시 채운다#

로슨 플립을 반복해도 Delaunay 격자를 만들 수 있다. 하지만 더 우아한 길이 있다. 에이드리언 바우어와 데이비드 왓슨이 1981년 같은 학술지에 나란히 발표한 증분 삽입법이다.

핵심 발상은 간단하다. 이미 Delaunay인 격자에 새 점 $p$ 를 넣을 때, $p$ 를 외접원 안에 품는 삼각형들은 전부 무효가 된다. 이 무효 삼각형들을 지우면 다각형 모양의 빈 공간, 즉 **공동(cavity)**이 생긴다. 이제 공동의 경계 에지 각각과 $p$ 를 이어 새 삼각형을 채우면 끝이다.

절차는 세 단계로 요약된다.

새 점 $p$ 를 외접원에 포함하는 삼각형(나쁜 삼각형)을 모두 찾는다.
나쁜 삼각형들이 이루는 공동의 경계 에지를 뽑는다. 경계 에지는 나쁜 삼각형 하나에만 속한 에지다.
나쁜 삼각형을 지우고, 경계 에지마다 $p$ 를 이어 삼각형을 새로 만든다.

시작할 때는 모든 입력 점을 감싸는 거대한 슈퍼 삼각형 하나에서 출발한다. 점을 다 넣은 뒤 슈퍼 삼각형 정점에 걸린 삼각형을 걷어내면 최종 Delaunay 격자만 남는다.

아래 캔버스를 클릭해 점을 하나씩 찍어보자. 매 삽입마다 격자가 Bowyer–Watson으로 다시 짜인다.

Show circumcircles

Click on the canvas to insert a point. Each insertion rebuilds the Delaunay triangulation via Bowyer–Watson. Toggle the circumcircles: every one stays empty of other vertices — that is the Delaunay property.

외접원 표시를 켜면 모든 원이 다른 정점을 담지 않는다. 점을 아무리 촘촘히 찍어도 이 성질은 깨지지 않는다. 그게 Delaunay다.

Python — 증분 Delaunay를 처음부터 짠다#

외접원 판정부터 삽입 커널까지, 라이브러리 없이 순수 Python으로 옮겨보자.

import numpy as np
 
def circumcircle(a, b, c):
    """세 점의 외접원 중심과 반지름 제곱을 반환. 일직선이면 None."""
    ax, ay = a; bx, by = b; cx, cy = c
    d = 2 * (ax * (by - cy) + bx * (cy - ay) + cx * (ay - by))
    if abs(d) < 1e-12:
        return None
    a2, b2, c2 = ax * ax + ay * ay, bx * bx + by * by, cx * cx + cy * cy
    ux = (a2 * (by - cy) + b2 * (cy - ay) + c2 * (ay - by)) / d
    uy = (a2 * (cx - bx) + b2 * (ax - cx) + c2 * (bx - ax)) / d
    return (ux, uy), (ax - ux) ** 2 + (ay - uy) ** 2
 
def in_circumcircle(p, tri, pts):
    """점 p가 삼각형 tri의 외접원 내부면 True."""
    cc = circumcircle(pts[tri[0]], pts[tri[1]], pts[tri[2]])
    if cc is None:
        return False
    (ux, uy), r2 = cc
    return (p[0] - ux) ** 2 + (p[1] - uy) ** 2 < r2 - 1e-12
 
def bowyer_watson(points):
    """증분 삽입으로 Delaunay 삼각화를 만든다."""
    pts = list(points)
    xs = [p[0] for p in pts]; ys = [p[1] for p in pts]
    dmax = 20 * max(max(xs) - min(xs), max(ys) - min(ys))
    cx, cy = (min(xs) + max(xs)) / 2, (min(ys) + max(ys)) / 2
    base = len(pts)                                    # 슈퍼 삼각형 정점 시작 인덱스
    pts += [(cx - dmax, cy - dmax), (cx + dmax, cy - dmax), (cx, cy + dmax)]
    tris = [(base, base + 1, base + 2)]
 
    for pi in range(base):                             # 점을 하나씩 삽입
        p = pts[pi]
        bad = [t for t in tris if in_circumcircle(p, t, pts)]
        edge_count = {}                                # 공동 경계 = 한 번만 등장한 에지
        for t in bad:
            for e in [(t[0], t[1]), (t[1], t[2]), (t[2], t[0])]:
                key = tuple(sorted(e))
                edge_count[key] = edge_count.get(key, 0) + 1
        boundary = [e for e, n in edge_count.items() if n == 1]
        tris = [t for t in tris if t not in bad]
        tris += [(a, b, pi) for a, b in boundary]      # p를 경계 에지에 잇는다
 
    return [t for t in tris if all(i < base for i in t)]  # 슈퍼 삼각형 제거
 
if __name__ == "__main__":
    rng = np.random.default_rng(3)
    P = [tuple(xy) for xy in rng.random((12, 2))]
    T = bowyer_watson(P)
    print(f"점 {len(P)}개 -> 삼각형 {len(T)}개")
    print("첫 삼각형 정점 인덱스:", T[0])

실행하면 점 12개 -> 삼각형 17개 같은 결과가 나온다. 볼록 껍질 안의 삼각형 개수는 대략 $2n - 2 - h$ 개다( $n$ 은 점 수, $h$ 는 볼록 껍질 위 점 수). 순수 삽입 커널이 60줄 안에 들어온다.

경계는 어떻게 지키나 — 제약과 파이프#

여기까지는 점만 있으면 되는 문제였다. 실제 CFD 형상은 다르다. 익형의 표면, 실린더의 벽처럼 반드시 격자 에지로 존재해야 하는 경계선이 있다. 그런데 순수 Delaunay는 이 경계 에지를 마음대로 가로지를 수 있다.

해법이 제약 Delaunay 삼각화(constrained DT)다. 원본 문서가 설명하는 절차는 이렇다. 잃어버린 경계선 $AB$ 를 복구하려면, 먼저 $AB$ 가 가로지르는 삼각형들의 띠, 이른바 **파이프(pipe)**를 찾는다. 점 $A$ 에 붙은 삼각형에서 출발해, $AB$ 가 뚫고 지나가는 이웃 삼각형을 따라가다 $B$ 에 닿으면 파이프가 완성된다.

파이프가 정해지면 그 안을 다시 삼각화해 $AB$ 를 에지로 복원한다. 대각선 교환(swapping of diagonals)이나 분할 정복으로 처리한다. 경계가 살아난 대신, 그 근처 삼각형은 더 이상 완벽한 Delaunay가 아닐 수 있다. 형상 충실도와 격자 품질을 맞바꾸는 셈이다.

전진 프론트 — 탐욕으로 요소를 쌓는다#

전진 프론트 기법(AFT)은 이 경계 문제를 아예 뒤집어 푼다. 경계가 곧 출발선이다.

경계 세그먼트 목록에서 기준 세그먼트 $AB$ 를 하나 고른다. 이 $AB$ 와 가장 좋은 삼각형을 이루는 점 $C$ 를 찾는다. 후보는 두 종류다. 기존 프론트 위의 점을 쓰거나, 새 내부 점 $I$ 를 만들거나. 둘 중 품질이 높은 쪽을 택해 삼각형을 만들고, 프론트를 갱신한다. 새로 생긴 에지는 프론트에 추가하고, 이미 프론트에 있던 에지는 닫힌 것으로 보고 제거한다.

품질은 두 요소의 곱으로 잰다.

\lambda = \alpha \cdot \delta

여기서 $\alpha$ 는 삼각형의 형상 계수(정삼각형이면 1, 납작할수록 0), $\delta$ 는 요구된 요소 크기와 실제 에지 길이의 일치도(둘이 같으면 1)다. $\lambda$ 가 클수록 좋은 요소다.

형상 계수는 이렇게 짤 수 있다.

import math
 
def shape_quality(a, b, c):
    """정삼각형이면 1, 납작할수록 0에 가까운 형상 계수 alpha."""
    l1 = math.dist(a, b); l2 = math.dist(b, c); l3 = math.dist(c, a)
    area = abs((b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])) / 2
    denom = l1 * l1 + l2 * l2 + l3 * l3
    return 4 * math.sqrt(3) * area / denom if denom > 0 else 0.0

프론트가 비면(닫힌 경계가 안쪽으로 다 모이면) 격자가 완성된다. 매 단계에서 국소 최적을 고르므로 AFT의 초기 격자 품질은 대개 Delaunay보다 높다. 특히 경계층처럼 방향성이 강한 이방성 격자를 만들 때 강점이 크다.

대가는 속도다. 새 요소마다 프론트의 다른 에지와 교차하는지 검사해야 한다. 소박하게 짜면 요소 하나에 $O(n)$ , 전체가 $O(n^2)$ 로 부풀 수 있다. 원본 문서가 강조하듯, 배경 격자나 사분트리(quadtree) 같은 공간 검색 자료구조로 이 검사를 국소화하는 것이 실전의 핵심이다.

언제 무엇을 고르나#

두 방법은 경쟁이 아니라 분업에 가깝다.

Delaunay는 점 분포가 주어졌을 때 유일하고 빠른 답을 준다. 볼록 껍질 채우기, 산란 데이터 보간, 사후 격자 개선에 강하다. 반면 경계를 스스로 지키지 못해 제약 처리가 따로 필요하다.

AFT는 경계 충실도와 초기 요소 품질이 뛰어나고 이방성 확장이 쉽다. 대신 구현이 까다롭고 자료구조 설계에 성능이 크게 좌우된다.

그래서 현대 격자 생성기는 둘을 섞는다. AFT로 요소 배치 순서를 정하되 Delaunay 연결 기준으로 점을 잇는 프론트–Delaunay 방식이 대표적이다. 두 철학의 장점만 취하는 절충이다.

기억할 점#

빈 외접원 조건이 Delaunay의 전부다. 판정은 부호만 보는 행렬식 하나로 끝나고, Bowyer–Watson은 공동을 파고 다시 채우는 60줄짜리 커널로 구현된다.
AFT는 경계에서 안쪽으로 $\lambda = \alpha\delta$ 가 최대인 요소를 탐욕적으로 쌓는다. 경계 충실도와 이방성에 강하지만 교차 검사 비용이 병목이다.
실무 격자기는 둘을 프론트–Delaunay로 결합해 순서는 AFT, 연결은 Delaunay로 나눠 맡긴다.

점 구름을 삼각형으로 덮는 두 철학 — Bowyer–Watson과 전진 프론트