smallest_enclosing_circle/
lib.rs

1//! This crate solves the smallest enclosing circle problem, also known as smallest-circle problem, minimum covering circle problem, or bounding circle problem.
2//! Welzl's algorithm solves this problem in expected `O(n)` runtime.
3//! The original algorithm was formulated as a recursive program, which leads to a call stack overflow for larger problem sizes.
4//! Thus, the iterative implementation in this crate should be preferred.
5//! However, the recursive version is provided for demonstration purposes.
6//!
7//! *Please note that the expected runtime only holds for randomized inputs (i.e., you may want to shuffle your input stream in advance).*
8//! 
9//! The main functionality of this crate is the [`smallest_enclosing_circle`] function.
10//!
11//! The implementation is based on the following work:
12//!
13//! Welzl, E. (1991). Smallest enclosing disks (balls and ellipsoids).
14//! In New results and new trends in computer science (pp. 359-370).
15//! Springer, Berlin, Heidelberg.
16//!
17//! # Examples
18//!
19//! ```
20//! use smallest_enclosing_circle::smallest_enclosing_circle;
21//! use smallest_enclosing_circle::predicates::in_circle::DefaultInCircle;
22//!
23//! // Input: Four corner points of square box of unit size
24//! let circle = smallest_enclosing_circle([[0., 0.], [1., 0.], [1., 1.], [0., 1.]]);
25//! assert_eq!(circle.center(), Some([0.5, 0.5]));
26//! assert_eq!(circle.radius(), Some(f64::sqrt(2.) / 2.));
27//! ```
28//! 
29//! # A Note on Custom Predicates
30//! 
31//! Some of the methods in this crate come in two flavors: with a simple interface (e.g., [`smallest_enclosing_circle`]), and with the possibility to supply your own predicates (e.g., [`smallest_enclosing_circle_with_predicate`]).
32//! This crates uses the [`predicates::orientation::Orientation`] and [`predicates::in_circle::InCircle`] predicates, which you could implement in your own way. 
33//! A possible use case would be that you include the functionality in this crate in, e.g., a higher level algorithm and you need both parts to make the exact same geometric decisions.
34//! However, if you don't specify your own predicates, then the default implementation is used, based on [`geometry_predicates`] crate, which is already a very reasonable choice.
35
36pub mod algorithm;
37pub mod circle;
38pub mod geometry;
39pub mod predicates;
40
41pub use self::algorithm::{smallest_enclosing_circle, smallest_enclosing_circle_with_predicate};
42pub use self::circle::{Circle2D};
smallest_enclosing_circle/lib.rs

smallest_enclosing_circle/
lib.rs
