Фортунов алгоритам

Fortune's algorithm animation

Фортунов алгоритам је алгоритам покретне линије ѕа генерисање Воронојевих дијаграма из скупа тачака у равни чија је временска сложеност O(n log n) и просторна O(n). Објавио га је Стивен Фортун 1986. у свом раду "Алгоритам покретне линије за Воронојеве дијаграме."

Опис алгоритма

Алгоритам одржава покретну линију и обалску линију, које се обе крећу кроз раван како алгоритам напредује. Покретна линија је права линија, и можемо по договору претпоставити да је вертикална и да се креће слева надесно. У било ком тренутку током трајања алгоритма тачке лево од покретне линије ће бити уграђене у Воронојев дијаграм, док тачке десно од покретне линије нису још увек разматране. Обалска линија није линија, већ комплексна крива са леве стране покретне која се састоји од делова парабола; она раздваја део равни у којем Воронојев дијаграм може бити познат, без обзира на тачке десно од покретне линије, од остатка равни. За сваку тачку лево од покретне линије, може се дефинисати парабола тачака које су на подједнаком растојању од те тачке и од покретне линије; обалска линија је граница уније ових парабола. Док покретна линија напредује, темена обалске линије, у којој се две параболе секу, прати ивице Воронојевог дијаграма. Обалска линија напредује чувајући сваку параболу тачно на пола пута између тачака преко којих се претходно прешло покретном линијом и новог положаја покретне линије.

Алгоритам одржава као структуру података бинарно стабло претраге које описује структуру обалске линије и приоритетни ред који садржи потенцијалне будуће догађаје који могу да промене структуру обалске линије. Ови догађаји укључују додавање нове параболе у обалску линију (када покретна линија наиђе на нову улазну тачку) и уклањање криве из обалске линије (када покретна линија постане тангента на кругу кроз неке три улазне тачке чије параболе формирају узастопне сегменте обалске линије). Приоритет сваког таквог догађаја се може одредити на основу x-координате покретне линије у тачки у којој се догађај десио. Сам алгоритам се онда састоји од уклањања следећег догађаја из приоритетног реда, проналажења промена које догађај проузрокује у обалској линији и ажурирања структура података.

Пошто има O(n) догађаја које треба обрадити (сваки је повезан са неком карактеристиком Воронојевог дијаграма) и O(log n) времена за обраду догађаја (сваки се састоји од константног броја операција на бинарном стаблу претраге и приоритетном реду) укупно време је O(n log n).

Псеудокод

Псеудокод опис алгоритма.

let $*(z)$ be the transformation $*(z)=(z_{x},z_{y}+d(z))$,
  where $d(z)$ is the Euclidean distance between $z$ and the nearest site
let $T$ be the "beach line"
let $R_{p}$ be the region covered by site $p$.
let $C_{pq}$ be the boundary ray between sites $p$ and $q$.
let $p_{1},p_{2},...,p_{m}$ be the sites with minimal $y$-coordinate, ordered by $x$-coordinate
$Q\gets S-{p_{1},p_{2},...,p_{m}}$
create initial vertical boundary rays $C_{p_{1},p_{2}}^{0},C_{p_{2},p_{3}}^{0},...C_{p_{m-1},p_{m}}^{0}$
$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 $*(V)$:
        find the occurrence of a region $*(R_{q})$ in $T$ containing $p$,
          bracketed by $C_{rq}$ on the left and $C_{qs}$ on the right
        create new boundary rays $C_{pq}^{-}$ and $C_{pq}^{+}$ with bases $p$
        replace $*(R_{q})$ with $*(R_{q}),C_{pq}^{-},*(R_{p}),C_{pq}^{+},*(R_{q})$ in $T$
        delete from $Q$ any intersection between $C_{rq}$ and $C_{qs}$
        insert into $Q$ any intersection between $C_{rq}$ and $C_{pq}^{-}$
        insert into $Q$ any intersection between $C_{pq}^{+}$ and $C_{qs}$
    $p$ is a Voronoi vertex in $*(V)$:
        let $p$ be the intersection of $C_{qr}$ on the left and $C_{rs}$ on the right
        let $C_{uq}$ be the left neighbor of $C_{qr}$ and
          let $C_{sv}$ be the right neighbor of $C_{rs}$ in $T$
        create a new boundary ray $C_{qs}^{0}$ if $q_{y}=s_{y}$,
          or create $C_{qs}^{+}$ if $p$ is right of the higher of $q$ and $s$,
          otherwise create $C_{qs}^{-}$
        replace $C_{qr},*(R_{r}),C_{rs}$ with newly created $C_{qs}$ in $T$
        delete from $Q$ any intersection between $C_{uq}$ and $C_{qr}$
        delete from $Q$ any intersection between $C_{rs}$ and $C_{sv}$
        insert into $Q$ any intersection between $C_{uq}$ and $C_{qs}$
        insert into $Q$ any intersection between $C_{qs}$ and $C_{sv}$
        record $p$ as the summit of $C_{qr}$ and $C_{rs}$ and the base of $C_{qs}$
        output the boundary segments $C_{qr}$ and $C_{rs}$
    endcase
endwhile
output the remaining boundary rays in $T$

Тежинске локације и дискови

Као што Фортун описује у модификована верзија алгоритма покретне линије може бити искоришћена за конструкцију адитивног тежинског Воронојевог дијаграма, у коме удаљеност до сваке локације (генератора) је померена за тежину локације; ово може бити еквивалентно посматрано као Воронојев дијаграм скупа дискова чији је центар у локацијама са радијусом једнаким тежини локације.

Спољашње везе

• Фортунов алгоритам имплементиран у Ц-у
• Фортунов алгоритам имплементиран у C++
• Фортунов алгоритам имплементиран у javascript-у