Aleph::RotatingCalipersConvexPolygon Class Reference

Rotating calipers metrics for convex polygons. More...

#include <geom_algorithms.H>

Classes
struct	DiameterResult
struct	WidthResult

Static Public Member Functions
static DiameterResult	diameter (const Polygon &poly)
	Compute convex polygon diameter (farthest vertex pair).
static WidthResult	minimum_width (const Polygon &poly)
	Compute the minimum width of a closed convex polygon.

Static Private Member Functions
static Array< Point >	extract_vertices (const Polygon &poly)
	Extract polygon vertices into an array.
static bool	is_convex (const Array< Point > &verts)
	Check if a polygon vertex cycle is convex.
static DiameterResult	make_diameter (const Point &a, const Point &b)

Detailed Description

Rotating calipers metrics for convex polygons.

Computes two standard convex-polygon metrics:

• Diameter (farthest pair of vertices).
• Minimum width (minimum distance between two parallel supporting lines).

Requirements

• The input polygon must be closed.
• The input polygon must be convex (collinear consecutive triples allowed).

Complexity

• Diameter: O(n) time.
• Minimum width: O(n) time (rotating calipers).
• Space: O(n) for temporary vertex storage.

Definition at line 1274 of file geom_algorithms.H.

Member Function Documentation

diameter()

static DiameterResult Aleph::RotatingCalipersConvexPolygon::diameter ( const Polygon &  poly )

inlinestatic

Compute convex polygon diameter (farthest vertex pair).

Parameters

poly	Closed convex polygon.

Returns

Farthest pair and squared distance.

Exceptions

domain_error

if the polygon is not closed, has < 2 vertices, or is non-convex.

Definition at line 1339 of file geom_algorithms.H.

References ah_domain_error_if, Aleph::and, Aleph::area_of_parallelogram(), Aleph::RotatingCalipersConvexPolygon::DiameterResult::distance_squared, Aleph::divide_and_conquer_partition_dp(), extract_vertices(), is_convex(), k, and make_diameter().

Referenced by main(), TEST_F(), TEST_F(), and Aleph::visualize_rotating_calipers().

extract_vertices()

static Array< Point > Aleph::RotatingCalipersConvexPolygon::extract_vertices ( const Polygon &  poly )

inlinestaticprivate

Extract polygon vertices into an array.

Parameters

poly	Input polygon.

Returns

Vertex array in iteration order.

Exceptions

domain_error

if poly is not closed or has fewer than 2 vertices.

Definition at line 1302 of file geom_algorithms.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::GeomPolygonUtils::extract_vertices(), Aleph::Polygon::is_closed(), and Aleph::Polygon::size().

Referenced by diameter(), and minimum_width().

is_convex()

static bool Aleph::RotatingCalipersConvexPolygon::is_convex ( const Array< Point > &  verts )

inlinestaticprivate

Check if a polygon vertex cycle is convex.

Convexity is tested by scanning all consecutive triples and ensuring all non-zero turns have the same sign. Collinear triples are ignored.

Parameters

verts

Polygon vertices.

Returns

True if convex (or degenerate with < 3 vertices), false otherwise.

Definition at line 1320 of file geom_algorithms.H.

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

Referenced by diameter(), and minimum_width().

make_diameter()

static DiameterResult Aleph::RotatingCalipersConvexPolygon::make_diameter ( const Point &  a, const Point &  b  )

inlinestaticprivate

Definition at line 1325 of file geom_algorithms.H.

References Aleph::Point::distance_squared_to().

Referenced by diameter().

minimum_width()

static WidthResult Aleph::RotatingCalipersConvexPolygon::minimum_width ( const Polygon &  poly )

inlinestatic

Compute the minimum width of a closed convex polygon.

The width for an edge is the maximum perpendicular distance from vertices to the edge line; the minimum width is the minimum of these edge widths.

Parameters

poly	Closed convex polygon.

Returns

Supporting edge, antipodal vertex, and squared width.

Note

Uses rotating calipers in O(n) for convex polygons.

Exceptions

domain_error

if the polygon is not closed, has < 2 vertices, or is non-convex.

Definition at line 1394 of file geom_algorithms.H.

References ah_domain_error_if, Aleph::and, Aleph::area_of_parallelogram(), Aleph::divide_and_conquer_partition_dp(), extract_vertices(), initialized, is_convex(), and k.

Referenced by main(), TEST_F(), and Aleph::visualize_rotating_calipers().

---

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

• geom_algorithms.H