보로노이 다이어그램

1. 직접 찍어 보기

캔버스를 클릭해 시드를 추가하자. 클릭할 때마다 모든 픽셀이 "누가 제일 가까운가"를 다시 계산해 색을 칠한다. 거리 재는 방식(유클리드 / 맨해튼)을 바꾸면 경계 모양이 확 달라진다.

2. 경계는 왜 수직 이등분선인가

시드 A와 B만 있다고 하자. 어떤 점 P가 셀 A에 속하려면 dist(P, A) < dist(P, B). 등호가 성립하는 점들 dist(P, A) = dist(P, B)은 정확히 A와 B를 잇는 선분의 수직 이등분선이다. 그 선을 기준으로 A쪽 반평면 전체가 셀 A가 된다.

시드가 여러 개면, 시드 A의 셀은 "A와 다른 모든 시드 사이의 수직 이등분선"이 만드는 반평면들을 전부 교집합한 것이다. 반평면의 교집합이므로 각 보로노이 셀은 항상 볼록 다각형 (경계 셀은 무한히 뻗는 볼록 영역)이다.

3. 만드는 방법 세 가지

화면에 색을 칠하는 용도라면 브루트포스(또는 GPU에서 "제프리 콘" 기법)로 충분하다. 하지만 셀의 실제 다각형 좌표가 필요하면 포춘 알고리즘이나 델로네 쌍대를 쓴다.

# 브루트포스: 픽셀 하나가 어느 셀인지
def owner(px, py, sites):
    best, bi = float('inf'), -1
    for i, (sx, sy) in enumerate(sites):
        d = (px - sx)**2 + (py - sy)**2   # sqrt 불필요: 대소만 비교
        if d < best:
            best, bi = d, i
    return bi

4. 델로네 삼각분할 — 보로노이의 뒷면

위 데모에서 "델로네 삼각분할"을 켜면 시드들을 삼각형으로 잇는 그물이 나타난다. 보로노이 다이어그램과 델로네 삼각분할은 같은 정보의 앞뒷면(쌍대, dual)이다.

• 보로노이 셀 1개 ↔ 델로네 정점(시드) 1개
• 보로노이 변(두 셀의 경계) 1개 ↔ 두 시드를 잇는 델로네 간선 1개 (서로 수직)
• 보로노이 정점 1개 ↔ 델로네 삼각형 1개 (그 삼각형의 외심이 보로노이 정점)

델로네 삼각분할의 핵심 성질: 어떤 삼각형의 외접원 안에도 다른 점이 들어가지 않는다 (empty circumcircle). 덕분에 지나치게 가늘고 긴 삼각형이 잘 안 생겨서, 지형 메시·유한요소 해석의 기본 삼각화로 쓰인다.

5. 어디에 쓰나

• 최근접 시설 질의 — "여기서 가장 가까운 소방서·와이파이 AP·서버는?" 미리 보로노이로 나눠 두면 즉답.
• 상권·커버리지 분석 — 각 매장이 담당하는 지역, 기지국 셀 설계.
• 게임·그래픽 — 절차적 맵 구역 분할, 균열/세포 텍스처, 성게 껍질 패턴.
• 과학 — 결정 구조 분석(위그너-자이츠 셀), 강수량 관측소별 담당 면적(티센 다각형), 생태학 세력권.
• 알고리즘 부품 — 유클리드 최소 신장 트리, 최근접 점 쌍, 경로 계획의 클리어런스 계산.