Inward (erosion) and outward (dilation) offset of convex polygons. More...

#include <geom_algorithms.H>

Static Public Member Functions
static Polygon	inward (const Polygon &convex_poly, const Geom_Number &distance)
	Inward offset (erosion) of a convex polygon.

static Polygon	outward (const Polygon &convex_poly, const Geom_Number &distance)
	Outward offset (dilation) of a convex polygon.

Static Private Member Functions
static Array< Point >	extract_verts (const Polygon &poly)

static Geom_Number	signed_double_area (const Array< Point > &v)

static bool	is_convex (const Array< Point > &v)

static void	ensure_ccw (Array< Point > &v)

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) moved by distance 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).

Friends
class	PolygonOffset

Detailed Description

Inward (erosion) and outward (dilation) offset of convex polygons.

The inward offset shrinks the polygon by moving each edge inward by a perpendicular distance d, then intersecting the resulting half-planes. The outward offset expands it by moving edges outward and computing consecutive offset-line intersections.

Complexity

Inward: O(n log n) via HalfPlaneIntersection
Outward: O(n)

Definition at line 8834 of file geom_algorithms.H.

Member Function Documentation

◆ ensure_ccw()

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

inlinestaticprivate

Definition at line 8855 of file geom_algorithms.H.

References Aleph::GeomPolygonUtils::ensure_ccw().

Referenced by inward(), and outward().

◆ extract_verts()

static Array< Point > Aleph::ConvexPolygonOffset::extract_verts ( const Polygon & poly )

inlinestaticprivate

Definition at line 8838 of file geom_algorithms.H.

References Aleph::GeomPolygonUtils::extract_vertices().

Referenced by inward(), and outward().

◆ inward()

static Polygon Aleph::ConvexPolygonOffset::inward	(	const Polygon &	convex_poly,
		const Geom_Number &	distance
	)

inlinestatic

Inward offset (erosion) of a convex polygon.

Parameters

convex_poly	A closed convex polygon.
distance	Perpendicular distance to move each edge inward.

Returns: The offset polygon, or an empty polygon if distance is too large.

Definition at line 8931 of file geom_algorithms.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), ensure_ccw(), extract_verts(), is_convex(), offset_edge(), Aleph::Array< T >::reserve(), and Aleph::Array< T >::size().

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

◆ is_convex()

static bool Aleph::ConvexPolygonOffset::is_convex ( const Array< Point > & v )

inlinestaticprivate

Definition at line 8848 of file geom_algorithms.H.

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

Referenced by inward(), and outward().

◆ line_intersect()

static Point Aleph::ConvexPolygonOffset::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 8899 of file geom_algorithms.H.

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

Referenced by Aleph::PolygonOffset::line_intersect(), and outward().

◆ offset_edge()

static void Aleph::ConvexPolygonOffset::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) moved by distance d along its outward (or inward) normal.

inward=true for CCW polygon means the normal is (dy, -dx) pointing to the interior.

The entire computation is performed in mpfr_class space because perpendicular-distance normalization involves sqrt, which is irrational for general rational inputs. Staying in mpfr avoids the costly mpfr->mpq->mpfr round-trips that produce large-denominator rationals and degrade subsequent arithmetic.

Definition at line 8869 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Point::get_x(), Aleph::Point::get_y(), hypot(), and inward().

Referenced by inward(), Aleph::PolygonOffset::offset_edge(), and outward().

◆ outward()

static Polygon Aleph::ConvexPolygonOffset::outward	(	const Polygon &	convex_poly,
		const Geom_Number &	distance
	)

inlinestatic

Outward offset (dilation) of a convex polygon.

Parameters

convex_poly	A closed convex polygon.
distance	Perpendicular distance to move each edge outward.

Returns: The expanded polygon.

Definition at line 8968 of file geom_algorithms.H.

References Aleph::Polygon::add_vertex(), ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Polygon::close(), ensure_ccw(), extract_verts(), is_convex(), line_intersect(), offset_edge(), Aleph::Array< T >::reserve(), Aleph::Polygon::size(), and Aleph::Array< T >::size().

Referenced by TEST_F().

◆ signed_double_area()

static Geom_Number Aleph::ConvexPolygonOffset::signed_double_area ( const Array< Point > & v )

inlinestaticprivate

Definition at line 8843 of file geom_algorithms.H.

References Aleph::GeomPolygonUtils::signed_double_area().

Friends And Related Symbol Documentation

◆ PolygonOffset

friend class PolygonOffset

friend

Definition at line 8836 of file geom_algorithms.H.

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

geom_algorithms.H

Static Public Member Functions

Static Private Member Functions

Friends

Detailed Description

Complexity

Member Function Documentation

◆ ensure_ccw()

◆ extract_verts()

◆ inward()

◆ is_convex()

◆ line_intersect()

◆ offset_edge()

◆ outward()

◆ signed_double_area()

Friends And Related Symbol Documentation

◆ PolygonOffset