Gift wrapping (Jarvis march) 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 const Point *	get_lowest_point (const DynList< Point > &point_set)
	Finds the point with the minimum y-coordinate (and minimum x on ties).

Detailed Description

Gift wrapping (Jarvis march) convex hull algorithm.

Computes the convex hull by starting from the lowest point and "wrapping" around the point set, always selecting the point that makes the smallest counter-clockwise angle.

Algorithm

Start with the lowest point (guaranteed to be on hull)
Find the point that makes the smallest angle with the last edge
Add it to the hull
Repeat until returning to the starting point

Complexity

Time: O(nh) where n = total points, h = hull points
Space: O(1) additional

Use Cases

When the convex hull has few points (h << n)
When output-sensitive algorithm is preferred

See also: QuickHull For general-purpose convex hull

Author: Alejandro J. Mujica

Definition at line 5221 of file geom_algorithms.H.

Member Function Documentation

◆ get_lowest_point()

static const Point * Aleph::GiftWrappingConvexHull::get_lowest_point ( const DynList< Point > & point_set )

inlinestaticprivate

Finds the point with the minimum y-coordinate (and minimum x on ties).

Definition at line 5226 of file geom_algorithms.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), Aleph::DynList< T >::Iterator::get_curr(), Aleph::Point::get_x(), Aleph::Point::get_y(), Aleph::HTList::Iterator::has_curr(), Aleph::HTList::Iterator::next(), and Aleph::HTList::Iterator::next_ne().

Referenced by operator()().

◆ operator()()

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

inline

Compute the convex hull of a point set.

Uses exact cross-product predicates instead of floating-point angles. At each step, the next hull vertex is the point such that all other points lie to the left of the directed edge from current to the next.

Parameters

point_set The input points.

Returns: A closed polygon representing the convex hull.

Definition at line 5254 of file geom_algorithms.H.

References Aleph::and, Aleph::COLLINEAR, Aleph::CW, Aleph::Point::distance_squared_to(), Aleph::divide_and_conquer_partition_dp(), get_lowest_point(), Aleph::HTList::Iterator::has_curr(), Aleph::next(), and Aleph::orientation().

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

geom_algorithms.H

Public Member Functions