Aleph::MinkowskiSumConvex Class Reference

Exact Minkowski sum of two closed convex polygons. More...

#include <geom_algorithms.H>

Public Member Functions
Polygon	operator() (const Polygon &P, const Polygon &Q) const
	Compute the Minkowski sum of two convex polygons.

Static Private Member Functions
static Array< Point >	extract_vertices (const Polygon &poly)
static Geom_Number	signed_double_area (const Array< Point > &v)
static bool	is_convex (const Array< Point > &verts)
static Array< Point >	normalize (Array< Point > v)
	Ensure CCW and rotate so that the bottom-most vertex is first.
static Point	edge_vec (const Array< Point > &v, const size_t i)
static Geom_Number	cross (const Point &a, const Point &b)

Detailed Description

Exact Minkowski sum of two closed convex polygons.

The Minkowski sum P ⊕ Q of two convex polygons P and Q is a convex polygon whose vertices are sums of vertex pairs from P and Q. The algorithm merges the edge vectors of both polygons sorted by polar angle in O(n + m).

Requirements

• Both polygons must be closed and convex with ≥ 3 vertices.
• Vertices may be CW or CCW (normalized internally to CCW).

Complexity

• Time: O(n + m)
• Space: O(n + m)

Example

Polygon P;
P.add_vertex(Point(0,0)); P.add_vertex(Point(1,0)); P.add_vertex(Point(0,1));
P.close();
Polygon Q;
Q.add_vertex(Point(0,0)); Q.add_vertex(Point(2,0)); Q.add_vertex(Point(0,2));
Q.close();
MinkowskiSumConvex ms;
Polygon R = ms(P, Q);

Definition at line 7352 of file geom_algorithms.H.

Member Function Documentation

cross()

static Geom_Number Aleph::MinkowskiSumConvex::cross ( const Point &  a, const Point &  b  )

inlinestaticprivate

Definition at line 7398 of file geom_algorithms.H.

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

Referenced by operator()().

edge_vec()

static Point Aleph::MinkowskiSumConvex::edge_vec ( const Array< Point > &  v, const size_t  i  )

inlinestaticprivate

Definition at line 7392 of file geom_algorithms.H.

References Aleph::Array< T >::size().

Referenced by operator()().

extract_vertices()

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

inlinestaticprivate

Definition at line 7355 of file geom_algorithms.H.

References Aleph::GeomPolygonUtils::extract_vertices().

Referenced by operator()().

is_convex()

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

inlinestaticprivate

Definition at line 7365 of file geom_algorithms.H.

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

Referenced by operator()().

normalize()

static Array< Point > Aleph::MinkowskiSumConvex::normalize ( Array< Point >  v )

inlinestaticprivate

Ensure CCW and rotate so that the bottom-most vertex is first.

Definition at line 7373 of file geom_algorithms.H.

References Aleph::and, Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::GeomPolygonUtils::ensure_ccw(), Aleph::Array< T >::reserve(), and Aleph::Array< T >::size().

Referenced by operator()().

operator()()

Polygon Aleph::MinkowskiSumConvex::operator() ( const Polygon &  P, const Polygon &  Q  ) const

inline

Compute the Minkowski sum of two convex polygons.

Parameters

P	First convex polygon.
Q	Second convex polygon.

Returns

Convex polygon P ⊕ Q.

Exceptions

domain_error

if either polygon is not closed, has < 3 vertices, or is not convex.

Definition at line 7414 of file geom_algorithms.H.

References Aleph::Polygon::add_vertex(), ah_domain_error_if, Aleph::and, Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), cross(), edge_vec(), Aleph::eq(), extract_vertices(), is_convex(), normalize(), Aleph::Array< T >::reserve(), and Aleph::Array< T >::size().

signed_double_area()

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

inlinestaticprivate

Definition at line 7360 of file geom_algorithms.H.

References Aleph::GeomPolygonUtils::signed_double_area().

---

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

• geom_algorithms.H