Aleph::QuickHull Class Reference

QuickHull convex hull algorithm. More...

#include <geom_algorithms.H>

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

Static Private Member Functions
static Point	get_farthest_point (const DynList< Point > &point_set, const Segment &s)
	Return the point in point_set farthest from segment s.
static std::pair< DynList< Point >, DynList< Point > >	get_right_points (DynList< Point > &point_set, const Point &a, const Point &b, const Point &c)
	Partition points to the right of edges (a,c) and (c,b).
static DynList< Point >	quick_hull (DynList< Point > &point_set, const Point &a, const Point &b)
	Recursive QuickHull step for a directed edge (a,b).
static std::pair< Point, Point >	search_extremes (const DynList< Point > &point_set)
	Find leftmost and rightmost points by x coordinate.
static std::pair< DynList< Point >, DynList< Point > >	partition (const DynList< Point > &point_set, const Point &a, const Point &b)
	Split points by the line through directed segment (a,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 5331 of file geom_algorithms.H.

Member Function Documentation

get_farthest_point()

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

inlinestaticprivate

Return the point in point_set farthest from segment s.

This is the standard QuickHull selection step: pick the point with maximum perpendicular distance to the current hull edge. In this implementation we compare the absolute value of the parallelogram area |area_of_parallelogram(a,b,p)| which is proportional to that distance (the segment length |ab| is constant for all candidates), avoiding square-roots.

Parameters

point_set	Candidate points.
s	Base segment (a,b) used as reference.

Returns

A point from point_set maximizing |area_of_parallelogram|.

Note

If point_set is empty, the returned point is default-constructed.

Definition at line 5349 of file geom_algorithms.H.

References Aleph::area_of_parallelogram(), Aleph::divide_and_conquer_partition_dp(), Aleph::Segment::get_src_point(), Aleph::Segment::get_tgt_point(), and Aleph::HTList::Iterator::has_curr().

Referenced by quick_hull().

get_right_points()

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

inlinestaticprivate

Partition points to the right of edges (a,c) and (c,b).

Given a triangle (a,c,b) where c is the farthest point from segment (a,b), QuickHull must recursively process the points on the outside (i.e. the same side as the hull) of the sub-edges (a,c) and (c,b).

This function consumes point_set and splits its points into two sets:

• ret.first: points strictly on the right side of the directed edge (a,c), excluding endpoints a and c.
• ret.second: points strictly on the right side of the directed edge (c,b), excluding endpoints c and b.

“Right side” is detected with the signed area predicate: area_of_parallelogram(u,v,p) < 0.

Parameters

[in,out]	point_set	Input candidate points. This list is emptied by repeated remove_first().
	a	First endpoint of the current hull edge.
	b	Second endpoint of the current hull edge.
	c	Farthest point from edge (a,b) defining the split.

Returns

A pair of lists (S_ac, S_cb) as described above.

Definition at line 5402 of file geom_algorithms.H.

References Aleph::and, Aleph::area_of_parallelogram(), and Aleph::divide_and_conquer_partition_dp().

Referenced by quick_hull().

operator()()

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

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 5514 of file geom_algorithms.H.

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

partition()

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

inlinestaticprivate

Split points by the line through directed segment (a,b).

Parameters

point_set	Input points.
a	Segment source.
b	Segment target.

Returns

A pair (right, left_or_collinear) where:

• right: points with area_of_parallelogram(a,b,p) < 0.
• left_or_collinear: all remaining points.

Definition at line 5494 of file geom_algorithms.H.

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

Referenced by operator()().

quick_hull()

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

inlinestaticprivate

Recursive QuickHull step for a directed edge (a,b).

Assumes point_set contains points on the outside of the directed edge (a,b) (in this implementation: points to the right of (a,b)).

Parameters

[in,out]	point_set	Candidate points; may be consumed by recursion.
	a	Edge source.
	b	Edge target.

Returns

Ordered list of intermediate hull vertices between a and b (does not include a nor b). If point_set is empty, it returns an empty list.

Definition at line 5437 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), get_farthest_point(), get_right_points(), and quick_hull().

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

search_extremes()

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

inlinestaticprivate

Find leftmost and rightmost points by x coordinate.

Parameters

point_set

Non-empty input set.

Returns

(leftmost, rightmost) where ties are broken by first occurrence during traversal.

Definition at line 5462 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::DynList< T >::Iterator::get_curr(), Aleph::Point::get_x(), Aleph::HTList::Iterator::has_curr(), 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