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

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

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.3
Filename, size File type Python version Upload date Hashes
Filename, size miniball-1.0.3-py2-none-any.whl (4.6 kB) File type Wheel Python version py2 Upload date Hashes View hashes
Filename, size miniball-1.0.3-py3.6.egg (5.5 kB) File type Egg Python version 3.6 Upload date Hashes View hashes
Filename, size miniball-1.0.3-py3-none-any.whl (4.6 kB) File type Wheel Python version py3 Upload date Hashes View hashes
Filename, size miniball-1.0.3.tar.gz (4.4 kB) File type Source Python version None Upload date Hashes View hashes

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN DigiCert DigiCert EV certificate StatusPage StatusPage Status page