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 7551 of file geom_algorithms.H.

Member Function Documentation

◆ centroid_of()

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

inlinestaticprivate

Definition at line 7625 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 7708 of file geom_algorithms.H.

References Aleph::ConvexPolygonDistanceGJK::SupportPoint::a, ah_domain_error_if, Aleph::and, Aleph::ConvexPolygonDistanceGJK::SupportPoint::b, Aleph::divide_and_conquer_partition_dp(), dot2(), Aleph::Point::get_x(), Aleph::Point::get_y(), kEps, lerp_point(), norm2(), 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 7598 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp().

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
	)