MarbleMice.com

Repost from old site.
Introduction
In this article I am going to discuss how given a set of points you can generate a circle that encompasses them. Calculation of the best possible fit for n points has an O(n^3) dependence making it unsuitable for large data sets or real time applications. We have to use our brains to generate a good approximation to the optimum solution; I should say use other peoples brains as this is a well researched topic. To keep this article a reasonable length I will focus on a few algorithms that have guaranteed O(n) behaviour. These tend to be the simplest to implement but it does mean we exclude some good algorithms like the one discussed in Eberly[1].

For this article I work in 2 dimensions but all the techniques easily transfer to 3 dimensions and beyond. I have resisted the temptation to templatise my code.

The C++ source code can be downloaded from here

While it is not the aim of this article to introduce the reasons for generating bounding circles a quick overview for the motivation behind bounding circles and for that matter sphere and boxes should be given. The classic example is collision detection between two complex polygons. Testing to see whether two polygons overlap is a slow operation. In comparison testing to see whether two circles overlap is very fast. If you have a circle or sphere that encompasses each polygon you can do a quick test to see if the circles overlap. If they don’t overlap you know the two polygons are not colliding without having to do any complex computations. If they do overlap then you must do a polygon-polygon overlap test to be sure. When testing between many different polygons using a bounding shape of some kind can drastically speed up the calculation. The tighter the bounding shape fits the better as you are less likely to have situation where the bounding shapes overlap but the polygons do not. I recommend the book Real Time Collision Detection [2] if you are interested in learning more.

Averaging Method
The idea of this algorithm is to scan over the points and generate the average position in the set of points. A rescan the points is done to find the maximum distance any point is from the average position, giving the radius of the bounding circle. This algorithm takes seconds to implement but can lead to some overly large bounding circles. The reasoning for this is clear if you consider a set of three points (0, 0), (0, 10), (0, 11). Applying the algorithm we find the bounding circle to be centred at (0, 7) with a radius of 7. It is easy to spot a tighter bounding circle at a position (0, 5) and a radius of 6. In fact the best one it at (0, 5.5) with a radius of 5.5, but is perhaps a little harder to spot off the top of your head.

This algorithm performs the least well of all bounding circle algorithms because of this I have used it as the benchmark against which to compared others.

Bounding Box Method
The Bounding box method attempts to counter the weakness of the averaging method by generate a better centre point for the bounding circle. It scans the whole data set and remembers the extremes of the x and y directions. From this we can easily generate an axis aligned bounding box. By taking the centre of the bounding box as the centre point of the bounding circle we generate the bounding circle.

This method results in a tighter bounding circle than the averaging method and I can’t think of an example where this generates a very bad centre points.

Ritter Method
The bounding box approach, like all the algorithms here, only approximates the centre of the ideal bounding circle so the question we ask is can we generate a better approximation while still maintaining the linear dependence on the number of points in the set. This is what Ritter [3] described and in tests it performs better than the bounding box method. His basic idea is to approximate the centre point and then gradually grow a circle, from a radius of zero, to encompass all the points. We consider each point in turn and when he encountered a point not inside his bounding circle we adjust both the radius and the centre point.

The quality of the resulting bounding box is dependent on the quality of the initial approximation. In his original algorithm he finds the extremes of the set of points and from this set of extreme points finds the two most distant points. Halfway between these two points is taken as the initial centre point.

Ritter Iterative Method
A suggestion [2] has been made to use the Ritter method in an iterative way. That is feed the result of an application of the Ritter method back into itself as the initial approximation for the centre point. Before feeding the results back in, you should randomise the data set so we consider the points in a different order and slightly shrink the radius of the circle being fed in.

Descriptions of the tests
I have implemented all the discussed algorithms, using C++, in order to test them against each other. For a baseline measurement I took the results from the averaging method. The tests consisted of a set of random points placed within a rectangle. The number of points generated also being random. Each algorithm was applied to the set and the resulting circle stored. This was repeated 10000 times and then the average of the radius of the given method divide by the radius obtained from the averaging the point algorithm was generated, along with the standard deviation.

As an update to this article I have added an additional test that compares the results against the perfect bounding circle for the set of points. This time the generated points were constrained to lie inside a circle (instead of a rectangle as in the previous test) , I then generate a few points that lie on the boundary of the circle ensuring the minimum bounding circle is the radius of the constraining circle. I then calculated the average radius generated over a number of runs.

Results
Average ratio of various methods compared with the averaging point method. Lower is better

Averaging method:                       1.000 Std. Dev: 0.0000

Axis Align Bounding box method:   0.973 Std. Dev: 0.0612

Ritter method:                             0.954 Std. Dev: 0.0617

Ritter iterative method:                 0.916 Std. Dev: 0.0535

It is clear that the averaging of points is the worst performing approach as you would expect. The Ritter method consistently beat the Bounding box method but only by a small amount. The iterative Ritter method demonstrated a significant improvement over the standard Ritter method with only a tiny amount of additional complexity in the code.

The results for the test with the know perfect bounding circle are given below

Ratio of various method compared with the averaging method. Lower is better.

Bounding box method:    0.761972       Std Dev: 0.0268063

Ritter method:                0.68882         Std Dev: 0.031524

Ritter iterative method:    0.653785       Std Dev: 0.025013

Average radius for the algorithms. Perfect bounding circle is 100.

Averaging method:         153.992

Bounding box method:   117.197

Ritter method:               105.908

Ritter Iter method:         100.542

The first thing we can see is the algorithms perform much better compared with the averaging method. This is made clearer when we look at the average radius generated, the Averaging of the point’s algorithm gives an average bounding circle radius that is over 50% bigger than the perfect one. The bounding box method improves on this but it is the Ritter methods that really shine. The basic Ritter method is, on average, within 6% of the perfect circle, which is consistent with the 5% quoted in Graphic Gems[3] and the iterative method produces a near perfect bounding circle, to within 0.5% on average. It is worth bearing in mind that while I am quoting radii, algorithms that make use of bounding circles are highly dependant on the tightness of the fit, basically the area of the bounding circle. The area is proportional to r^2 meaning there are substantial gains to be had using the Ritter algorithm. Of course the gain for spheres is even greater.

Randomly produced set of data points may not provide reliable comparison with real world datasets. For instance as the number of data points increases in a random spread the averaging method becomes more accurate and making the other algorithms look as if they provide little improvement. If in the code example provided if you vary the mean number of points generated you will see the results considerably.

Unfortunately with 2D algorithms there is little in the way of free and easily available datasets to test the algorithms. With hindsight I should have implemented the algorithms in 3D as then I would have access to the numerous free 3D models available on the internet to test the algorithms. I may in the future return to this code and extend it to 3D to compare the results as the work to do so is fairly small.

As it stands this articles provides a working implementation in 2D for various bounding circle algorithms that could provide a good improvement over the Averaging method. Given that the complexity of any of these algorithms is fairly low I would choose to use the iterative Ritter method unless given a reason not to do so.

Comments are welcome, or if you have run these algorithms on real data I would be very interested in the comparisons between the algorithms.

References:
[1] Geometric tools for computer graphics, Schneider and Eberly, Morgan Kaufmann.
[2] Real-Time Collision Detection, Christer Ericson, Morgan Kaufmann.
[3] An efficient Bounding sphere. Graphic Gems, Jack Ritter, P301.

Update 10-April-2006: Thanks to Christer Ericson for spotting errors in my implementation of the iterative Ritter method and letting me know!

Update 12-April-2006: Added a comparison with a perfect bounding circle.