Brute force convex hull algorithm. More...

#include <geom_algorithms.H>

Classes
struct	CmpSegment

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

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

using	PointIt = DynList< Point >::Iterator

Private Member Functions
bool	are_all_points_on_left (DynList< Point > &l, const Segment &s)

SegmentSet	extreme_edges (DynList< Point > &point_set)

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

Member Typedef Documentation

◆ PointIt

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

private

Definition at line 370 of file geom_algorithms.H.

◆ SegmentSet

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

private

Definition at line 369 of file geom_algorithms.H.

Member Function Documentation

◆ are_all_points_on_left()

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

inlineprivate

Definition at line 372 of file geom_algorithms.H.

References l.

Referenced by extreme_edges().

◆ extreme_edges()

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

inlineprivate

Definition at line 385 of file geom_algorithms.H.

References are_all_points_on_left(), Aleph::DynList< T >::insert(), and Aleph::maps().

Referenced by operator()().

◆ operator()()

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

References extreme_edges(), LocateFunctions< Container, Type >::find_ptr(), Segment::get_src_point(), Segment::get_tgt_point(), Aleph::maps(), and Aleph::DynList< T >::remove().

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

geom_algorithms.H

Classes

Public Member Functions

Private Types

Private Member Functions