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:


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. This randomized algorithm runs in expected linear time, unlike the naive Θ(n4) algorithm. Thus it can handle thousands of points with ease.

Source code

Java (SE 7+)
JavaScript
Python (compatible with 2 and 3)
C#
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