оквир|десно|Fortune's algorithm animation
Фортунов алгоритам је алгоритам покретне линије ѕа генерисање Воронојевих дијаграма из скупа тачака у равни чија је временска сложеност O(n log n) и просторна O(n). Section 7.2: Computing the Voronoi Diagram: pp. 151—160. Објавио га је Стивен Фортун 1986. у свом раду "Алгоритам покретне линије за Воронојеве дијаграме."Steven Fortune. A sweepline algorithm for Voronoi diagrams. . Yorktown Heights, New York, United States. ACM Digital Library
Опис алгоритма Алгоритам одржава покретну линију и обалску линију, које се обе крећу кроз раван како алгоритам напредује. Покретна линија је права линија, и можемо по договору претпоставити да је вертикална и да се креће слева надесно. У било ком тренутку током трајања алгоритма тачке лево од покретне линије ће бити уграђене у Воронојев дијаграм, док тачке десно од покретне линије нису још увек разматране. Обалска линија није линија, већ комплексна крива са леве стране покретне која се састоји од делова парабола; она раздваја део равни у којем Воронојев дијаграм може бити познат, без обзира на тачке десно од покретне линије, од остатка равни. За сваку тачку лево од покретне линије, може се дефинисати парабола тачака које су на подједнаком растојању од те тачке и од покретне линије; обалска линија је граница уније ових парабола. Док покретна линија напредује, темена обалске линије, у којој се две параболе секу, прати ивице Воронојевог дијаграма. Обалска линија напредује чувајући сваку параболу тачно на пола пута између тачака преко којих се претходно прешло покретном линијом и новог положаја покретне линије.
Алгоритам одржава као структуру података бинарно стабло претраге које описује структуру обалске линије и приоритетни ред који садржи потенцијалне будуће догађаје који могу да промене структуру обалске линије. Ови догађаји укључују додавање нове параболе у обалску линију (када покретна линија наиђе на нову улазну тачку) и уклањање криве из обалске линије (када покретна линија постане тангента на кругу кроз неке три улазне тачке чије параболе формирају узастопне сегменте обалске линије). Приоритет сваког таквог догађаја се може одредити на основу x-координате покретне линије у тачки у којој се догађај десио. Сам алгоритам се онда састоји од уклањања следећег догађаја из приоритетног реда, проналажења промена које догађај проузрокује у обалској линији и ажурирања структура података.
Пошто има O(n) догађаја које треба обрадити (сваки је повезан са неком карактеристиком Воронојевог дијаграма) и O(log n) времена за обраду догађаја (сваки се састоји од константног броја операција на бинарном стаблу претраге и приоритетном реду) укупно време је O(n log n).
Псеудокод Псеудокод опис алгоритма.
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
Тежинске локације и дискови
Као што Фортун описује у модификована верзија алгоритма покретне линије може бити искоришћена за конструкцију адитивног тежинског Воронојевог дијаграма, у коме удаљеност до сваке локације (генератора) је померена за тежину локације; ово може бити еквивалентно посматрано као Воронојев дијаграм скупа дискова чији је центар у локацијама са радијусом једнаким тежини локације. Референце
Спољашње везе Фортунов алгоритам имплементиран у Ц-у Фортунов алгоритам имплементиран у C++ Фортунов алгоритам имплементиран у javascript-у
Категорија:Алгоритми