Skip to main content
Join the official 2019 Python Developers SurveyStart the survey!

Smallest Enclosing Balls of Points

Project description

These are python bindings to Bernd Gärtners miniball software.

Setup

To install miniball clone the repository and run the setup script:

python setup.py install

There is also a package for Arch Linux: https://aur.archlinux.org/packages/python-miniball/

Example

import math
import random
import miniball

P = [(random.uniform(0, 100), random.uniform(0, 100)) for i in range(10000)]
mb = miniball.Miniball(P)
print('Center', mb.center())
print('Radius', math.sqrt(mb.squared_radius()))

Notes

This algorithm has some numerical challenges worth mentioning. The result may deviate from the optimal result by 10 times the machine epsilon and sometimes even more:

P = [(642123.5528970208, 5424489.146461355),
     (651592.349934072, 5424969.380667617),
     (642591.1068130962, 5425775.320365907),
     (646380.0282527813, 5418648.987550308),
     (648098.891235107, 5426586.3920675),
     (650011.5835629451, 5426132.820254512),
     (650297.6960375579, 5419125.777007122),
     (645249.2122321032, 5421055.739722816),
     (645333.9125837489, 5426228.852409409)]

mb = miniball.Miniball(P)
if not mb.is_valid():
    print('Possibly invalid!')
print('Relative error', mb.relative_error())

If this is a problem for you, shifting the input towards (0,0) may help:

minx = min(P, key=lambda p: p[0])[0]
miny = min(P, key=lambda p: p[1])[1]

P = [(p[0] - minx, p[1] - miny) for p in P]

mb = miniball.Miniball(P)
if not mb.is_valid():
    print('Possibly invalid!')
print('Relative error', mb.relative_error())

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 MiniballCpp, version 0.2.1
Filename, size File type Python version Upload date Hashes
Filename, size MiniballCpp-0.2.1.tar.gz (7.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 SignalFx SignalFx Supporter DigiCert DigiCert EV certificate StatusPage StatusPage Status page