Aleph::MinimumEnclosingCircle Class Reference

Smallest circle enclosing a point set (Welzl's algorithm). More...

#include <geom_algorithms.H>

Classes
struct	Circle
	Result type: a circle defined by center and squared radius. More...

Public Member Functions
Circle	operator() (const DynList< Point > &points) const
	Compute the minimum enclosing circle of a point set.
Circle	operator() (std::initializer_list< Point > points) const
	Convenience overload accepting an initializer list.

Static Public Member Functions
static Circle	from_one_point (const Point &a)
	Circle through a single point (degenerate, radius = 0).
static Circle	from_two_points (const Point &a, const Point &b)
	Smallest circle with a and b on its boundary (diameter).
static Circle	from_three_points (const Point &a, const Point &b, const Point &c)
	Circumscribed circle through three points.

Static Private Member Functions
static Circle	mec_with_point (const Array< Point > &pts, size_t n, const Point &p1)
	Minimum enclosing circle with boundary point p1.
static Circle	mec_with_two_points (const Array< Point > &pts, size_t n, const Point &p1, const Point &p2)
	Minimum enclosing circle with boundary points p1 and p2.
static Circle	welzl_iterative (const Array< Point > &pts)
	Iterative Welzl: three nested loops.

Detailed Description

Smallest circle enclosing a point set (Welzl's algorithm).

Given a set of 2D points, computes the minimum enclosing circle (MEC) using an iterative version of Welzl's randomized incremental algorithm.

Complexity

• Expected time: O(n)
• Worst-case time: O(n³) (extremely unlikely with random shuffle)
• Space: O(n) for the working copy

Usage

DynList<Point> pts;
pts.append(Point(0, 0));
pts.append(Point(4, 0));
pts.append(Point(2, 3));
 
MinimumEnclosingCircle mec;
auto circle = mec(pts);
// circle.center, circle.radius(), circle.contains(p)

Definition at line 1082 of file geom_algorithms.H.

Member Function Documentation

from_one_point()

static Circle Aleph::MinimumEnclosingCircle::from_one_point ( const Point &  a )

inlinestatic

Circle through a single point (degenerate, radius = 0).

Definition at line 1105 of file geom_algorithms.H.

Referenced by mec_with_point(), and welzl_iterative().

from_three_points()

static Circle Aleph::MinimumEnclosingCircle::from_three_points ( const Point &  a, const Point &  b, const Point &  c  )

inlinestatic

Circumscribed circle through three points.

If the three points are collinear, returns the diameter circle of the farthest pair.

Definition at line 1121 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Point::distance_squared_to(), from_two_points(), Aleph::Point::get_x(), and Aleph::Point::get_y().

Referenced by mec_with_two_points(), and TEST_F().

from_two_points()

static Circle Aleph::MinimumEnclosingCircle::from_two_points ( const Point &  a, const Point &  b  )

inlinestatic

Smallest circle with a and b on its boundary (diameter).

Definition at line 1111 of file geom_algorithms.H.

References Aleph::Point::distance_squared_to(), and Aleph::Point::midpoint().

Referenced by from_three_points(), mec_with_two_points(), and TEST_F().

mec_with_point()

static Circle Aleph::MinimumEnclosingCircle::mec_with_point ( const Array< Point > &  pts, size_t  n, const Point &  p1  )

inlinestaticprivate

Minimum enclosing circle with boundary point p1.

Definition at line 1198 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::MinimumEnclosingCircle::Circle::contains(), from_one_point(), and mec_with_two_points().

Referenced by welzl_iterative().

mec_with_two_points()

static Circle Aleph::MinimumEnclosingCircle::mec_with_two_points ( const Array< Point > &  pts, size_t  n, const Point &  p1, const Point &  p2  )

inlinestaticprivate

Minimum enclosing circle with boundary points p1 and p2.

Definition at line 1208 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::MinimumEnclosingCircle::Circle::contains(), from_three_points(), from_two_points(), and k.

Referenced by mec_with_point().

operator()() [1/2]

Circle Aleph::MinimumEnclosingCircle::operator() ( const DynList< Point > &  points ) const

inline

Compute the minimum enclosing circle of a point set.

Parameters

points

Input point set (unmodified; a working copy is made).

Returns

The smallest Circle containing every input point.

Exceptions

std::domain_error

if the point set is empty.

Definition at line 1164 of file geom_algorithms.H.

References ah_domain_error_if, Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::HTList::Iterator::has_curr(), and welzl_iterative().

operator()() [2/2]

Circle Aleph::MinimumEnclosingCircle::operator() ( std::initializer_list< Point >  points ) const

inline

Convenience overload accepting an initializer list.

Definition at line 1188 of file geom_algorithms.H.

References Aleph::DynList< T >::append(), and l.

welzl_iterative()

static Circle Aleph::MinimumEnclosingCircle::welzl_iterative ( const Array< Point > &  pts )

inlinestaticprivate

Iterative Welzl: three nested loops.

Definition at line 1221 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::MinimumEnclosingCircle::Circle::contains(), from_one_point(), and mec_with_point().

Referenced by operator()().

---

The documentation for this class was generated from the following file:

• geom_algorithms.H