Follow
A really neat thing about #RStats is that it can be super fast for prototyping algorithms.
Fortune's Voronoi algorithm only returns a list of edges. These need to be assembled into actual polygons as a post processing step
The assemblage can easily be O(n^2), but I found a neat O(nlogn) algorithm.
Jiang & Bunke's "An optimal algorithm for extracting the regions of a plane graph" (Pattern Recognition Letters 14, July 1993)
Got an R version working in no time!
https://github.com/coolbutuseless/rvoronoi/blob/polygon-extraction/vignettes/voronoi-polygons.Rmd