Fortune's algorithm
≈ 4 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
Fortune's algorithm is a sweep line algorithm for generating a Voronoi diagram from a set of points in a plane using O(n log n) time and O(n) space. It was originally published by Steven Fortune in 19861 in his paper "A sweepline algorithm for Voronoi diagrams."
Fortune's algorithm is a sweep line algorithm for generating a Voronoi diagram from a set of points in a plane using O(n log n) time and O(n) space. It was originally published by Steven Fortune in 1986 in his paper "A sweepline algorithm for Voronoi diagrams."
Pseudocode
Pseudocode description of the algorithm. let \scriptstyle *(z) be the transformation \scriptstyle *(z)=(z_x,z_y+d(z)) , where \scriptstyle d(z) is the Euclidean distance between and the nearest site let be the "beach line" let \scriptstyle R_p be the region covered by site . let \scriptstyle C_{pq} be the boundary ray between sites and . let \scriptstyle S be a set of sites on which this algorithm is to be applied. let \scriptstyle p_1,p_2,...,p_m be the sites extracted from with minimal -coordinate, ordered by -coordinate let DeleteMin( ) be the act of removing the lowest and leftmost site of (sort by y unless they're identical, in which case sort by x) let be the Voronoi map of which is to be constructed by this algorithm Q \gets {p_1,p_2,\dots,p_m,S} create initial vertical boundary rays \scriptstyle C_{p_1,p_2}^0,C_{p_2,p_3}^0,\dots,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,\dots,*(R_{p_{m-1}}),C_{p_{m-1},p_m}^0,*(R_{p_m}) while not IsEmpty( ) do ← DeleteMin( ) case of is a site in \scriptstyle *(V) : find the occurrence of a region \scriptstyle *(R_q) in containing , bracketed by \scriptstyle C_{rq} on the left and \scriptstyle C_{qs} on the right create new boundary rays \scriptstyle C_{pq}^- and \scriptstyle C_{pq}^+ with bases replace \scriptstyle *(R_q) with \scriptstyle *(R_q),C_{pq}^-,*(R_p),C_{pq}^+,*(R_q) in delete from any intersection between \scriptstyle C_{rq} and \scriptstyle C_{qs} insert into any intersection between \scriptstyle C_{rq} and \scriptstyle C_{pq}^- insert into any intersection between \scriptstyle C_{pq}^+ and \scriptstyle C_{qs} is a Voronoi vertex in \scriptstyle *(V) : let be the intersection of \scriptstyle C_{qr} on the left and \scriptstyle C_{rs} on the right let \scriptstyle C_{uq} be the left neighbor of \scriptstyle C_{qr} and let \scriptstyle C_{sv} be the right neighbor of \scriptstyle C_{rs} in if \scriptstyle q_y = s_y , create a new boundary ray \scriptstyle C_{qs}^0 else if is right of the higher of and , create \scriptstyle C_{qs}^+ else create \scriptstyle C_{qs}^- endif replace \scriptstyle C_{qr},*(R_r),C_{rs} with newly created \scriptstyle C_{qs} in delete from any intersection between \scriptstyle C_{uq} and \scriptstyle C_{qr} delete from any intersection between \scriptstyle C_{rs} and \scriptstyle C_{sv} insert into any intersection between \scriptstyle C_{uq} and \scriptstyle C_{qs} insert into any intersection between \scriptstyle C_{qs} and \scriptstyle C_{sv} record as the summit of \scriptstyle C_{qr} and \scriptstyle C_{rs} and the base of \scriptstyle C_{qs} output the boundary segments \scriptstyle C_{qr} and \scriptstyle C_{rs} endcase endwhile output the remaining boundary rays in
Weighted sites and disks
References
External links
Steven Fortune's C implementation Fortune's Voronoi algorithm implemented in C++ Fortune's algorithm implemented in JavaScript archived on GitHub as of August 2015 Fortune's Algorithm Visualization as of 2025 access is blocked
Text derived from https://en.wikipedia.org/w/index.php?oldid=1320640602 under CC BY-SA 4.0; modifications have been made.
References
- ↩Wikipedia “Fortune's algorithm” publication date (×1) · confidence 0.95 revision URL