Skip to content

Voronoi decomposition of the surface of a sphere

License

Notifications You must be signed in to change notification settings

uchchwhash/voronoi

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

7 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

About

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.

License

MIT

Requirements

Demonstration

Open voronoi.ipynb in a browser after running jupyter notebook from the root folder.

Documentation

HTML documentation for the program can be generated by running make -C docs html from the root folder (requires Sphinx).

Prior art

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.

About

Voronoi decomposition of the surface of a sphere

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published