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
Description
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+)
-
- SmallestEnclosingCircle.java (computation functions)
- SmallestEnclosingCircleTest.java (JUnit test suite)
- TypeScript / JavaScript
-
- smallest-enclosing-circle.ts / smallest-enclosing-circle.js (computation functions)
- smallest-enclosing-circle-demo.ts / smallest-enclosing-circle-demo.js (the demo on this page)
- Python
-
- smallestenclosingcircle.py (computation functions)
- smallestenclosingcircle-test.py (test suite)
- C# (.NET 4.0+)
-
- SmallestEnclosingCircle.cs (computation functions)
- SmallestEnclosingCircleTest.cs (test suite)
- C++ (C++11 and above)
-
- SmallestEnclosingCircle.cpp (computation functions)
- SmallestEnclosingCircle.hpp (header file)
- SmallestEnclosingCircleTest.cpp (test suite)
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+