GN⁺: 포춘 알고리즘을 활용한 보로노이 다이어그램 생성

보로노이 다이어그램 생성하기

• 보로노이 다이어그램이란?

  • 보로노이 다이어그램은 평면을 여러 영역으로 나누는 방법으로, 주로 절차적으로 지도를 생성하는 데 사용됨.
  • 평면에 '사이트'라 불리는 여러 점을 선택하고, 각 사이트에 대응하는 영역은 그 사이트에 가장 가까운 모든 점을 포함하는 영역임.
  • 각 영역의 경계는 두 사이트와 같은 거리에 있는 점들로 이루어짐. 세 사이트와 같은 거리에 있는 점은 '보로노이 정점'이라 불림.

• 포춘 알고리즘

  • 포춘 알고리즘은 평면의 왼쪽에서 오른쪽으로 '스윕'하는 선을 사용하여 다이어그램을 생성하는 방법임.
  • 스윕 라인이 사이트를 만나면 그 주위에 '버블'(포물선 호)이 생성되고, 스윕 라인이 멀어질수록 버블이 커짐.
  • 두 사이트의 호가 충돌하면 그 충돌 지점이 셀의 경계가 됨.
  • 모든 활성 버블의 경계는 '비치라인'이라 불림.

• 용어 해설

  • 사이트: 2차원 점으로, 보로노이 다이어그램의 모양을 결정함.
  • 스윕 라인: 영역을 가로지르는 수직선으로, 이벤트 큐의 각 이벤트를 처리함.
  • 비치라인: 여러 호로 이루어진 선으로, 이벤트가 처리될 때 호가 추가되거나 제거됨.
  • 교차점: 비치라인의 두 호가 만나는 지점으로, 관련된 사이트와 같은 거리에 있음.
  • 이벤트 큐: 사이트와 원 이벤트가 저장되는 곳으로, x좌표 오름차순으로 정렬됨.
  • 사이트 이벤트: 이벤트 큐의 두 가지 이벤트 중 하나로, 해당 사이트의 좌표로 정의됨.
  • 원 이벤트: 큐의 다른 유형의 이벤트로, 원의 둘레에 있는 세 호로 정의됨.
  • 보로노이 정점: 세 사이트와 같은 거리에 있는 점으로, 셀의 모서리임.
  • 동등 경계: 두 사이트와 같은 거리에 있는 선.
  • 불완전한 경계: 한쪽 끝은 고정된 점이고, 다른 쪽은 두 포물선 초점의 교차점으로 정의된 선.

• 포물선 접선

  • 포물선의 개념과 속성은 알고리즘에서 매우 중요함.
  • 포물선은 초점 점과 직선(디렉트릭스)으로 정의됨.
  • 두 사이트의 초점을 설정하고 스윕 라인을 디렉트릭스로 설정하면, 두 포물선의 교차점을 찾음으로써 두 사이트와 같은 거리에 있는 경계선을 찾을 수 있음.

• 비치라인으로 돌아가기

  • 비치라인은 스윕 라인의 주어진 지점에서 모든 호의 '경계'임.
  • 각 호는 사이트의 초점 점으로 표현될 수 있음.
  • 비치라인은 간단한 점의 시퀀스로 표현될 수 있음.

• 새로운 호는 스윕 라인이 새로운 사이트를 만날 때 생성됨

  • 비치라인은 점의 시퀀스로, 각 점은 사이트와 호를 나타냄.
  • 스윕 라인이 새로운 사이트를 만날 때 새로운 호가 생성되고 시퀀스에 삽입됨.

• 교차하는 경계와 외접원

  • 세 사이트가 원의 둘레에 있을 때, 원의 중심은 세 점과 같은 거리에 있음.
  • 외접원의 중심은 보로노이 정점이 됨.

• 불완전한 경계

  • 불완전한 경계는 한쪽 끝이 고정된 점이고, 다른 쪽은 두 호의 교차점임.
  • 두 불완전한 경계가 충돌하면 보로노이 정점이 생성되고, 불완전한 경계는 반경계로 변환됨.

• 시계 반대 방향의 원만이 원 이벤트를 생성함

  • 세 호가 시계 반대 방향으로 읽힐 때만 원 이벤트가 생성됨.

• 요약

  • 사이트 집합을 주어지면, 모든 사이트 점을 큐에 '사이트' 이벤트로 넣고 x값으로 정렬함.
  • 큐가 비어 있지 않은 동안, 다음 이벤트를 큐에서 꺼내 처리함.
  • 사이트 이벤트일 경우, 새로운 호를 비치라인에 추가하고 불완전한 경계를 생성함.
  • 원 이벤트일 경우, 보로노이 정점을 추가하고 비치라인에서 호를 제거함.