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)
	Computes the intersection of two polygons.

static Array< Polygon >	compute_union (const Polygon &a, const Polygon &b)
	Computes the union of two polygons.

static Array< Polygon >	compute_difference (const Polygon &a, const Polygon &b)
	Computes the difference (A \ B) of two polygons.

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:11299

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:221

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

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

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

Aleph::blossom_maximum_cardinality_matching
size_t blossom_maximum_cardinality_matching(const GT &g, DynDlist< typename GT::Arc * > &matching, SA sa=SA())
Alias of compute_maximum_cardinality_general_matching().
Definition Blossom.H:466

Definition at line 11298 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 11304 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 11396 of file geom_algorithms.H.

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

Referenced by greiner_hormann().

◆ compute_difference()

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

inlinestaticprivate

Computes the difference (A \ B) of two polygons.

Uses the Greiner-Hormann algorithm by reversing the orientation of B.

Parameters

a	The first polygon (minuend).
b	The second polygon (subtrahend).

Returns: An array of polygons representing the difference.

Definition at line 11777 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), 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

Computes the intersection of two polygons.

Uses the Greiner-Hormann algorithm.

Parameters

a	The first polygon.
b	The second polygon.

Returns: An array of polygons representing the intersection.

Definition at line 11699 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), 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

Computes the union of two polygons.

Uses the Greiner-Hormann algorithm. If polygons are disjoint, both are returned.

Parameters

a	The first polygon.
b	The second polygon.

Returns: An array of polygons representing the union.

Definition at line 11737 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), 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 11352 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 11407 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching().

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 11379 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 11373 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 11473 of file geom_algorithms.H.

References Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), build_poly(), 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(), sort_indices_by_alpha(), and steps.