Boolean operations on simple polygons (union, intersection, difference) using the Greiner-Hormann algorithm. More...

#include <geom_algorithms.H>

Classes
struct	GHNode

struct	IsectPair
	Intersection pair found between edge i of A and edge j of B. More...

Public Types
enum class	Op { INTERSECTION , UNION , DIFFERENCE }
	Type of Boolean operation to perform. More...

Public Member Functions
Array< Polygon >	operator() (const Polygon &a, const Polygon &b, Op op) const
	Compute a boolean operation on two simple polygons.

Array< Polygon >	intersection (const Polygon &a, const Polygon &b) const
	Convenience: intersection.

Array< Polygon >	polygon_union (const Polygon &a, const Polygon &b) const
	Convenience: union.

Array< Polygon >	difference (const Polygon &a, const Polygon &b) const
	Convenience: difference (a minus b).

Static Private Member Functions
static Array< Point >	extract (const Polygon &p)
	Extract vertices from a polygon into an Array.

static void	ensure_ccw (Array< Point > &v)
	Ensure vertices are in CCW order.

static void	reverse_array (Array< Point > &v)
	Reverse a vertex array in place.

static Polygon	build_poly (const Array< Point > &pts)
	Build a polygon from a vertex array (bypasses colinearity merge).

static Geom_Number	edge_param (const Point &P, const Point &Q, const Point &I)
	Compute parameter t of point I along directed edge P→Q.

static bool	point_inside_ccw (const Array< Point > &poly, const Point &p)
	Point-in-polygon test on a CCW vertex array (winding number).

static void	sort_indices_by_alpha (Array< size_t > &idx, const Array< Geom_Number > &keys)
	Insertion-sort indices by a key array.

static Array< Polygon >	greiner_hormann (const Array< Point > &va, const Array< Point > &vb, bool start_entering)
	Run Greiner-Hormann and return result polygons.

static Array< Polygon >	compute_intersection (const Polygon &a, const Polygon &b)

static Array< Polygon >	compute_union (const Polygon &a, const Polygon &b)

static Array< Polygon >	compute_difference (const Polygon &a, const Polygon &b)

Detailed Description

Boolean operations on simple polygons (union, intersection, difference) using the Greiner-Hormann algorithm.

Implements general boolean operations on arbitrary simple polygons, including concave ones, via the Greiner-Hormann clipping algorithm:

Find all proper intersection points between polygon edges.
Build augmented vertex lists with intersection nodes inserted.
Mark each intersection as entering or exiting the other polygon.
Traverse the augmented lists to extract result boundaries.

Intersection: A ∩ B — regions inside both polygons.
Union: A ∪ B — outer boundary of both polygons.
Difference: A \ B = A ∩ complement(B) — regions in A outside B.

Limitations

Both polygons must be simple (no self-intersections) and closed.
Degenerate cases (shared edges, vertex-on-edge tangencies) may produce approximate results; the algorithm handles proper (transversal) intersections exactly.
Results with holes (e.g. B entirely inside A for difference) are not representable as a single simple polygon; in such cases the outer boundary alone is returned.

Complexity

O(n·m + k log k) where n, m are vertex counts and k is the number of intersection points.

Example: Polygon A;

A.add_vertex(Point(0,0)); A.add_vertex(Point(2,0)); A.add_vertex(Point(2,2)); A.add_vertex(Point(0,2));

A.close();

Polygon B;

B.add_vertex(Point(1,1)); B.add_vertex(Point(3,1)); B.add_vertex(Point(3,3)); B.add_vertex(Point(1,3));

B.close();

BooleanPolygonOperations bop;

auto res = bop(A, B, BooleanPolygonOperations::Op::INTERSECTION);

Aleph::BooleanPolygonOperations
Boolean operations on simple polygons (union, intersection, difference) using the Greiner-Hormann alg...
Definition geom_algorithms.H:11336

Aleph::BooleanPolygonOperations::Op::INTERSECTION
@ INTERSECTION
Find regions common to both polygons.

Aleph::Point
Represents a point with rectangular coordinates in a 2D plane.
Definition point.H:229

Aleph::Polygon
A general (irregular) 2D polygon defined by a sequence of vertices.
Definition polygon.H:246

Aleph::Polygon::add_vertex
void add_vertex(const Point &point)
Add a vertex to the polygon.
Definition polygon.H:677

Aleph::Polygon::close
void close()
Close the polygon.
Definition polygon.H:840

