intersections.hpp File Reference

The pairwise intersection table: intersects(A, B [, tau]) overloads for all combinations of {point, Box, Ball, Ellipsoid, Simplex} plus the query-only objects {Segment, Halfspace}, and the closest-point machinery behind the solver-backed cells. More...

#include <cmath>
#include <limits>
#include <stdexcept>
#include <vector>
#include <Eigen/Dense>
#include <Eigen/Eigenvalues>
#include "ellipsoid_tree/geometry.hpp"
#include "ellipsoid_tree/detail/minimize_scalar.hpp"
#include "ellipsoid_tree/detail/linear_feasibility.hpp"

Classes
struct	ellipsoid_tree::ClosestPointResult
	Result of a closest-point query: the closest point and its squared distance. More...
struct	ellipsoid_tree::BoxClosestPointOptions
	Options controlling the iterative (M-metric) closest_point_in_box solve. More...

Namespaces
namespace	ellipsoid_tree

Functions
ClosestPointResult	ellipsoid_tree::closest_point_in_simplex (const Eigen::Ref< const Eigen::VectorXd > &p, const Eigen::Ref< const Eigen::MatrixXd > &V, const Eigen::Ref< const Eigen::MatrixXd > &M)
	Closest point to p in the solid simplex conv(V), in the metric ||y||_M^2 = y^T M y with M symmetric positive definite.
ClosestPointResult	ellipsoid_tree::closest_point_in_simplex (const Eigen::Ref< const Eigen::VectorXd > &p, const Eigen::Ref< const Eigen::MatrixXd > &V)
	Euclidean special case (M = I).
ClosestPointResult	ellipsoid_tree::closest_point_in_box (const Eigen::Ref< const Eigen::VectorXd > &p, const Box &B)
	Closest point to p in the box, Euclidean metric: clamping, exact.
ClosestPointResult	ellipsoid_tree::closest_point_in_box (const Eigen::Ref< const Eigen::VectorXd > &p, const Box &B, const Eigen::Ref< const Eigen::MatrixXd > &M, BoxClosestPointOptions opts=BoxClosestPointOptions())
	Closest point to p in the box, in the metric ||y||_M^2 = y^T M y with M symmetric positive definite.
bool	ellipsoid_tree::intersects (const Eigen::Ref< const Eigen::VectorXd > &p, const Box &B)
	Whether point p lies in box B (componentwise coordinate-bounds test).
bool	ellipsoid_tree::intersects (const Eigen::Ref< const Eigen::VectorXd > &p, const Ball &B)
	Whether point p lies in ball B (distance to center vs radius).
bool	ellipsoid_tree::intersects (const Eigen::Ref< const Eigen::VectorXd > &p, const Ellipsoid &E, double tau)
	Whether point p lies in ellipsoid E(tau) (Mahalanobis test via an LDLT solve).
bool	ellipsoid_tree::intersects (const Eigen::Ref< const Eigen::VectorXd > &p, const Halfspace &H)
	Whether point p lies in halfspace H (closed-form normal . p <= offset).
bool	ellipsoid_tree::intersects (const Box &A, const Box &B)
	Whether boxes A and B overlap (per-axis interval overlap).
bool	ellipsoid_tree::intersects (const Box &A, const Ball &B)
	Whether box A and ball B overlap (distance from the center to its clamped closest point in the box vs radius).
bool	ellipsoid_tree::intersects (const Box &A, const Halfspace &H)
	Whether box A meets halfspace H (support function: min of normal . x over the box vs offset).
bool	ellipsoid_tree::intersects (const Ball &A, const Ball &B)
	Whether balls A and B overlap (center distance vs the sum of radii).
bool	ellipsoid_tree::intersects (const Ball &A, const Halfspace &H)
	Whether ball A meets halfspace H (closed-form support-function comparison against the offset).
bool	ellipsoid_tree::intersects (const Ellipsoid &E, const Halfspace &H, double tau)
	Whether ellipsoid E(tau) meets halfspace H (support test: normal . mu - tau*sqrt(normal^T Sigma normal) vs offset).
bool	ellipsoid_tree::intersects (const Simplex &S, const Halfspace &H)
	Whether simplex S meets halfspace H (support function: min of normal . x over the vertices vs offset).
