Aleph::ConvexPolygonDistanceGJK Class Reference

Distance between two closed convex polygons using GJK. More...

#include <geom_algorithms.H>

Collaboration diagram for Aleph::ConvexPolygonDistanceGJK:

Classes
struct	ClosestSimplexResult
struct	Result
	Holds the results of the distance computation. More...
struct	SupportPoint
	A point in the Minkowski difference and its source components. More...

Public Member Functions
Result	operator() (const Polygon &p, const Polygon &q) const
	Compute the distance between two closed convex polygons.

Static Private Member Functions
static double	to_double (const Geom_Number &v)
static double	dot2 (const double ax, const double ay, const double bx, const double by) noexcept
static double	norm2 (const double x, const double y) noexcept
static Point	point_from_double (const double x, const double y)
static Point	lerp_point (const Point &a, const Point &b, const double t)
static Point	centroid_of (const Array< Point > &v)
static SupportPoint	support (const Array< Point > &p, const Array< Point > &q, const double dx, const double dy)
static bool	polygons_intersect_or_contain (const Polygon &p, const Polygon &q)
static ClosestSimplexResult	closest_from_simplex (const std::vector< SupportPoint > &simplex)
static Result	exact_refine_disjoint (const Polygon &p, const Polygon &q, const Array< Point > &pv, const Array< Point > &qv)

Static Private Attributes
static constexpr size_t	kMaxIters = 64
static constexpr double	kEps = 1e-12

Detailed Description

Distance between two closed convex polygons using GJK.

The algorithm runs a 2D GJK loop on the Minkowski difference to detect overlap and drive the search direction. For robust witness output, disjoint cases are refined with exact point-to-segment checks.

Requirements

• Both polygons must be closed and convex with >= 3 vertices.

Complexity

• GJK phase: O((n + m) * k), where k is the number of iterations.
• Refinement (disjoint): O(n * m).

Definition at line 7511 of file geom_algorithms.H.

Member Function Documentation

centroid_of()

static Point Aleph::ConvexPolygonDistanceGJK::centroid_of ( const Array< Point > &  v )

inlinestaticprivate

Definition at line 7585 of file geom_algorithms.H.

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

Referenced by operator()().

closest_from_simplex()

static ClosestSimplexResult Aleph::ConvexPolygonDistanceGJK::closest_from_simplex ( const std::vector< SupportPoint > &  simplex )

inlinestaticprivate

Definition at line 7663 of file geom_algorithms.H.

References Aleph::ConvexPolygonDistanceGJK::SupportPoint::a, ah_domain_error_if, Aleph::and, Aleph::ConvexPolygonDistanceGJK::SupportPoint::b, Aleph::blossom_maximum_cardinality_matching(), dot2(), Aleph::Point::get_x(), Aleph::Point::get_y(), kEps, lerp_point(), norm2(), out, point_from_double(), Aleph::ConvexPolygonDistanceGJK::ClosestSimplexResult::reduced_simplex, to_double(), Aleph::ConvexPolygonDistanceGJK::SupportPoint::vx, and Aleph::ConvexPolygonDistanceGJK::SupportPoint::vy.

Referenced by operator()().

dot2()

static double Aleph::ConvexPolygonDistanceGJK::dot2 ( const double  ax, const double  ay, const double  bx, const double  by  )

inlinestaticprivatenoexcept

Definition at line 7558 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching().

Referenced by closest_from_simplex(), norm2(), and support().

exact_refine_disjoint()

static Result Aleph::ConvexPolygonDistanceGJK::exact_refine_disjoint ( const Polygon &  p, const Polygon &  q, const Array< Point > &  pv, const Array< Point > &  qv  )

inlinestaticprivate

Definition at line 7860 of file geom_algorithms.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::ConvexPolygonDistanceGJK::Result::intersects, out, polygons_intersect_or_contain(), Aleph::Segment::project(), and Aleph::square_root().

Referenced by operator()().

lerp_point()

static Point Aleph::ConvexPolygonDistanceGJK::lerp_point ( const Point &  a, const Point &  b, const double  t  )

inlinestaticprivate

Definition at line 7576 of file geom_algorithms.H.

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

Referenced by closest_from_simplex().

norm2()

static double Aleph::ConvexPolygonDistanceGJK::norm2 ( const double  x, const double  y  )

inlinestaticprivatenoexcept

Definition at line 7566 of file geom_algorithms.H.

References dot2(), and y.

Referenced by closest_from_simplex(), and operator()().

operator()()

Result Aleph::ConvexPolygonDistanceGJK::operator() ( const Polygon &  p, const Polygon &  q  ) const

inline

Compute the distance between two closed convex polygons.

Exceptions

domain_error

If either polygon is open, has < 3 vertices, or is non-convex.

Definition at line 7937 of file geom_algorithms.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), centroid_of(), closest_from_simplex(), Aleph::ConvexPolygonDistanceGJK::ClosestSimplexResult::contains_origin, Aleph::ConvexPolygonDistanceGJK::ClosestSimplexResult::cx, Aleph::ConvexPolygonDistanceGJK::ClosestSimplexResult::cy, Aleph::ConvexPolygonDistanceGJK::Result::distance_squared, exact_refine_disjoint(), Aleph::GeomPolygonUtils::extract_vertices(), Aleph::Polygon::is_closed(), Aleph::GeomPolygonUtils::is_convex(), kEps, kMaxIters, norm2(), polygons_intersect_or_contain(), r, Aleph::ConvexPolygonDistanceGJK::ClosestSimplexResult::reduced_simplex, Aleph::Polygon::size(), support(), to_double(), Aleph::ConvexPolygonDistanceGJK::ClosestSimplexResult::witness_a, and Aleph::ConvexPolygonDistanceGJK::ClosestSimplexResult::witness_b.

point_from_double()

static Point Aleph::ConvexPolygonDistanceGJK::point_from_double ( const double  x, const double  y  )

inlinestaticprivate

Definition at line 7571 of file geom_algorithms.H.

References y.

Referenced by closest_from_simplex(), and lerp_point().

polygons_intersect_or_contain()

static bool Aleph::ConvexPolygonDistanceGJK::polygons_intersect_or_contain ( const Polygon &  p, const Polygon &  q  )

inlinestaticprivate

Definition at line 7636 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PointInPolygonWinding::contains(), Aleph::Polygon::Segment_Iterator::has_curr(), and Aleph::Dlink::Iterator::has_curr().

Referenced by exact_refine_disjoint(), and operator()().

support()

static SupportPoint Aleph::ConvexPolygonDistanceGJK::support ( const Array< Point > &  p, const Array< Point > &  q, const double  dx, const double  dy  )

inlinestaticprivate

Definition at line 7598 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), dot2(), Aleph::Array< T >::size(), and to_double().

Referenced by operator()().

to_double()

static double Aleph::ConvexPolygonDistanceGJK::to_double ( const Geom_Number &  v )

inlinestaticprivate

Definition at line 7553 of file geom_algorithms.H.

References Aleph::geom_number_to_double().

Referenced by closest_from_simplex(), lerp_point(), operator()(), and support().

Member Data Documentation

kEps

constexpr double Aleph::ConvexPolygonDistanceGJK::kEps = 1e-12

staticconstexprprivate

Definition at line 7551 of file geom_algorithms.H.

Referenced by closest_from_simplex(), and operator()().

kMaxIters

constexpr size_t Aleph::ConvexPolygonDistanceGJK::kMaxIters = 64

staticconstexprprivate

Definition at line 7550 of file geom_algorithms.H.

Referenced by operator()().

---

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

• geom_algorithms.H