Aleph::divide_and_conquer_partition_dp
Divide_Conquer_DP_Result< Cost > divide_and_conquer_partition_dp(const size_t groups, const size_t n, Transition_Cost_Fn transition_cost, const Cost inf=dp_optimization_detail::default_inf< Cost >())
Optimize partition DP using divide-and-conquer optimization.
Definition DP_Optimizations.H:133

Definition at line 11335 of file geom_algorithms.H.

Member Enumeration Documentation

◆ Op

enum class Aleph::BooleanPolygonOperations::Op

strong

Type of Boolean operation to perform.

Enumerator
INTERSECTION	Find regions common to both polygons.
UNION	Find regions covered by either polygon.
DIFFERENCE	Find regions in the first polygon not covered by the second.

Definition at line 11341 of file geom_algorithms.H.

Member Function Documentation

◆ build_poly()

static Polygon Aleph::BooleanPolygonOperations::build_poly ( const Array< Point > & pts )

inlinestaticprivate

Build a polygon from a vertex array (bypasses colinearity merge).

Definition at line 11434 of file geom_algorithms.H.

References Aleph::Polygon::add_vertex(), Aleph::Polygon::close(), and Aleph::divide_and_conquer_partition_dp().

Referenced by greiner_hormann().

◆ compute_difference()

static Array< Polygon > Aleph::BooleanPolygonOperations::compute_difference	(	const Polygon &	a,
		const Polygon &	b
	)

inlinestaticprivate

Definition at line 11796 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), ensure_ccw(), extract(), greiner_hormann(), point_inside_ccw(), and reverse_array().

Referenced by operator()().

◆ compute_intersection()

static Array< Polygon > Aleph::BooleanPolygonOperations::compute_intersection	(	const Polygon &	a,
		const Polygon &	b
	)

inlinestaticprivate

Definition at line 11734 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), ensure_ccw(), extract(), greiner_hormann(), and point_inside_ccw().

Referenced by operator()().

◆ compute_union()

static Array< Polygon > Aleph::BooleanPolygonOperations::compute_union	(	const Polygon &	a,
		const Polygon &	b
	)

inlinestaticprivate

Definition at line 11764 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), ensure_ccw(), extract(), greiner_hormann(), and point_inside_ccw().

Referenced by operator()().

◆ difference()

Array< Polygon > Aleph::BooleanPolygonOperations::difference	(	const Polygon &	a,
		const Polygon &	b
	)		const

inline

Convenience: difference (a minus b).

Definition at line 11390 of file geom_algorithms.H.

References DIFFERENCE.

Referenced by TEST_F(), TEST_F(), and TEST_F().

◆ edge_param()

static Geom_Number Aleph::BooleanPolygonOperations::edge_param	(	const Point &	P,
		const Point &	Q,
		const Point &	I
	)

inlinestaticprivate

Compute parameter t of point I along directed edge P→Q.

Definition at line 11446 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp().

Referenced by greiner_hormann().

◆ ensure_ccw()

static void Aleph::BooleanPolygonOperations::ensure_ccw ( Array< Point > & v )

inlinestaticprivate

Ensure vertices are in CCW order.

Definition at line 11417 of file geom_algorithms.H.

References Aleph::GeomPolygonUtils::ensure_ccw().

Referenced by compute_difference(), compute_intersection(), and compute_union().

◆ extract()

static Array< Point > Aleph::BooleanPolygonOperations::extract ( const Polygon & p )

inlinestaticprivate

Extract vertices from a polygon into an Array.

Definition at line 11411 of file geom_algorithms.H.

References Aleph::GeomPolygonUtils::extract_vertices().

Referenced by compute_difference(), compute_intersection(), and compute_union().

◆ greiner_hormann()

static Array< Polygon > Aleph::BooleanPolygonOperations::greiner_hormann	(	const Array< Point > &	va,
		const Array< Point > &	vb,
		bool	start_entering
	)

inlinestaticprivate

Run Greiner-Hormann and return result polygons.

Parameters

va	CCW vertices of A.
vb	CCW vertices of B.
start_entering	true → start at entering intersections (intersection op); false → start at exiting (union op).

Definition at line 11517 of file geom_algorithms.H.

References Aleph::Array< T >::append(), build_poly(), Aleph::divide_and_conquer_partition_dp(), edge_param(), Aleph::Segment::intersection_with(), Aleph::Segment::intersects_properly_with(), k, point_inside_ccw(), Aleph::BooleanPolygonOperations::GHNode::pt, Aleph::Array< T >::reserve(), Aleph::Array< T >::size(), and sort_indices_by_alpha().