bool	ellipsoid_tree::intersects (const Segment &S, const Box &B)
	Whether segment S meets box B (slab method along the segment's parameter).
bool	ellipsoid_tree::intersects (const Segment &S, const Ball &B)
	Whether segment S meets ball B (distance from its closest point to the center vs radius).
bool	ellipsoid_tree::intersects (const Segment &S, const Ellipsoid &E, double tau)
	Whether segment S meets ellipsoid E(tau) (closed-form 1D minimization of the Mahalanobis quadratic over the segment).
bool	ellipsoid_tree::intersects (const Eigen::Ref< const Eigen::VectorXd > &p, const Simplex &S)
	Point in simplex.
bool	ellipsoid_tree::intersects (const Ball &B, const Simplex &S)
	Whether ball B and simplex S overlap (Euclidean distance from the center to the simplex, via face enumeration, vs radius).
bool	ellipsoid_tree::intersects (const Segment &seg, const Simplex &S)
	Whether segment seg meets simplex S (coordinate-interval feasibility for a full-dimensional simplex, else a tolerance-based 1D distance minimization).
bool	ellipsoid_tree::intersects (const Simplex &A, const Simplex &B)
	Simplices A and B intersect iff some point is a convex combination of both vertex sets: exists alpha, beta >= 0 with sum(alpha) = sum(beta) = 1 and V_A alpha = V_B beta — a linear feasibility problem.
bool	ellipsoid_tree::intersects (const Box &A, const Simplex &S)
	Box and simplex intersect iff exists alpha >= 0, sum(alpha) = 1, with lo <= V alpha <= hi; the two-sided bound becomes equalities with slack variables s, t >= 0: V alpha - s = lo, s + t = hi - lo.
bool	ellipsoid_tree::intersects (const Ellipsoid &A, const Ellipsoid &B, double tau)
	Exact ellipsoid-ellipsoid overlap (Gilitschenski & Hanebeck 2014): with the generalized eigendecomposition Sigma_A Phi = Sigma_B Phi Lambda, Phi^T Sigma_B Phi = I, and v = Phi^T (mu_A - mu_B), the ellipsoids overlap iff min over s in [0,1] of K(s) = 1 - s(1-s)/tau^2 * sum_i v_i^2 / (1 + s (lambda_i - 1)) is nonnegative.
bool	ellipsoid_tree::intersects (const Ball &B, const Ellipsoid &E, double tau)
	Whether ball B and ellipsoid E(tau) overlap: treats the ball as an ellipsoid (Sigma = (radius/tau)^2 I) and applies the Gilitschenski-Hanebeck test.
bool	ellipsoid_tree::intersects (const Box &A, const Ellipsoid &E, double tau)
	Whether box A and ellipsoid E(tau) overlap (closest point to mu in the box under the Sigma^{-1} metric, by projected coordinate descent, vs tau^2).
bool	ellipsoid_tree::intersects (const Ellipsoid &E, const Simplex &S, double tau)
	Whether ellipsoid E(tau) and simplex S overlap (closest point to mu in the simplex under the Sigma^{-1} metric, by face enumeration, vs tau^2).
bool	ellipsoid_tree::intersects (const Box &B, const Eigen::Ref< const Eigen::VectorXd > &p)
	Overlap test between box and point (arguments reversed).
bool	ellipsoid_tree::intersects (const Ball &B, const Eigen::Ref< const Eigen::VectorXd > &p)
	Overlap test between ball and point (arguments reversed).
bool	ellipsoid_tree::intersects (const Ellipsoid &E, const Eigen::Ref< const Eigen::VectorXd > &p, double tau)
	Overlap test between ellipsoid E(tau) and point (arguments reversed).
bool	ellipsoid_tree::intersects (const Simplex &S, const Eigen::Ref< const Eigen::VectorXd > &p)
	Overlap test between simplex and point (arguments reversed).
bool	ellipsoid_tree::intersects (const Halfspace &H, const Eigen::Ref< const Eigen::VectorXd > &p)
	Overlap test between halfspace and point (arguments reversed).
bool	ellipsoid_tree::intersects (const Ball &B, const Box &A)
	Overlap test between ball and box (arguments reversed).
bool	ellipsoid_tree::intersects (const Ellipsoid &E, const Box &A, double tau)
	Overlap test between ellipsoid E(tau) and box (arguments reversed).
bool	ellipsoid_tree::intersects (const Halfspace &H, const Box &A)
	Overlap test between halfspace and box (arguments reversed).
bool	ellipsoid_tree::intersects (const Box &A, const Segment &S)
	Overlap test between box and segment (arguments reversed).
bool	ellipsoid_tree::intersects (const Ellipsoid &E, const Ball &B, double tau)
	Overlap test between ellipsoid E(tau) and ball (arguments reversed).
bool	ellipsoid_tree::intersects (const Simplex &S, const Ball &B)
	Overlap test between simplex and ball (arguments reversed).
bool	ellipsoid_tree::intersects (const Halfspace &H, const Ball &B)
	Overlap test between halfspace and ball (arguments reversed).
bool	ellipsoid_tree::intersects (const Ball &B, const Segment &S)
	Overlap test between ball and segment (arguments reversed).
bool	ellipsoid_tree::intersects (const Simplex &S, const Ellipsoid &E, double tau)
	Overlap test between simplex and ellipsoid E(tau) (arguments reversed).
bool	ellipsoid_tree::intersects (const Halfspace &H, const Ellipsoid &E, double tau)
	Overlap test between halfspace and ellipsoid E(tau) (arguments reversed).
bool	ellipsoid_tree::intersects (const Ellipsoid &E, const Segment &S, double tau)
	Overlap test between ellipsoid E(tau) and segment (arguments reversed).
bool	ellipsoid_tree::intersects (const Halfspace &H, const Simplex &S)
	Overlap test between halfspace and simplex (arguments reversed).
bool	ellipsoid_tree::intersects (const Simplex &S, const Segment &seg)
	Overlap test between simplex and segment (arguments reversed).
bool	ellipsoid_tree::intersects (const Simplex &S, const Box &A)
	Overlap test between simplex and box (arguments reversed).

Detailed Description

The pairwise intersection table: intersects(A, B [, tau]) overloads for all combinations of {point, Box, Ball, Ellipsoid, Simplex} plus the query-only objects {Segment, Halfspace}, and the closest-point machinery behind the solver-backed cells.

Both argument orders are provided for every pair.

Semantics (see geometry.hpp): all objects are solid and closed, so touching counts as intersecting. Points are plain Eigen vectors. Every function consuming an Ellipsoid takes the scale tau at call time; a pair of ellipsoids shares a single common tau (for heterogeneous scales, fold the scale into Sigma). Cells backed by iterative solvers (ellipsoid-ellipsoid, ellipsoid-box) are exact up to solver tolerance: verdicts may go either way for configurations within ~1e-8 of exact tangency.

The ellipsoid-ellipsoid test follows: I. Gilitschenski and U. D. Hanebeck, "A Direct Method for Checking Overlap of Two Hyperellipsoids", Proc. 2014 Sensor Data Fusion: Trends, Solutions, Applications (SDF), 2014. The simplex-simplex and box-simplex cells are decided by a small phase-I LP (detail/linear_feasibility.hpp): do the two convex hulls share a point.