voronoifortune is an R port of a program written in C by Steven Fortune. It performs Voronoi tessellation and Delaunay triangulation using a very efficient algorithm described in:
Fortune, S. (1987) A sweepline algorithm for Voronoi diagrams. Algorithmica 2: 153-174. Doi:
10.1007/BF01840357.
Two main changes were made to the original C code:
The package should be easy to install giving R and a C compiler (i.e., standard install from sources of an R package).
The main function is named voronoi() and takes as main argument a matrix with two columns giving the $x$ and $y$ coordinates. There are two options:
sorted = FALSE: if the coordinates are already sorted in increasing order first by $y$, then by $x$ (see ?order in R).debug = FALSE: if debug = TRUE (very) verbose of the computation details are printed.The returned list has four elements:
Triplets: the triangles of the Delaunay triangulation;Vertices: the vertices of the Voronoi tessellation;Edges: the edges (or segments) of the tessellation;Lines: a description of the previous segments (some of them are semi-infinite).There are a print() and a plot() methods to display the results.
I found two packages performing similar operations on CRAN: deldir and tessellation. Another implementation is provided by the package BH with a C++ code not tested here (see below for a comment about performance scaling).
First, these packages do not have the same functionalities: the present one considers only 2-D data, whereas tessellation can do tessellation in 3-D.
Second, Fortune's algorithm is much faster than the algorithms implemented in the two other packages. Next is an example with 1000 points:
R> library(deldir)
deldir 0.1-25
R> library(tessellation)
R> library(voronoifortune)
Attachement du package : ‘voronoi’
L'objet suivant est masqué depuis ‘package:tessellation’:
voronoi
We note that tessellation has also a function named voronoi(), but since the present package was loaded after, we don't need to call it with the namespace operator. In case of doubt, voronoifortune::voronoi() and tessellation::voronoi() can be used.
R> n <- 1000L
R> xx <- runif(n)
R> yy <- runif(n)
R> X <- cbind(xx, yy)
R> system.time(res <- voronoi(X))
utilisateur système écoulé
0.001 0.000 0.001
R> system.time(dd <- deldir(xx, yy))
utilisateur système écoulé
0.03 0.00 0.03
R> system.time(del <- delaunay(X))
utilisateur système écoulé
0.359 0.003 0.365
Fortune's algorithm has been reported to scale with $O(n)$ which seems to be true in practice:
R> n <- 1e4L
R> xx <- runif(n)
R> yy <- runif(n)
R> system.time(res <- voronoi(X))
utilisateur système écoulé
0.010 0.001 0.012
R> system.time(dd <- deldir(xx, yy))
utilisateur système écoulé
2.103 0.014 2.125
R> system.time(del <- delaunay(X))
utilisateur système écoulé
7.948 0.383 8.369
The C++ code in BH includes a comment stating that its algorithm has complexity $O(n\ln n)$.
The results seem identical for all functions. Here's an example with n <- 100 and the default plotting parameters of each package (from left to right: tessellation, deldir, voronoifortune):
R> layout(matrix(1:3, 1))
R> plotDelaunay2D(del)
R> plot(dd)
R> plot(res)