Infinite loop

[paulharris]

Hi,

I found a small set of points in real world data that causes miniball to enter into an infinite loop.

I was going to patch the problem before submitting a pull request, but I've been busy and I thought you might have a better idea of what should be done.

From what I can tell, the stopping condition isn't a good enough check, when the change gets close to epsilon, 'scale' can become zero, this bit: Float scale = find_stop_fraction(stopper); Seb.C:222

I made a small test program called test_1.C, its in this branch with a very basic Makefile.

cheers, Paul

[hbf]

Sorry for the late reply. I have just taken a look at your example and can reproduce the problem have uncovered, by feeding your 9 points (https://gist.github.com/hbf/7728754) into fromfile.C (https://gist.github.com/hbf/7715996).

It's not yet clear to me how to best fix the cycling that occurs.

[zet23t]

I believe to have run into this issue as well with a point set with about 280 points or so coming from a real world example. The iteration count goes into the millions in that case with no sign of resolving into a solution. It would be nice if a limit and epsilon could be set. In my case, the approximation does not need to be that accurate.

[hbf]

@zet23t As a quick fix you can change the epsilon in the code, there is only one.

I like the idea of adding a max iteration count and a way to set a tolerance. Just for the worst case, ideally that would not be necessary.

[paulharris]

I believe I have fixed this bug, I will re-issue the pull request.

[paulharris]

I have a bunch of fixes and new tests in this pull request, the bit that fixes the main bug is this change:

• if (bound < scale) {
• if (bound > 0 && bound < scale) {

The problem (as stated when I first reported) is that the return value can become zero, which means you are trying to talk to the nearest point by zero units... so the very next loop, it'll likely find the same solution again and again - walk towards X by zero units.

So, check that bound > 0 : ie that you will walk more than zero units.

There is a test a few lines above that involves Epsilon. That test is not stable enough to be relied on.

I have left it in, because it would skip some of the really tiny movements (I think), which saves on a couple of inner_product() calls.

Note that the tests only contain a small number of points - it does not take much to throw the algorithm into an infinite loop without this fix.

[ekpyron]

I also ran into this issue with the following four three-dimensional points:

-2.4500000476837158 5.4889297551596883e-09 -2.4500000476837158 -2.4500000476837158 -2.3189800302247932e-08 2.4500100612640381 2.4500000476837158 -2.6713399492450662e-08 2.4500000476837158 2.4500000476837158 2.1923398207945866e-08 -2.4499900341033936

The pull request fixes this data set as well and the result seems quite reasonable: center: -5.00679e-06 -6.33189e-10 5.00679e-06 radius: 3.46482