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.
Source Distribution
MiniballCpp-0.2.2.tar.gz
(8.0 kB
view hashes)
Built Distribution
Close
Hashes for MiniballCpp-0.2.2-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 52eb238c3eb2594940248f9a6ec56c70945025c644d853bf7e3804b65e9ef2a0 |
|
MD5 | 404b468b8229a850d7d733f8e11b750a |
|
BLAKE2b-256 | 7a138e013a6d5f4195be74afd835e804606bfdc1945234a33c4cd5d6fdee995e |