search

hbf / miniball

Fast computation of the smallest enclosing ball of a point set, in low or moderately high dimensions.
133 stars 41 forks source link

the calculation for a pointset doesn't terminate #19

Open FrankBuss opened 8 years ago

FrankBuss commented 8 years ago

The calculation for the data at http://www.frank-buss.de/tmp/test.data doesn't terminate. To reproduce the bug: PointSet pts = PointSetUtils.pointsFromStream(new FileInputStream("c:\tmp\test-bug.data")); new Miniball(pts); Tested with Java version 1.7.0_71, 64 bit on Windows 7. I could already reduce the input elements to reproduce the bug, it terminates without the last element.

I need this for a production system for a company and it gets expensive if such an error happens on the server. Maybe I'm doing something wrong, like duplicate points etc., but if it is a bug in your library, do you know a more stable Java implementation which works for any inputs? Doesn't need to be as fast as your library and needs only 3 dimensions.

paulharris commented 8 years ago

Please try my open pull request #13

FrankBuss commented 8 years ago

Sorry, this doesn't inspire confidence in this software. How can I be sure that this works for all cases and that there is not another bug? I'm now using Apache Commons Math with the integrated WelzlEncloser, which works for all data I've fed to it so far without problems (douzens of sets with thousands of points each, the miniball termination was in set 3), and it is only about 3 times slower than miniball (e.g. 60 milliseconds for some thousand points instead of 20 milliseconds). But feel free to test your patch with my testdata and to improve miniball, maybe it will mature in some years.

paulharris commented 8 years ago

Up to you. Its not my software, but I've been feeding the library (with my patch) many different datasets for a few years now without issues.

I updated my copy and added your test, but you didn't specify what the answer should be for your test.

This is what my little test program gave as a result, is it correct?

Squared radius = 1.45545963354282162e+03 Radius = 3.81504866750454639e+01 Center = 4.04006902766964140e+03 6.11139274652161362e+02 4.88799924089688921e+03

If so then I'll adjust the test (give it the answer) and push up the commit with the new test.

Cheers, Paul

FrankBuss commented 8 years ago

I don't know the answer, but the WelzlEncloser in Apache Common Math with 0.001 for the tolerance parameter, gives nearly the same answer: center: 4040.0690276696414, 611.1392746521614, 4887.99924089689 radius: 38.15048667504536

paulharris commented 8 years ago

I've pushed the new test to my paulharris/miniball repo, I imagine the Java version is still affected, but I'm not a Java guy yet.

Would you be able to help out a little (or a lot)? What is the procedure to compile and run your test?