Skip to main content

Efficiently computes the smallest bounding ball of a point set, in arbitrary number of dimensions.

Project description

miniball on PyPI miniball on TravisCI MIT License badge

miniball

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

Requirements

miniball 1.0 requires

  • Python 2.7, >=3.4
  • Numpy

Installation

$ pip install miniball

Usage

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.

Implementation notes

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.

Authors

License

This project is licensed under the MIT License - see the [LICENSE.md](LICENSE.md) file for details

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for miniball, version 1.0.4
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

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring DigiCert DigiCert EV certificate Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page