Welzl's Minimum Sphere Algorithm Demystified
by Eli Kara

Contents   Page 1   Page 2   Page 3   Page 4   Source code   Printable version   Discuss this article

The tester and the source code

An implementation of the algorithm for 2D circles is given in the form of a simple Java-based tester. The tester provides a way for us to see the algorithm in action and see simple statistics about the number of point tests made (total iterations) and the number of restarts (m) of the algorithm.

To run it, issue the following command in the directory containing the JAR file:

> java -jar WelzlSphere.jar

To use the tester, input the number of input points wanted and click 'Generate'. This will generate that amount of points in random locations and display them.

Once points are randomized, 'Create Sphere' can be used to initiate the sphere generation. The sphere is then displayed on screen along with the points. Once a sphere is created the algorithm statistics appear in the status bar and are left there until a new sphere is created.

The tester supports a maximum number of 10000 points. The number is chosen arbitrarily in the code.

In terms of the source code – It is a very simple implementation and not production code. Aside for a circle class that supports construction of circles from various amounts of points there are no custom classes to make the code simpler (a lack of a simple vector class meant some calculations are just inlined).

Some more notes:

• All coordinates and radii are in a logical coordinate system of a rectangular area of 10000 on 10000. They are later transformed to client-area coordinates when drawing
• Point locations are randomized in a way that makes it more likely for the entire circle to be visible. See the randomizePoints function for details.
• The actual drawing area is always a square. The smaller dimension (width or height) is used as a scale factor in order to make the transformation and drawing simpler. Naturally, if the frame is resized the points and circle have to be transformed to the center of the client-area.
• The limit of 10000 points is arbitrary and is only used to see how fast the algorithm can run
• The tester has had very little optimization. The algorithm runs as expected but with a large number of points the drawing delay is noticeable. Although it's very easy to make it run orders of magnitude faster this is not really a problem.
• All the sphere's radii are squared when the algorithm is running, to save the cost of performing a square root operation. Once the algorithm ends, the final sphere's radius is square-rooted.

Conclusion

Spheres can be a great bounding volume in collision detection and are generally great geometric entities. The algorithm described here (Welzl 1991) is an efficient approach at computing the minimum enclosing sphere of a set of points, in real time.

True, spheres and other bounding volumes can be computed in a pre-processing step but the need for a good real-time algorithm still exists (and it also helps to speed up pre-processing, whether the algorithm runs when loading a scene or when an external tool creates the bounding volume).

References

1. [Welzl91] - Smallest enclosing disks (balls and ellipsoids) "New Results and New Trends in Computer Science", (H. Maurer, Ed.), Lecture Notes in Computer Science 555 (1991) 359-370.

2. [Eberly03] - Geometric Tools for Computer Graphics by Philip J. Schneider and David H. Eberly, The Morgan Kaufmann Series in Computer Graphics and Geometric Modeling Copyright © 2003 by Elsevier Science (USA), Philip J. Schneider, and David H. Eberly