cyminiball

A Python package to compute the smallest bounding ball of a point cloud in arbitrary dimensions. A Python/Cython binding of the popular miniball utility by Bernd Gärtner.

To my knowledge, this is currently the fastest implementation available in Python. For other implementations see:

• miniballcpp Python binding of the same C++ source (miniball)
• miniball Pure Python implementation (slow)

Installation:

The package is available via pip.

python -m pip install cyminiball

Usage:

import cyminiball as miniball
import numpy as np

d = 2               # Number of dimensions
n = 10000           # Number of points
dt = np.float64     # Data type

points = np.random.randn(n, d)
points = points.astype(dt)
C, r2 = miniball.compute(points)
print("Center:", C)
print("Radius:", np.sqrt(r2))

Additional output can be generated using the details flag and compute_max_chord().

C, r2, info = miniball.compute(points, details=True)
# Returns an info dict with the following keys:
#       center:         center
#       radius:         radius
#       support:        indices of the support points
#       relative_error: error measure realtive to r2
#       is_valid:       numerical validity
#       elapsed:        time required
#
# The maximal chord is the longest line connecting any
# two of the support points. The following extends the
# info dict by the following keys:
#       pts_max:        point coordinates of the two points
#       ids_max:        ids of the two extreme points
#       d_max:          length of the maximal chord
(p1, p2), d_max = miniball.compute_max_chord(points, info=info)

See examples/examples.py for further usage examples

Build package

Building the package requires

• Python 3.x
• Cython
• numpy

First, download the project and set up the environment.

git clone "https://github.com/hirsch-lab/cyminiball.git"
cd cyminiball
python -m pip install -r "requirements.txt"

Then build and install the package. Run the tests/examples to verify the package.

./build_install.sh
python "tests/test_all.py"
python "examples/examples.py"

Performance

For a comparison with miniballcpp, run the below command. In my experiments, the Cython-optimized code ran 10-50 times faster, depending on the number of points and point dimensions.

python "examples/comparison.py"