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

## Project description

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

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