Skip to main content

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

Project description

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)

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


Release history Release notifications

Download files

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

Filename, size & hash SHA256 hash help File type Python version Upload date
miniball-1.0.2-py2-none-any.whl (4.5 kB) Copy SHA256 hash SHA256 Wheel py2
miniball-1.0.2.tar.gz (4.1 kB) Copy SHA256 hash SHA256 Source None

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 SignalFx SignalFx Supporter DigiCert DigiCert EV certificate StatusPage StatusPage Status page