Пређи на садржај

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

С Википедије, слободне енциклопедије
Fortune's algorithm animation

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

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

[уреди | уреди извор]

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

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

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

Псеудокод

[уреди | уреди извор]

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

let  be the transformation ,
  where  is the Euclidean distance between  and the nearest site
let  be the "beach line"
let  be the region covered by site .
let  be the boundary ray between sites  and .
let  be the sites with minimal -coordinate, ordered by -coordinate

create initial vertical boundary rays 

while not IsEmpty() do
     ← DeleteMin()
    case  of
     is a site in :
        find the occurrence of a region  in  containing ,
          bracketed by  on the left and  on the right
        create new boundary rays  and  with bases 
        replace  with  in 
        delete from  any intersection between  and 
        insert into  any intersection between  and 
        insert into  any intersection between  and 
     is a Voronoi vertex in :
        let  be the intersection of  on the left and  on the right
        let  be the left neighbor of  and
          let  be the right neighbor of  in 
        create a new boundary ray  if ,
          or create  if  is right of the higher of  and ,
          otherwise create 
        replace  with newly created  in 
        delete from  any intersection between  and 
        delete from  any intersection between  and 
        insert into  any intersection between  and 
        insert into  any intersection between  and 
        record  as the summit of  and  and the base of 
        output the boundary segments  and 
    endcase
endwhile
output the remaining boundary rays in 

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

[уреди | уреди извор]

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

Референце

[уреди | уреди извор]
  1. ^ а б Mark de Berg; Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000), Computational Geometry (2nd revised изд.), Springer-Verlag, ISBN 978-3-540-65620-3  Section 7.2: Computing the Voronoi Diagram: pp. 151—160.
  2. ^ Austin, David, Voronoi Diagrams and a Day at the Beach, Feature Column, American Mathematical Society 
  3. ^ Steven Fortune. A sweepline algorithm for Voronoi diagrams. Proceedings of the second annual symposium on Computational geometry. Yorktown Heights, New York, United States. . 1986. стр. 313—322. ISBN 978-0-89791-194-8.  Недостаје или је празан параметар |title= (помоћ) ACM Digital LibrarySpringerLink[мртва веза]
  4. ^ Wong, Kenny; Hausi A. Müller, An Efficient Implementation of Fortune's Plane-Sweep Algorithm for Voronoi Diagrams, CiteSeerX 10.1.1.83.5571Слободан приступ 

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

[уреди | уреди извор]