Aleph::QuickHull Class Reference

QuickHull convex hull algorithm. More...

#include <geom_algorithms.H>

Public Member Functions
Polygon	operator() (DynList< Point > &point_set)
	Compute the convex hull of a point set.

Private Member Functions
Point	get_fartest_point (DynList< Point > &point_set, const Segment &s)
std::pair< DynList< Point >, DynList< Point > >	get_right_points (DynList< Point > &point_set, const Point &a, const Point &b, const Point &c)
DynList< Point >	quick_hull (DynList< Point > &point_set, const Point &a, const Point &b)
std::pair< Point, Point >	search_extremes (DynList< Point > &point_set)
std::pair< DynList< Point >, DynList< Point > >	partition (DynList< Point > &point_set, const Point &a, const Point &b)

Detailed Description

QuickHull convex hull algorithm.

Computes the convex hull using a divide-and-conquer approach similar to QuickSort. Recursively finds the farthest point from a line and partitions the remaining points.

Algorithm

1. Find leftmost and rightmost points (guaranteed on hull)
2. Partition points into those above and below the line
3. For each partition, find the farthest point from the line
4. Recursively process the sub-partitions

Complexity

• Time: O(n log n) average, O(n²) worst case
• Space: O(n) for recursive calls

Use Cases

• General-purpose convex hull computation
• Large point sets
• When average-case performance matters more than worst-case

Author

Alejandro J. Mujica

Definition at line 586 of file geom_algorithms.H.

Member Function Documentation

get_fartest_point()

Point Aleph::QuickHull::get_fartest_point ( DynList< Point > &  point_set, const Segment &  s  )

inlineprivate

Definition at line 588 of file geom_algorithms.H.

References Segment::get_perpendicular(), Aleph::HTList::Iterator::has_curr(), Aleph::maps(), and Aleph::HTList::size().

Referenced by quick_hull().

get_right_points()

std::pair< DynList< Point >, DynList< Point > > Aleph::QuickHull::get_right_points ( DynList< Point > &  point_set, const Point &  a, const Point &  b, const Point &  c  )

inlineprivate

Definition at line 612 of file geom_algorithms.H.

References Aleph::DynList< T >::append(), Aleph::HTList::is_empty(), Aleph::maps(), and Aleph::DynList< T >::remove_first().

Referenced by quick_hull().

operator()()

Polygon Aleph::QuickHull::operator() ( DynList< Point > &  point_set )

inline

Compute the convex hull of a point set.

Parameters

point_set

The input points.

Returns

A closed polygon representing the convex hull.

Definition at line 699 of file geom_algorithms.H.

References Aleph::DynList< T >::append(), Aleph::HTList::concat(), Aleph::HTList::Iterator::has_curr(), Aleph::maps(), partition(), quick_hull(), and search_extremes().

partition()

std::pair< DynList< Point >, DynList< Point > > Aleph::QuickHull::partition ( DynList< Point > &  point_set, const Point &  a, const Point &  b  )

inlineprivate

Definition at line 674 of file geom_algorithms.H.

References Aleph::DynList< T >::append(), Aleph::HTList::Iterator::has_curr(), and Aleph::maps().

Referenced by operator()().

quick_hull()

DynList< Point > Aleph::QuickHull::quick_hull ( DynList< Point > &  point_set, const Point &  a, const Point &  b  )

inlineprivate

Definition at line 634 of file geom_algorithms.H.

References Aleph::DynList< T >::append(), Aleph::HTList::concat(), get_fartest_point(), get_right_points(), Aleph::HTList::is_empty(), Aleph::maps(), and quick_hull().

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

search_extremes()

std::pair< Point, Point > Aleph::QuickHull::search_extremes ( DynList< Point > &  point_set )

inlineprivate

Definition at line 652 of file geom_algorithms.H.

References Aleph::DynList< T >::Iterator::get_curr(), Aleph::HTList::Iterator::has_curr(), Aleph::maps(), Aleph::HTList::Iterator::next(), and Aleph::HTList::Iterator::next_ne().

Referenced by operator()().

---

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

• geom_algorithms.H