Exact bounded intersection of half-planes. More...

#include <geom_algorithms.H>

Classes
struct	HalfPlane

Public Member Functions
Polygon	operator() (const Array< HalfPlane > &halfplanes) const
	Intersect half-planes and return bounded feasible polygon.

Polygon	operator() (const std::initializer_list< HalfPlane > il) const
	Overload for initializer-list convenience.

Static Public Member Functions
static Array< HalfPlane >	from_convex_polygon (const Polygon &poly)
	Build half-planes from the edges of a closed convex polygon.

Static Private Member Functions
static Geom_Number	signed_double_area (const Array< Point > &verts)

static bool	upper_half (const HalfPlane &h)

static Geom_Number	cross_dir (const HalfPlane &a, const HalfPlane &b)

static Geom_Number	dot_dir (const HalfPlane &a, const HalfPlane &b)

static bool	same_direction (const HalfPlane &a, const HalfPlane &b)

static bool	parallel (const HalfPlane &a, const HalfPlane &b)

static Point	line_intersection (const HalfPlane &a, const HalfPlane &b)

static void	push_clean (Array< Point > &out, const Point &p)

static Array< Point >	normalize_vertices (const Array< Point > &pts)

static Polygon	build_polygon (const Array< Point > &pts)

Detailed Description

Exact bounded intersection of half-planes.

Each half-plane is represented by a directed line (p -> q); the feasible side is the left side of that line (including boundary).

This class computes the bounded polygon defined by the intersection of a set of half-planes using the classic angle-sorted deque algorithm.

Complexity

Time: O(n log n) for n half-planes.
Space: O(n).

Definition at line 1772 of file geom_algorithms.H.

Member Function Documentation

◆ build_polygon()

static Polygon Aleph::HalfPlaneIntersection::build_polygon ( const Array< Point > & pts )

inlinestaticprivate

Definition at line 1892 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), and normalize_vertices().

Referenced by operator()().

◆ cross_dir()

static Geom_Number Aleph::HalfPlaneIntersection::cross_dir	(	const HalfPlane &	a,
		const HalfPlane &	b
	)

inlinestaticprivate

Definition at line 1811 of file geom_algorithms.H.

References Aleph::HalfPlaneIntersection::HalfPlane::dx(), and Aleph::HalfPlaneIntersection::HalfPlane::dy().

Referenced by operator()(), parallel(), and same_direction().

◆ dot_dir()

static Geom_Number Aleph::HalfPlaneIntersection::dot_dir	(	const HalfPlane &	a,
		const HalfPlane &	b
	)

inlinestaticprivate

Definition at line 1817 of file geom_algorithms.H.

References Aleph::HalfPlaneIntersection::HalfPlane::dx(), and Aleph::HalfPlaneIntersection::HalfPlane::dy().

Referenced by same_direction().

◆ from_convex_polygon()

static Array< HalfPlane > Aleph::HalfPlaneIntersection::from_convex_polygon ( const Polygon & poly )

inlinestatic

Build half-planes from the edges of a closed convex polygon.

Edge direction is normalized, so the interior of the polygon is always on the left side of each half-plane, for both CCW and CW input order.

Parameters

poly	Closed convex polygon.

Returns: Array of edge half-planes.

Definition at line 1916 of file geom_algorithms.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Dlink::Iterator::has_curr(), Aleph::Polygon::is_closed(), Aleph::Array< T >::reserve(), signed_double_area(), and Aleph::Polygon::size().

Referenced by Aleph::VoronoiDiagramFromDelaunay::clipped_cells(), TEST(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ line_intersection()

static Point Aleph::HalfPlaneIntersection::line_intersection	(	const HalfPlane &	a,
		const HalfPlane &	b
	)

inlinestaticprivate

Definition at line 1834 of file geom_algorithms.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::HalfPlaneIntersection::HalfPlane::dx(), Aleph::HalfPlaneIntersection::HalfPlane::dy(), Aleph::Point::get_x(), Aleph::Point::get_y(), and Aleph::HalfPlaneIntersection::HalfPlane::p.

Referenced by operator()().

◆ normalize_vertices()

static Array< Point > Aleph::HalfPlaneIntersection::normalize_vertices ( const Array< Point > & pts )

inlinestaticprivate

Definition at line 1879 of file geom_algorithms.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), push_clean(), and Aleph::Array< T >::reserve().

Referenced by build_polygon().

◆ operator()() [1/2]

Polygon Aleph::HalfPlaneIntersection::operator() ( const Array< HalfPlane > & halfplanes ) const

inline

Intersect half-planes and return bounded feasible polygon.

Parameters

halfplanes Input half-planes.

Returns: Bounded intersection polygon; empty polygon if infeasible or unbounded.

Definition at line 1947 of file geom_algorithms.H.

References Aleph::and, Aleph::DynDlist< T >::append(), build_polygon(), cross_dir(), Aleph::divide_and_conquer_partition_dp(), line_intersection(), Aleph::HalfPlaneIntersection::HalfPlane::offset(), parallel(), Aleph::quicksort_op(), Aleph::Array< T >::reserve(), same_direction(), Aleph::unique(), and upper_half().

◆ operator()() [2/2]

Polygon Aleph::HalfPlaneIntersection::operator() ( const std::initializer_list< HalfPlane > il ) const

inline

Overload for initializer-list convenience.

Parameters

il	Input half-planes.

Returns: Bounded intersection polygon.

Definition at line 2070 of file geom_algorithms.H.

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

◆ parallel()

static bool Aleph::HalfPlaneIntersection::parallel	(	const HalfPlane &	a,
		const HalfPlane &	b
	)

inlinestaticprivate

Definition at line 1829 of file geom_algorithms.H.

References cross_dir().

Referenced by operator()().

◆ push_clean()

static void Aleph::HalfPlaneIntersection::push_clean	(	Array< Point > &	out,
		const Point &	p
	)

inlinestaticprivate

Definition at line 1852 of file geom_algorithms.H.

References Aleph::COLLINEAR, Aleph::divide_and_conquer_partition_dp(), Aleph::on_segment(), and Aleph::orientation().

Referenced by normalize_vertices().

◆ same_direction()

static bool Aleph::HalfPlaneIntersection::same_direction	(	const HalfPlane &	a,
		const HalfPlane &	b
	)

inlinestaticprivate

Definition at line 1823 of file geom_algorithms.H.

References Aleph::and, cross_dir(), and dot_dir().

Referenced by operator()().

◆ signed_double_area()

static Geom_Number Aleph::HalfPlaneIntersection::signed_double_area ( const Array< Point > & verts )

inlinestaticprivate

Definition at line 1801 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::GeomPolygonUtils::signed_double_area().

Referenced by from_convex_polygon().

◆ upper_half()

static bool Aleph::HalfPlaneIntersection::upper_half ( const HalfPlane & h )

inlinestaticprivate

Definition at line 1806 of file geom_algorithms.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), and h.

Referenced by operator()().

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

geom_algorithms.H

Classes

Public Member Functions

Static Public Member Functions

Static Private Member Functions

Detailed Description

Complexity

Member Function Documentation

◆ build_polygon()

◆ cross_dir()

◆ dot_dir()

◆ from_convex_polygon()

◆ line_intersection()

◆ normalize_vertices()

◆ operator()() [1/2]

◆ operator()() [2/2]

◆ parallel()

◆ push_clean()

◆ same_direction()

◆ signed_double_area()

◆ upper_half()