- Fortune’s Algorithm은 보로노이 다이어그램을 O(n log n) 시간에 만들 수 있지만, 구현이 까다로워 대규모 다이어그램을 반복 생성하는 경우가 아니면 O(n²) 구현이나 라이브러리가 더 현실적임
- 보로노이 다이어그램은 여러 site를 기준으로 평면을 가장 가까운 영역으로 나누며, 경계는 두 site와 같은 거리인 점들로 형성됨
- 알고리듬은 왼쪽에서 오른쪽으로 움직이는 sweep line과 포물선 호들의 전선인 beachline을 유지하고, site event와 circle event만 처리함
- site event는 새 호를 삽입해 기존 호를 나누고 incomplete edge를 만들며, circle event는 가운데 호를 제거하면서 Voronoi Vertex와 half edge를 완성함
- 실용 구현에서는 이벤트 큐, beachline, incomplete edge 맵, DCEL을 함께 다뤄야 하며, 무효 circle event 제거와 남은 edge 정리가 복잡도를 크게 높임
구현 난도와 적용 범위
- Fortune’s Algorithm은 보로노이 다이어그램을 O(n log n) 시간에 생성하는 알고리듬임
- 실제 사용 목적이라면 바로 구현하기보다 요구 규모를 먼저 따져보는 편이 좋음
- 큰 다이어그램을 초당 여러 개 생성해야 하는 경우가 아니라면 O(n²) 구현이 더 쉬운 선택지가 될 수 있음
- 더 현실적인 대안은 기존 라이브러리 사용임
- 알고리듬은 동작 결과가 시각적으로 흥미롭지만, 구현 과정은 까다롭고 좌절감이 큰 편임
보로노이 다이어그램의 기본 개념
- 보로노이 다이어그램은 평면을 여러 영역으로 나누는 방법이며, 절차적 지도 생성에 자주 사용됨
- 입력으로 선택한 점들은 site 또는 seed라고 부름
- 각 site에 대응하는 cell은 평면 위의 점 중 해당 site에 가장 가까운 점들의 집합임
- 셀의 경계는 두 site와 같은 거리에 있는 점들로 구성됨
- 셀의 모서리가 만나는 Voronoi Vertex는 세 site와 같은 거리에 있는 점임
sweep line, beachline, event
- Fortune’s Algorithm은 왼쪽에서 오른쪽으로 이동하는 세로선인 sweep line을 사용함
- sweep line이 site를 만나면 해당 site를 초점으로 하는 포물선 호가 만들어지고, sweep line이 멀어질수록 호가 커짐
- 서로 다른 site의 두 호가 만나는 지점은 두 site와 같은 거리이므로 셀의 경계가 됨
- 두 경계가 만나면 다이어그램의 꼭짓점이 생성됨
- 활성화된 호들의 전선은 beachline이라고 부름
- 실제 구현은 픽셀 단위로 sweep line을 이동하지 않고, 계산 가능한 특정 지점인 event만 처리함
- site event: 미리 알고 있는 site 좌표로 정의되며, 처리 시 beachline에 새 호가 추가됨
- circle event: beachline의 세 호로 정의되며, 처리 시 호 하나가 제거되고 Voronoi Vertex와 half edge가 생성됨
포물선으로 경계 찾기
- 알고리듬에서 포물선은 일반적인
y = ax^2 + bx + c형태 대신 locus definition으로 다룸 - 포물선은 하나의 focus point와 하나의 directrix로 정의됨
- focus point는 site가 됨
- directrix는 sweep line이 됨
- 같은 sweep line을 directrix로 사용하는 두 포물선의 교점은 두 site와 같은 거리에 있음
- 따라서 두 포물선의 교점을 찾으면 두 site 사이의 equiedge를 찾을 수 있음
- 포물선의 x 좌표를 계산하는 의사 코드와, sweep line 위치가 바뀔 때 두 포물선의 교점이 경계를 따라 이동하는 예시가 사용됨
beachline 표현과 site event 처리
- beachline의 각 호는 해당 site의 좌표만으로 표현할 수 있음
- sweep line은 모든 호에 공통으로 적용됨
- 구현에서는 호를 별도 객체가 아니라 2D 좌표로 다룸
- beachline은 단순한 점의 순서로 표현할 수 있음
- 예:
[arc1, arc2],[arc1, arc2, arc3] - 같은 site의 호가 beachline에 여러 번 나타날 수 있음
- 예:
[arc1, arc3, arc1, arc2]
- 예:
- site event가 발생하면 새 site에서 왼쪽으로 선을 그었을 때 만나는 beachline의 호를 찾고, 새 호가 그 호를 분할함
- 새 site
L이 기존 beachline[.., i, j, k, ..]의j를 나누면 구조는[.., i, j, L, j, k, ..]가 됨 - site들은 x 좌표 순서대로 큐에 들어가며, 처리될 때마다 beachline과 이벤트 후보가 갱신됨
circle event와 circumcircle
- beachline의 세 호
[.., i, j, k, ..]에서 두 경계가 만나는 상황이 생기면 가운데 호j가 사라짐 - 이때 세 site를 지나는 circumcircle이 존재하고, 원의 중심은 세 site와 같은 거리에 있음
- circumcircle의 중심은 Voronoi Vertex가 됨
- circle event는 원의 오른쪽 끝점인 circle point를 기준으로 이벤트 큐에 배치됨
- 새로운 site가 circle point에 도달하기 전에 원 내부에서 발견되면 기존 circle event는 무효가 됨
- 새 site가 가운데 호를 먼저 나누기 때문에 세 호의 조합이 더 이상 유지되지 않음
- 기존 triple
i, j, k는 사라지고i, j, L,L, j, k같은 새 triple을 검사해야 함
incomplete edge와 half edge
- incomplete edge는 한쪽 끝은 고정되어 있지만, 다른 끝은 두 포물선 호의 교점으로 정의되는 선임
- site event로 새 호가 삽입될 때 두 개의 incomplete edge가 생성됨
- 고정점은 새 호가 기존 beachline과 만난 좌표임
- 새 호
j가 기존 호i를 나누면[i, j],[j, i]교점에 대응하는 edge가 생김
- circle event에서 두 incomplete edge가 충돌하면 그 충돌점이 Voronoi Vertex가 됨
- 기존 incomplete edge는 이 지점에서 half edge로 완성되고, 새로 인접하게 된 두 호 사이에는 새로운 incomplete edge가 생성됨
반시계 방향 원만 circle event가 됨
- beachline에
[i, j, k, j, i]가 있을 때ijk와kji는 모두 원을 만들 수 있지만, 둘 다 유효한 circle event는 아님 - 가운데 호가 사라지는 경우는 경계가 실제로 수렴하는 쪽뿐임
- 프로그램에서는 세 점의 orientation을 determinant로 판정함
- determinant가 음수이면 반시계 방향이며 circle event가 됨
- determinant가 양수이면 시계 방향이며 circle event가 아님
- determinant가 0이면 세 점이 일직선이라 원이 없음
전체 알고리듬 흐름
- 입력 site들을 x 좌표 기준으로 정렬해 site event로 큐에 넣음
- 큐가 빌 때까지 다음 event를 꺼내 처리함
- site event 처리:
- 앞으로 남아 있는 circle event 중 새 site가 원 내부에 들어가는 이벤트를 제거함
- 새 site가 분할할 beachline의 호를 찾음
- 새 호를 삽입해 기존 호를 나눔
- 두 개의 incomplete edge를 추가함
- 새로 생긴 triple들이 circle event를 만들 수 있는지 검사함
- circle event 처리:
- circumcircle 중심을 Voronoi Vertex로 추가함
- 가운데 호를 beachline에서 제거함
- 제거된 호 때문에 무효가 되는 향후 circle event를 제거함
- 새로 인접해진 호들의 triple을 검사해 circle event를 추가함
- 큐가 비면 남은 incomplete edge를 다이어그램 경계까지 연장하고, 경계와 만나는 지점에 Voronoi Vertex를 생성함
Odin 구현의 자료구조
- 예제 구현은 C 대안 언어인 Odin으로 작성됨
- 전체 코드는 RedPenguin101/voronoi 저장소에 있음
- 기본 타입:
V2:[2]int형태의 2D 점PointPair: 두V2의 쌍Event:{site: bool, a, b, c: V2}구조체
Event의 의미는 타입에 따라 달라짐- site event에서는
a가 site 좌표이고b,c는 사용하지 않음 - circle event에서는
a,b,c가 event를 만든 beachline의 세 호임
- site event에서는
Fortune구조체는 다음 상태를 관리함beachline:V2배열queue:Event배열incomplete_edges:PointPair -> V2맵vd: Voronoi Diagram을 저장하는 DCEL
구현에서 생략되거나 단순화된 부분
- beachline은 벡터로 표현했지만, 효율을 높이려면 binary tree가 더 적합함
- event queue도 개념적으로는 priority queue이지만, 예제 구현에서는 배열을 정렬 삽입하는 방식으로 다룸
- circle event 무효화는 향후 이벤트를 순회해 검사하는 방식이며, 더 빠른 방법이 필요하다는 TODO가 있음
clean_beachline_edges는 beachline 양 끝에서 불필요한 호를 잘라내는 절차임- 구현에는 같은 x 좌표를 가진 site, circle point와 site가 같은 경우, 참조점 충돌 같은 예외 처리가 포함됨
- 큐가 빈 뒤 남은 incomplete edge, twin이 없는 half edge, vertex를 정리하는 마지막 단계는 단순한 수학 처리로만 다뤄짐
DCEL로 보로노이 다이어그램 저장하기
- 보로노이 다이어그램은 보통 Doubly Connected Edge List(DCEL) 로 저장됨
- DCEL은 vertex와 edge로 이루어진 cell-complex를 조작하기 쉽게 표현하는 자료구조임
- edge 중심 표현이지만 vertex와 face 정보도 함께 저장함
- 일반 edge는 방향이 없지만, DCEL에서는 각 edge를 양방향의 두 half edge로 저장함
- 보로노이 다이어그램에서 DCEL에 저장되는 vertex는 site가 아니라 Voronoi Vertex임
- edge
E의 목적지는E.twin.origin으로 얻고, 오른쪽 face는E.twin.left로 얻음