Aleph::ClosestPairDivideAndConquer Class Reference

Closest pair of points via divide and conquer. More...

#include <geom_algorithms.H>

Classes
struct	ByYCmp
	Strict weak order for sorting points by (y,x). More...
struct	LexicographicCmp
	Strict weak order for sorting points lexicographically by (x,y). More...
struct	Result

Public Member Functions
Result	operator() (const DynList< Point > &point_set) const
	Compute the closest pair of points.
Segment	closest_segment (DynList< Point > &point_set) const
	Convenience wrapper returning the closest segment.

Static Private Member Functions
static Geom_Number	dist2 (const Point &a, const Point &b)
	Squared Euclidean distance between two points.
static Result	make_result (const Point &a, const Point &b)
	Construct a Result object for a pair (a,b).
static Result	brute_force (const Array< Point > &px, const size_t l, const size_t r)
	Brute-force closest pair on a small subarray.
static Result	recurse (const Array< Point > &px, const size_t l, const size_t r, Array< Point > &py)
	Recursive divide-and-conquer step.

Detailed Description

Closest pair of points via divide and conquer.

Computes the pair of points with minimum Euclidean distance using a classic O(n log n) divide-and-conquer algorithm.

Policy

• Uses exact arithmetic (Geom_Number) for distance comparisons.
• Duplicate points are detected after sorting; if found, returns distance 0.
• Throws if the input has fewer than 2 points.

Complexity

• Time: O(n log n)
• Space: O(n)

Definition at line 843 of file geom_algorithms.H.

Member Function Documentation

brute_force()

static Result Aleph::ClosestPairDivideAndConquer::brute_force ( const Array< Point > &  px, const size_t  l, const size_t  r  )

inlinestaticprivate

Brute-force closest pair on a small subarray.

Parameters

px	Points sorted by x.
l	Left index (inclusive).
r	Right index (exclusive).

Returns

Closest pair in px[l..r).

Precondition

r - l >= 2.

Definition at line 927 of file geom_algorithms.H.

References Aleph::ClosestPairDivideAndConquer::Result::distance_squared, Aleph::divide_and_conquer_partition_dp(), l, make_result(), and r.

Referenced by recurse().

closest_segment()

Segment Aleph::ClosestPairDivideAndConquer::closest_segment ( DynList< Point > &  point_set ) const

inline

Convenience wrapper returning the closest segment.

Parameters

point_set

Input set of points.

Returns

Segment between the closest pair.

Definition at line 1052 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::ClosestPairDivideAndConquer::Result::first, and r.

dist2()

static Geom_Number Aleph::ClosestPairDivideAndConquer::dist2 ( const Point &  a, const Point &  b  )

inlinestaticprivate

Squared Euclidean distance between two points.

Uses exact arithmetic (Geom_Number).

Definition at line 904 of file geom_algorithms.H.

References Aleph::Point::distance_squared_to().

Referenced by make_result().

make_result()

static Result Aleph::ClosestPairDivideAndConquer::make_result ( const Point &  a, const Point &  b  )

inlinestaticprivate

Construct a Result object for a pair (a,b).

Definition at line 912 of file geom_algorithms.H.

References dist2().

Referenced by brute_force(), and recurse().

operator()()

Result Aleph::ClosestPairDivideAndConquer::operator() ( const DynList< Point > &  point_set ) const

inline

Compute the closest pair of points.

Parameters

point_set

Input set of points.

Returns

The closest pair and its squared distance.

Exceptions

domain_error

if point_set has fewer than 2 points.

Definition at line 1024 of file geom_algorithms.H.

References ah_domain_error_if, Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::HTList::Iterator::has_curr(), Aleph::quicksort_op(), and recurse().

recurse()

static Result Aleph::ClosestPairDivideAndConquer::recurse ( const Array< Point > &  px, const size_t  l, const size_t  r, Array< Point > &  py  )

inlinestaticprivate

Recursive divide-and-conquer step.

Splits the x-sorted array at mid, recurses on left/right halves, then checks a y-sorted "strip" around the split line to account for cross-boundary pairs.

Parameters

px	Points sorted by x.
l	Left index (inclusive).
r	Right index (exclusive).
py	Points in the range [l,r) sorted by y.

Returns

Closest pair in px[l..r).

Definition at line 955 of file geom_algorithms.H.

References brute_force(), Aleph::ClosestPairDivideAndConquer::Result::distance_squared, Aleph::divide_and_conquer_partition_dp(), Aleph::Point::get_x(), l, make_result(), r, recurse(), and Aleph::Array< T >::reserve().

Referenced by operator()(), and recurse().

---

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

• geom_algorithms.H