Smallest Enclosing Circle

Iterative (and recursive) two-dimensional implementations of Welzl's algorithm for computing the smallest enclosing circle.

Live Demo: wakefullynx.dev/smallest-enclosing-circle-demo/

Crate: crates.io

Documentation: docs.rs

This crate solves the smallest enclosing circle problem, also known as smallest-circle problem, minimum covering circle problem, or bounding circle problem.Welzl's algorithm solves this problem in expected O(n) runtime. The original algorithm was formulated as a recursive program, which leads to a call stack overflow for larger problem sizes. Thus, the iterative implementation in this crate should be preferred. However, the recursive version is provided for demonstration purposes.

Please note that the expected runtime only holds for randomized inputs (i.e., you may want to shuffle your input stream in advance).

The implementation is based on the following work(s):

Welzl, E. (1991). Smallest enclosing disks (balls and ellipsoids). In New results and new trends in computer science (pp. 359-370). Springer, Berlin, Heidelberg.

Examples

use smallest_enclosing_circle::smallest_enclosing_circle;

// Input: Four corner points of square box of unit size
let circle = smallest_enclosing_circle([[0., 0.], [1., 0.], [1., 1.], [0., 1.]]);
assert_eq!(circle.center(), Some([0.5, 0.5]));
assert_eq!(circle.radius(), Some(f64::sqrt(2.) / 2.));

Related Implementations

An equivalent TypeScript implementation is available on GitHub and npm.