Graham scan convex hull algorithm. More...

#include <geom_algorithms.H>

Classes
struct	LexicographicCmp
	Lexicographical comparison for points. More...

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

Static Private Member Functions
static Array< Point >	sorted_unique_points (const DynList< Point > &point_set)
	Extracts points from a list, sorts them and removes duplicates.

static Geom_Number	turn (const Point &a, const Point &b, const Point &c)
	Computes the turn orientation of triple (a, b, c).

Detailed Description

Graham scan convex hull algorithm.

Computes the convex hull by choosing the lowest point as pivot, sorting the remaining points by polar angle around the pivot, and scanning with a stack-like process.

Policy

Duplicate points are removed before processing.
Collinear points on hull edges are excluded, keeping only extreme endpoints of each edge.
Degenerate cases are preserved:
- 0 unique points -> empty polygon
- 1 unique point -> 1-vertex (open) polygon
- 2 unique points -> 2-vertex closed degenerate hull

Complexity

Time: O(n log n) due to sorting
Space: O(n)

Definition at line 4876 of file geom_algorithms.H.

Member Function Documentation

◆ operator()()

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

inline

Compute the convex hull of a point set.

Parameters

point_set The input points.

Returns: A polygon representing the convex hull.

Definition at line 4934 of file geom_algorithms.H.

References Aleph::Array< T >::append(), Aleph::area_of_parallelogram(), Aleph::divide_and_conquer_partition_dp(), Aleph::quicksort_op(), Aleph::Array< T >::reserve(), Aleph::Array< T >::size(), sorted_unique_points(), and turn().

◆ sorted_unique_points()

static Array< Point > Aleph::GrahamScanConvexHull::sorted_unique_points ( const DynList< Point > & point_set )

inlinestaticprivate

Extracts points from a list, sorts them and removes duplicates.

Definition at line 4898 of file geom_algorithms.H.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::get_last(), Aleph::HTList::Iterator::has_curr(), Aleph::quicksort_op(), Aleph::Array< T >::reserve(), Aleph::Array< T >::size(), and Aleph::unique().

Referenced by operator()().

◆ turn()

static Geom_Number Aleph::GrahamScanConvexHull::turn	(	const Point &	a,
		const Point &	b,
		const Point &	c
	)

inlinestaticprivate

Computes the turn orientation of triple (a, b, c).

Definition at line 4922 of file geom_algorithms.H.

References Aleph::area_of_parallelogram().

Referenced by operator()().

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

geom_algorithms.H

Classes

Public Member Functions