Offset (inflate/deflate) an arbitrary simple polygon. More...

#include <geom_algorithms.H>

Classes
struct	AugVertex
	Augmented vertex in the cleaned polygon. More...

struct	Intersection
	Intersection found between edge i and edge j of the raw polygon. More...

struct	Result
	The result of an offset operation, which may produce multiple polygons. More...

Public Types
enum class	JoinType { Miter , Bevel }
	Strategy for connecting offset edges at vertices. More...

Public Member Functions
Result	operator() (const Polygon &poly, const Geom_Number &distance, const JoinType join=JoinType::Miter, const Geom_Number &miter_limit=Geom_Number(2)) const
	Offset a simple polygon by the given distance.

Polygon	offset_polygon (const Polygon &poly, const Geom_Number &distance, JoinType join=JoinType::Miter, const Geom_Number &miter_limit=Geom_Number(2)) const
	Convenience: return the single largest-area result polygon.

Static Private Member Functions
static Geom_Number	abs_area (const Polygon &p)

static void	offset_edge (const Point &a, const Point &b, const Geom_Number &d, const bool inward, Point &oa, Point &ob)
	Compute two points on the offset line of edge (a→b) shifted by \|d\| along its outward or inward normal.

static Point	line_intersect (const Point &a1, const Point &a2, const Point &b1, const Point &b2)
	Line–line intersection of (a1,a2) and (b1,b2).

static Geom_Number	sq_dist (const Point &a, const Point &b)
	Compute the squared distance between two points.

static Array< Point >	compute_raw_offset (const Array< Point > &v, const Geom_Number &distance, const JoinType join, const Geom_Number &miter_limit)

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 Array< Intersection >	find_self_intersections (const Array< Point > &raw)
	O(n²) scan for all proper self-intersections.

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

static Array< AugVertex >	build_augmented (const Array< Point > &raw, const Array< Intersection > &isects)
	Build the augmented vertex list with crossing links.

static Polygon	build_poly (const Array< Point > &pts)
	Build a polygon from a point array.

static Array< Polygon >	extract_contours (Array< AugVertex > &aug)
	Walk the augmented polygon and extract valid CCW contours.

static Result	cleanup (const Array< Point > &raw)
	Full cleanup pipeline.

Detailed Description

Offset (inflate/deflate) an arbitrary simple polygon.

Unlike ConvexPolygonOffset, this class handles non-convex (simple) polygons. The raw miter-join offset polygon may self-intersect at reflex vertices; a self-intersection cleanup phase extracts the valid contours.

Algorithm

Raw offset: Shift each edge by |d| along its outward (d>0) or inward (d<0) normal, then join consecutive offset edges at their miter point (line–line intersection). An optional miter limit replaces excessively long miter joins with bevel (two-point) joins.
Self-intersection cleanup: O(n²) scan finds all proper self-intersections of the raw polygon, builds an augmented vertex list with crossing links, then traces valid CCW contours (positive signed area).

Complexity

Time: O(n²) — dominated by the all-pairs edge intersection scan.
Space: O(n + k) where k = number of self-intersections.

Definition at line 9071 of file geom_algorithms.H.

Member Enumeration Documentation

◆ JoinType

enum class Aleph::PolygonOffset::JoinType

strong

Strategy for connecting offset edges at vertices.

Enumerator
Miter	Extend edges until they intersect.
Bevel	Connect edge endpoints with a straight line.

Definition at line 9077 of file geom_algorithms.H.

Member Function Documentation

◆ abs_area()

static Geom_Number Aleph::PolygonOffset::abs_area ( const Polygon & p )

inlinestaticprivate

Definition at line 9169 of file geom_algorithms.H.

References Aleph::GeomPolygonUtils::signed_double_area().

Referenced by offset_polygon().

◆ build_augmented()

static Array< AugVertex > Aleph::PolygonOffset::build_augmented	(	const Array< Point > &	raw,
		const Array< Intersection > &	isects
	)

inlinestaticprivate

Build the augmented vertex list with crossing links.

Definition at line 9382 of file geom_algorithms.H.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), k, m, Aleph::PolygonOffset::AugVertex::pt, Aleph::Array< T >::reserve(), OhashCommon< HashTbl, Key >::size(), Aleph::Array< T >::size(), and sort_by_alpha().

Referenced by cleanup().

◆ build_poly()

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

inlinestaticprivate

Build a polygon from a point array.

Definition at line 9465 of file geom_algorithms.H.

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

Referenced by cleanup(), and extract_contours().

◆ cleanup()

static Result Aleph::PolygonOffset::cleanup ( const Array< Point > & raw )

inlinestaticprivate

Full cleanup pipeline.

Definition at line 9546 of file geom_algorithms.H.

References build_augmented(), build_poly(), Aleph::divide_and_conquer_partition_dp(), extract_contours(), find_self_intersections(), Aleph::PolygonOffset::Result::polygons, r, and Aleph::GeomPolygonUtils::signed_double_area().

Referenced by operator()().

◆ compute_raw_offset()

static Array< Point > Aleph::PolygonOffset::compute_raw_offset	(	const Array< Point > &	v,
		const Geom_Number &	distance,
		const JoinType	join,
		const Geom_Number &	miter_limit
	)

inlinestaticprivate

Definition at line 9203 of file geom_algorithms.H.

