보로노이 다이어그램 시각화
평면의 각 지점을 가장 가까운 사이트에 할당하여 영역을 분할하는 과정을 관찰합니다
기하학★★☆
속도
1 / 1사이트 수: 12스윕 진행률: 100%
사이트 수12
캔버스를 클릭하여 사이트를 추가하세요.
스윕 라인이 위에서 아래로 이동하며 각 픽셀을 가장 가까운 사이트에 할당합니다.
스윕 라인이 위에서 아래로 이동하며 각 픽셀을 가장 가까운 사이트에 할당합니다.
보로노이 다이어그램이란?
보로노이 다이어그램은 평면을 여러 사이트 기준으로 분할하여, 각 영역 내 모든 점이 해당 사이트에 가장 가까운 공간 분할입니다.
사용 방법
- 1사이트 수를 슬라이더로 조절하거나 캔버스를 클릭하여 추가하세요
- 2랜덤 또는 그리드 배치 버튼으로 사이트를 생성하세요
- 3재생 버튼으로 스윕 라인 애니메이션을 관찰하세요
- 4각 영역은 해당 사이트의 색상으로 칠해집니다
동작 원리
- 1각 픽셀에서 모든 사이트까지의 거리를 계산합니다
- 2가장 가까운 사이트의 인덱스를 할당합니다
- 3인접 픽셀의 사이트가 다르면 경계로 표시합니다
- 4브루트포스는 O(n × w × h), Fortune은 O(n log n)
- 5이 시각화는 이해를 위해 픽셀 단위 방식을 사용합니다
실무 활용
- •도시 계획 — 가장 가까운 시설 배정 영역 계산
- •게임 개발 — 맵 생성, 영역 분할
- •네트워크 설계 — 기지국 커버리지 영역
- •기상학 — 관측소 데이터 공간 보간
비슷한 알고리즘
- •보로노이 vs 들로네 삼각분할 — 듀얼 관계
- •Fortune Sweep Line — O(n log n) 최적 알고리즘
- •k-d 트리 — 최근접 이웃 검색 자료구조
학습 팁
- •균등 배치하면 영역 크기가 비슷해집니다
- •한쪽에 몰면 불균형을 관찰할 수 있습니다
- •보로노이 경계선은 수직 이등분선입니다
자주 묻는 질문
Q. 보로노이와 들로네의 관계는?
A. 듀얼 관계입니다. 들로네 삼각형의 외심이 보로노이 꼭짓점이 됩니다.
Q. Fortune 알고리즘은?
A. 스윕 라인과 비치 라인을 이용한 O(n log n) 알고리즘입니다.
Q. 3D 확장 가능?
A. 네, 3D 보로노이는 다면체 영역으로 확장됩니다.