Brute force convex hull algorithm. More...

#include <geom_algorithms.H>

Classes
struct	CmpSegment
	Comparator for segments to ensure strict weak ordering in sets. More...

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

Private Types
using	SegmentSet = DynSetTree< Segment, Treap_Rk, CmpSegment >

using	PointIt = DynList< Point >::Iterator

Static Private Member Functions
static bool	are_all_points_on_left (const DynList< Point > &l, const Segment &s)
	Checks if all points in a list lie to the left of a segment.

static SegmentSet	extreme_edges (const DynList< Point > &point_set)
	Finds the extreme edges of a point set (edges that form the convex hull).

Detailed Description

Brute force convex hull algorithm.

Computes the convex hull by testing all pairs of points to find extreme edges (edges where all other points are on one side).

Algorithm

For each pair of points (p, q): If all other points are to the left of segment (p, q), then (p, q) is an edge of the convex hull.

Complexity

Time: O(n³) - checks n² pairs, each against n points
Space: O(n) for the edge set

Use Cases

Educational purposes
Very small point sets (< 20 points)
Verification of other algorithms

See also: GiftWrappingConvexHull O(nh) algorithm; QuickHull O(n log n) average algorithm

Author: Alejandro J. Mujica

Definition at line 5045 of file geom_algorithms.H.

Member Typedef Documentation

◆ PointIt

using Aleph::BruteForceConvexHull::PointIt = DynList<Point>::Iterator

private

Definition at line 5073 of file geom_algorithms.H.

◆ SegmentSet

using Aleph::BruteForceConvexHull::SegmentSet = DynSetTree<Segment, Treap_Rk, CmpSegment>

private

Definition at line 5072 of file geom_algorithms.H.

Member Function Documentation

◆ are_all_points_on_left()

static bool Aleph::BruteForceConvexHull::are_all_points_on_left	(	const DynList< Point > &	l,
		const Segment &	s
	)

inlinestaticprivate

Checks if all points in a list lie to the left of a segment.

Definition at line 5078 of file geom_algorithms.H.

References Aleph::HTList::Iterator::has_curr(), and l.

Referenced by extreme_edges().

◆ extreme_edges()

static SegmentSet Aleph::BruteForceConvexHull::extreme_edges ( const DynList< Point > & point_set )

inlinestaticprivate

Finds the extreme edges of a point set (edges that form the convex hull).

Parameters

point_set The input set of points.

Returns: A set of extreme segments (edges of the convex hull).

Definition at line 5093 of file geom_algorithms.H.

References are_all_points_on_left(), Aleph::blossom_maximum_cardinality_matching(), and Aleph::HTList::Iterator::has_curr().

Referenced by operator()().

◆ operator()()

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

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), extreme_edges(), Aleph::Segment::get_src_point(), and Aleph::Segment::get_tgt_point().

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

geom_algorithms.H

Classes

Public Member Functions

Private Types

Static Private Member Functions