Project Nayuki

Smallest enclosing circle

Demo (JavaScript)

This JavaScript program computes the smallest circle that encloses an arbitrary set of points in the plane. Points defining the circumference are colored red; points in the interior are colored gray. Instructions for manual positioning mode:

  • Left-click in a blank space to add a new point

  • Left-click an existing point and drag to move it

  • Right-click an existing point to delete it


Although the problem looks easy to solve visually, the algorithm is in fact moderately long and quite tricky. (This deceptive difficulty is a common theme in computational geometry.) I don’t fully understand how to solve this problem from scratch, and my program’s implementation relies heavily on the mathematics and reasoning covered in the PDF below.

The code implements a variant of Welzl’s algorithm. With randomization, it runs in expected Θ(n) (linear) time, unlike the brute-force Θ(n4) algorithm. Thus it can handle thousands of points with ease.

Source code

Java (SE 7+)
TypeScript / JavaScript
C# (.NET 4.0+)
C++ (C++11 and above)

The Java version is considered the reference version because it has object types and the code is structured more clearly. License: GNU Lesser General Public License v3.0+

More info