References Bevel, Aleph::divide_and_conquer_partition_dp(), Aleph::join(), line_intersect(), Miter, offset_edge(), Aleph::Array< T >::reserve(), Aleph::Array< T >::size(), and sq_dist().

Referenced by operator()().

◆ edge_param()

static Geom_Number Aleph::PolygonOffset::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 9317 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp().

Referenced by find_self_intersections().

◆ extract_contours()

static Array< Polygon > Aleph::PolygonOffset::extract_contours ( Array< AugVertex > & aug )

inlinestaticprivate

Walk the augmented polygon and extract valid CCW contours.

At each intersection vertex, jump to the partner first (switching to the other branch of the crossing) and then walk forward. This traces the inner contours correctly for self-intersecting offset polygons.

Definition at line 9482 of file geom_algorithms.H.

References Aleph::Array< T >::append(), build_poly(), Aleph::divide_and_conquer_partition_dp(), N, Aleph::GeomPolygonUtils::signed_double_area(), and Aleph::Array< T >::size().

Referenced by cleanup().

◆ find_self_intersections()

static Array< Intersection > Aleph::PolygonOffset::find_self_intersections ( const Array< Point > & raw )

inlinestaticprivate

O(n²) scan for all proper self-intersections.

Definition at line 9326 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), edge_param(), Aleph::Segment::intersection_with(), and Aleph::Segment::intersects_properly_with().

Referenced by cleanup().

◆ line_intersect()

static Point Aleph::PolygonOffset::line_intersect	(	const Point &	a1,
		const Point &	a2,
		const Point &	b1,
		const Point &	b2
	)

inlinestaticprivate

Line–line intersection of (a1,a2) and (b1,b2).

Definition at line 9186 of file geom_algorithms.H.

References Aleph::ConvexPolygonOffset::line_intersect().

Referenced by compute_raw_offset().

◆ offset_edge()

static void Aleph::PolygonOffset::offset_edge	(	const Point &	a,
		const Point &	b,
		const Geom_Number &	d,
		const bool	inward,
		Point &	oa,
		Point &	ob
	)

inlinestaticprivate

Compute two points on the offset line of edge (a→b) shifted by |d| along its outward or inward normal.

Delegates to mpfr arithmetic.

Definition at line 9178 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::ConvexPolygonOffset::offset_edge().

Referenced by compute_raw_offset().

◆ offset_polygon()

Polygon Aleph::PolygonOffset::offset_polygon	(	const Polygon &	poly,
		const Geom_Number &	distance,
		JoinType	join = `JoinType::Miter`,
		const Geom_Number &	miter_limit = `Geom_Number(2)`
	)		const

inline

Convenience: return the single largest-area result polygon.

Returns: The largest polygon, or an empty (0-vertex) polygon if the offset collapses entirely.

Definition at line 9147 of file geom_algorithms.H.

References abs_area(), Aleph::divide_and_conquer_partition_dp(), Aleph::join(), and r.

◆ operator()()

Result Aleph::PolygonOffset::operator()	(	const Polygon &	poly,
		const Geom_Number &	distance,
		const JoinType	join = `JoinType::Miter`,
		const Geom_Number &	miter_limit = `Geom_Number(2)`
	)		const

inline

Offset a simple polygon by the given distance.

Parameters

poly	A closed simple polygon.
distance	Positive = outward (expand), negative = inward (shrink).
join	Join strategy (Miter or Bevel).
miter_limit	When miter distance exceeds miter_limit * \|d\|, fall back to bevel join.

Returns: Zero or more result polygons.

Definition at line 9115 of file geom_algorithms.H.

References ah_domain_error_if, cleanup(), compute_raw_offset(), Aleph::divide_and_conquer_partition_dp(), Aleph::GeomPolygonUtils::ensure_ccw(), Aleph::GeomPolygonUtils::extract_vertices(), Aleph::Polygon::is_closed(), Aleph::join(), Aleph::PolygonOffset::Result::polygons, r, and Aleph::Polygon::size().

◆ sort_by_alpha()

static void Aleph::PolygonOffset::sort_by_alpha	(	Array< size_t > &	idx,
		const Array< Geom_Number > &	keys
	)

inlinestaticprivate

Insertion-sort indices by alpha key.

Definition at line 9363 of file geom_algorithms.H.

References keys, and Aleph::Array< T >::size().

Referenced by build_augmented().

◆ sq_dist()

static Geom_Number Aleph::PolygonOffset::sq_dist	(	const Point &	a,
		const Point &	b
	)

inlinestaticprivate

Compute the squared distance between two points.

Definition at line 9195 of file geom_algorithms.H.

References Aleph::Point::get_x(), and Aleph::Point::get_y().

Referenced by compute_raw_offset().

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

geom_algorithms.H

Classes

Public Types

Public Member Functions

Static Private Member Functions

Detailed Description

Algorithm

Complexity

Member Enumeration Documentation

◆ JoinType

Member Function Documentation

◆ abs_area()

◆ build_augmented()

◆ build_poly()

◆ cleanup()

◆ compute_raw_offset()

◆ edge_param()

◆ extract_contours()

◆ find_self_intersections()

◆ line_intersect()

◆ offset_edge()

◆ offset_polygon()

◆ operator()()

◆ sort_by_alpha()

◆ sq_dist()