포춘 알고리즘

포춘 알고리즘은 O(n log n) 시간과 O(n) 공간을 사용하여 평면의 점 집합에서 보로노이 다이어그램을 생성하기 위한 스위프 라인 알고리즘이다.^[1][2]원래 스티븐 포춘이 1986년 자신의 논문 '보로노이 다이어그램의 스위플린 알고리즘'^[3]에서 발표한 것이다.

알고리즘 설명

알고리즘은 스위프 라인과 비치 라인을 모두 유지하며, 이 둘 다 알고리즘이 진행됨에 따라 평면을 통해 이동한다.스윕 라인은 직선으로, 관례상 수직으로 되어 있고 비행기를 가로질러 왼쪽에서 오른쪽으로 이동한다고 가정할 수 있다.알고리즘이 진행되는 동안 언제든지 스위프 라인의 왼쪽 입력 지점이 보로노이 다이어그램에 통합되는 반면 스위프 라인의 오른쪽 지점은 아직 고려되지 않을 것이다.비치 라인은 직선이 아니라, 포물선 조각들로 구성된 스위프 라인 왼쪽의 복잡하고 단편적인 곡선이다. 이 곡선은 다른 어떤 지점이 스위프 라인의 오른쪽인지에 관계 없이, 보로노이 다이어그램이 알 수 있는 비행기의 부분을 나머지 부분으로부터 나눈다.스위프 라인의 왼쪽 지점 각각에 대해, 그 지점과 스위프 라인에서 등거리 지점의 포물선을 정의할 수 있다. 비치 라인은 이 포물선들의 결합의 경계선이다.스위프 라인이 진행되면서 두 개의 포물선이 교차하는 해변 라인의 정점이 보로노이 도표의 가장자리를 추적한다.비치 라인은 각 포물선 기지를 처음에 스위프 라인으로 쓸어넘긴 지점과 스위프 라인의 새로운 위치 사이에 정확히 절반으로 유지함으로써 진행된다.수학적으로 이것은 각 포물선이 다이렉트릭스로, 입력점을 포커스로 사용하여 형성되는 것을 의미한다.

알고리즘은 데이터 구조로 비치 라인의 결합 구조를 설명하는 바이너리 검색 트리와 비치 라인 구조를 변경할 수 있는 잠재적 미래 이벤트를 나열하는 우선순위 대기열을 유지한다.이러한 이벤트에는 비치 라인에 또 다른 포물선을 추가하고(스윕 라인이 다른 입력 지점을 통과할 때), 비치 라인에서 곡선을 제거하는 것(파라볼라가 비치 라인의 연속 세그먼트를 형성하는 3개의 입력 지점을 통해 스위프 라인이 원에 접하는 경우)이 포함된다.그러한 각 이벤트는 이벤트가 발생하는 지점에서 스위프 라인의 x 좌표로 우선순위를 정할 수 있다.그런 다음 알고리즘 자체는 우선순위 대기열에서 다음 이벤트를 반복적으로 제거하고, 비치 라인의 이벤트 원인 변경사항을 찾아내고, 데이터 구조를 업데이트하는 것으로 구성된다.

처리할 O(n) 이벤트(각각 보로노이 다이어그램의 일부 기능과 연관됨)와 이벤트를 처리하는 O(log n) 시간(각각 일정한 수의 이진 검색 트리 및 우선 순위 대기열 작업으로 구성됨)이 있으므로 총 시간은 O(n log n)이다.

가성음

알고리즘의 유사 코드 설명.^[4]

