Unexpected results of minEnclosingCircle in OpenCV

Question

I have recently used the function minEnclosingCircle of OpenCV (2.4.2) because I needed to measure the diameters of a blob of points.

After a while I realized that the results were not correct, so I decided to write a small routine that calculates the diameters of a really small set of points.

I tested the function against:

• 1 single point
• 2 - 4 points in a row
• Squares of different size formed by only 4 corner points

In the table below you can see the results of my tests:

Note         Diameter           Center                                         Points
1x1             2.000       (1.0, 1.0)                                       [[1, 1]]
2x1             2.000       (1.0, 1.5)                               [[1, 1], [1, 2]]
3x1             2.060       (1.0, 2.0)                       [[1, 1], [1, 2], [1, 3]]
4x1             3.090       (1.0, 2.5)               [[1, 1], [1, 2], [1, 3], [1, 4]]
2x2             2.000       (1.5, 1.5)               [[1, 1], [1, 2], [2, 1], [2, 2]]
3x3             2.913       (2.0, 2.0)               [[1, 1], [1, 3], [3, 1], [3, 3]]
4x4             4.370       (2.5, 2.5)               [[1, 1], [1, 4], [4, 1], [4, 4]]
6x6             7.283       (3.5, 3.5)               [[1, 1], [1, 6], [6, 1], [6, 6]]
8x8            10.196       (4.5, 4.5)               [[1, 1], [1, 8], [8, 1], [8, 8]]
9x9            11.653       (5.0, 5.0)               [[1, 1], [1, 9], [9, 1], [9, 9]]
16x16          21.850       (8.5, 8.5)           [[1, 1], [1, 16], [16, 1], [16, 16]]
10x10          13.110       (5.5, 5.5)           [[1, 1], [1, 10], [10, 1], [10, 10]]
100x100       144.207     (50.5, 50.5)       [[1, 1], [1, 100], [100, 1], [100, 100]]
1000x1000    1455.183   (500.5, 500.5)   [[1, 1], [1, 1000], [1000, 1], [1000, 1000]]

I have already seen that the function does not return a radius smaller than 1, so the minimum diameter I get is 2.0.

Apart from that, the function is always returning a radius bigger than I would expect. For instance the 10x10 square would have a radius of about 12.726 instead of 13.110. The error increases with the size of the square: for a square of 1000x1000 I would expect 1412.5 instead of 1455.

Actually, I realized that the relative error is always about 3%.

How can I explain this strange behavior?

Answer 1

I tried to solve the same problem using another library called Miniball.

The results obtained with Miniball are correct. At this point I guess that the algorithm used in minEnclosingCircle contains some error.

Answer 2

For the sake of completeness, there are several implementations of algorithms out there to solve the Smallest enclosing balls problem.

• For 2D and 3D, Gärtner's implementation, mentioned also in another answer to this question, is probably the fastest.

• For higher dimensions (up to 10,000, say), take a look at https://github.com/hbf/miniball, which is the implementation of an algorithm by Gärtner, Kutz, and Fischer (note: I am one of the co-authors).

• For very, very high dimensions, core-set (approximation) algorithms will be faster.

Note: If you are looking for an algorithm to compute the smallest enclosing sphere of spheres, you will find a C++ implementation in the Computational Geometry Algorithms Library (CGAL). (You do not need to use all of CGAL; simply extract the required header and source files.)

Answer 3

I believe, that there is a factor 1.03 wrong in the subfunction icvFindEnslosingCicle4pts_32f -- it's multiplied to the radius but never divided again. I opened a bug report with a simple fix at http://code.opencv.org/issues/3362