voronoi is a program to decompose the surface of the unit sphere into Voronoi cells for a set of ‘generators’ on it, and to calculate the areas of the resulting cells.
MIT
Open voronoi.ipynb in a browser after running jupyter notebook from the root folder.
HTML documentation for the program can be generated by running
make -C docs html from the root folder (requires Sphinx).
This implementation was inspired by the wonderfully readable paper:
Renka, R. J. (1997), Algorithm 772: STRIPACK: Delaunay triangulation and Voronoi diagram on the surface of a sphere, ACM Transactions on Mathematical Software 23(3), 416-434.
A more sophisticated implementation is detailed in:
Caroli, M., P. M. de Castro, S. Loriot, O. Rouiller, M. Teillaud, and C. Wormser (2010), Robust and efficient Delaunay triangulations of points on or close to a sphere, in International Symposium on Experimental Algorithms, 462-473, Springer.
Note that an implementation of Caroli et al. (2010) recently landed in SciPy 0.18.0. This project preceeds that with a simpler algorithm which is perhaps a bit slower and a bit less numerically stable but definitely easier to understand.