let ${\displaystyle *(z)}$ be the transformation ${\displaystyle *(z)=(z_{x},z_{y}+d(z))}$,   where ${\displaystyle d(z)}$ is the Euclidean distance between z and the nearest site let T be the "beach line" let ${\displaystyle R_{p}}$ be the region covered by s$Ite{\displaystyle {}_{}}$ p. ${\displaystyle p_{}}$ ${\$를 사이트 p와 Q 사이의 경계선으로$$ 한다. S ${\displaystyle$ S$}$을(를) 이 $알고리즘$을 적용할 사이트의 집합으로 한다$$.let ${\displaystyle p_{1},p_{2},...,p_{m}}$ be the sites extracted from ${\displaystyle S}$ with minimal y-coordinate, ordered by x-coordinate let DeleteMin(X) be the act of removing the lowest and leftmost site of ${\displaystyle X}$ (sort by y unless they're identical, in which case sortby x)  let ${\displaystyle V}$ be the Voronoi map of ${\displaystyle S}$ which is to be constructed by this algorithm ${\displaystyle Q\gets {p_{1},p_{2},...,p_{m},S}}$ create initial vertical boundary rays ${\displaystyle C_{p_1,p_2}^0,C_{p_2,p_3}^0,...C_{{}_{}}^{}}$${\$$$$C_{p_{m-1},p_{m}}^{0}}$ ${\displaystyle T\gets *(R_{p_{1}}),$$C_{p_{1},p_{2}}^{0},*(R_{p_{2}}),C_{p_{2},p_{3}^{0},...,*(R_{p_{m-1}),$$C_{p_{m-1},p_{m}}^{0},*(R_{p_{m}})}$ while not IsEmpty(Q) do p ← DeleteMin(Q)     case p of     p is a site in ${\displaystyle *(V)}$:         find the occurrence of a region ${\displaystyle *(R_{q})}$ in T containing p,           bracketed by ${\displaystyle C_{rq}}$ on the left and ${\displaystyle C_{qs}}$${\displaystyle C_{qs}}$ on the right         create new boundary rays ${\displaystyle C_{pq}^{-}}$ and ${\displaystyle C_{pq}^{+}}$ with bases p         replace ${\displaystyle *(R_{q})}$ with ${\displays$$tyle *(R_{q}),C_{pq}^{-},*(R_{p}),C_{pq}^{+},*(R_{q})}$ in T         delete from Q any intersection between ${\displaystyle C_{rq}}$ and ${\displaystyle C_{qs}}$         insert into Q any intersection between ${\displaystyle C_{rq}}$ and ${\displaystyle C_{pq}^{-}}$         insertinto Q any intersection between ${\displaystyle C_{pq}^{+}}$ and ${\displaystyle C_{qs}}$ p is a Voronoi vertex in ${\displaystyle *(V)}$:         let p be the intersection of ${\displaystyle C_{qr}}$ on the left and ${\displaystyle C_{rs}}$ on the right         let${\displaystyle C_{uq}}$ be the left neighbor of ${\displaystyle C_{qr}}$ and           let ${\displaystyle C_{sv}}$ be the right neighbor of ${\displaystyle C_{rs}}$ in T         create a new boundary ray ${\displaystyle C_{qs}^{0}}$ if ${\di$$splaystyle q_{y}=s_{y}}$,           or create ${\displaystyle C_{qs}^{+}}$ if p is right of the higher of q and s,           otherwise create ${\displaystyle C_{qs}^{-}}$         replace ${\displaystyle C_{qr},*(R_{r}),C_{rs}}$ with newly created ${\$$디스플레이{\displaystyle {}_{}}$ $스타일 C_{qs}}$ T에서 $C{\displaystyle {}_{}}$ ${\displaystyle u_{}}$ ${\displaystyle q_{}}$ ${\$와 $C{\displaystyle {}_{}}$$$$$${\displaystyle q_{}}$ $r{\displaystyle {}_{}}$ {\$displaystyle C_{$$qr}$ 사이의 교차로 삭제 C ${\displaystyle r_{}}$ ${\displaystyle s_{}}$ ${\$ 사이의 교차로 삭제${\displaystyle C_{uq}}$ and ${\displaystyle C_{qs}}$         insert into Q any intersection between ${\displaystyle C_{qs}}$ and ${\displaystyle C_{sv}}$         record p as the summit of ${\displaystyle C_{qr}}$ and ${\displaystyle C_{rs}}$ and the base of ${\displaystyle }$${\displaystyle C_{}}$ ${\displaystyle q_{}}$ ${\displaystyle s_{}}$ ${\$ 경계 $세그먼트{\displaystyle {}_{}}$ ${\displaystyle C_{}}$ ${\displaystyle q_{}}$ r$${\$displaystyle C_{qr}$ $및$ ${\displaystyle C_{}}$ ${\displaystyle r_{}}$ s$${\$displaystyle C_{rs}$ 엔드케이스$$ 엔드를 출력하는$$ 동시에 나머지 경계선을 T로 출력한다.

가중 사이트 및 디스크

으로서 포춘 ref.,[1]에 설명하는 스위프 라인 알고리즘을 수정한 버전은 각 사이트의 거리는 사이트의 무게에 의해서 상쇄된 추가적 가중 보로노이 다이어그램, 구축에 모두 동등하게 디스크에 걸친 보로노이 다이어그램, 반경 그 사이트들 의 무게와 맞먹위주로 보여질 수 있으며 사용될 수 있다. 앉다e

보로노이 도표를 사용하여 트리맵을 작성할 때 보로노이 셀의 영역을 제어하는 데 가중 사이트를 사용할 수 있다.가중치가 추가된 보로노이 다이어그램에서 사이트 간 이등분선은 일반적으로 하이퍼볼라로, 직선이 되는 디스크의 미가중 보로노이 다이어그램과 전력 다이어그램과는 대조적이다.

참조

외부 링크

• Steven Fortune의 C 구현
• C++에서 구현된 포춘의 보로노이 알고리즘
• 자바스크립트에 구현된 포춘 알고리즘