Aleph::AndrewMonotonicChainConvexHull Class Reference

Andrew's monotonic chain convex hull algorithm. More...

#include <geom_algorithms.H>

Classes
struct	LexicographicCmp
	Lexicographical comparison for points (x primary, y secondary). 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

Andrew's monotonic chain convex hull algorithm.

Computes the convex hull by sorting points lexicographically and building the lower and upper chains 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 4741 of file geom_algorithms.H.

Member Function Documentation

operator()()

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

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

sorted_unique_points()

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

inlinestaticprivate

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

Definition at line 4763 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::AndrewMonotonicChainConvexHull::turn ( const Point &  a, const Point &  b, const Point &  c  )

inlinestaticprivate

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

Definition at line 4787 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