Gift wrapping (Jarvis march) 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_lowest_point (DynList< Point > &point_set)

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

Member Function Documentation

◆ get_lowest_point()

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

inlineprivate

Definition at line 483 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()().

◆ operator()()

Polygon Aleph::GiftWrappingConvexHull::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 508 of file geom_algorithms.H.

References Segment::counterclockwise_angle_with(), get_lowest_point(), Aleph::HTList::Iterator::has_curr(), and Aleph::maps().

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

geom_algorithms.H

Public Member Functions