Efficiently computes the smallest bounding ball of a point set, in arbitrary number of dimensions.
A Python module to efficiently compute the smallest bounding ball of a point set, in arbitrary number of dimensions.
The algorithm runs in approximatively linear time in respects to the number of input points. This is NOT a derivative nor a port of Bernd Gaertner’s C++ library.
This project is licensed under the MIT License
miniball 1.0 requires
- Python 2.7, >=3.4
$ pip install miniball
Here is how you can get the smallest bounding ball of a set of points S
>>> import numpy >>> import miniball >>> S = numpy.random.randn(100, 2) >>> C, r2 = miniball.get_bounding_ball(S)
The center of the bounding ball is C, its radius is the square root of r2. The input coordinates S can be integer, they will automatically cast to floating point internally.
And that’s it ! miniball does only one thing with one function.
The algorithm implemented is Welzl’s algorithm. It is a pure Python implementation, it is not a binding of the popular C++ package Bernd Gaertner’s miniball.
The algorithm, although often presented in its recursive form, is here implemented in an iterative fashion. Python have an hard-coded recursion limit, therefore a recursive implementation of Welzl’s algorithm would have an artificially limited number of point it could process.
This project is licensed under the MIT License - see the [LICENSE.md](LICENSE.md) file for details
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
|Filename, size||File type||Python version||Upload date||Hashes|
|Filename, size miniball-1.0.4.tar.gz (4.9 kB)||File type Source||Python version None||Upload date||Hashes View|