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.1 requires

  • Python >= 3.5
  • Numpy >= 1.17

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.

Result accuracy

Although the algorithm returns exact results in theory, in practice it returns result only exact up to a given precision. The epsilon keyword argument allows to control that precision, it is set to 1e-7 by default.

>>> import numpy
>>> import miniball
>>> S = numpy.random.randn(100, 2)
>>> C, r2 = miniball.get_bounding_ball(S, epsilon=1e-7)

Repeatability

The algorithm to compute bounding balls relies on a pseudo-random number generator. Although the algorithms return an exact solution, it is only exact up to the epsilon parameter. As a consequence, running the get_bounding_ball function twice on the same input might not return exactly the same output.

By default, each call to get_bounding_ball pull out a new, freshly seeded pseudo-random number generator. Therefore, if you wish to get repeatable results from get_bounding_ball, you have to (and only have to) pass the same pseudo-random number generator, using with the rng keyword argument

>>> import numpy
>>> import miniball
>>> S = numpy.random.randn(100, 2)
>>> rng = numpy.random.RandomState(42)
>>> C, r2 = miniball.get_bounding_ball(S, rng = rng)

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 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.

Source Distribution

miniball-1.1.0.tar.gz (6.3 kB view hashes)

Uploaded source

Supported by

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