最小的点包围球
MiniballCpp的Python项目详细描述
这些是到bernd g_rtnersminiball software的python绑定。
设置
要安装miniball克隆存储库并运行安装脚本:
python setup.py install
还有一个针对arch linux的包:https://aur.archlinux.org/packages/python-miniball/
示例
importmathimportrandomimportminiballP=[(random.uniform(0,100),random.uniform(0,100))foriinrange(10000)]mb=miniball.Miniball(P)print('Center',mb.center())print('Radius',math.sqrt(mb.squared_radius()))
注释
该算法在数值上有一些挑战值得一提。结果可能偏离最佳结果 是机器epsilon的10倍,有时甚至更多:
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)ifnotmb.is_valid():print('Possibly invalid!')print('Relative error',mb.relative_error())
如果这是您的问题,将输入移到(0,0)可能会有帮助:
minx=min(P,key=lambdap:p[0])[0]miny=min(P,key=lambdap:p[1])[1]P=[(p[0]-minx,p[1]-miny)forpinP]mb=miniball.Miniball(P)ifnotmb.is_valid():print('Possibly invalid!')print('Relative error',mb.relative_error())