 Axis-aligned bounding box

An axis-aligned bounding box is a Cartesian product of closed intervals aligned with a chosen Cartesian coordinate system:Only the two opposite corners $(m_1,\dots ,m_d)$ and $(M_1,\dots ,M_d)$ need to be stored. In two dimensions it is a rectangle. Changing the Cartesian coordinate system can change how tightly the axis-aligned bounding box fits the same object.^[ref]

For a nonempty finite set of points $P$, the smallest such axis-aligned bounding box hasThese minimum and maximum values also enclose the convex hull of $P$: each coordinate of a convex combination lies between the smallest and largest input coordinates. In particular, three vertices of a polygon determine the axis-aligned bounding box of a filled triangle. For a general nonempty compact set, the same formulas use all its points; inspecting only an arbitrary finite sample is insufficient.

Given nonempty boxes $B={\prod }_i[m_i,M_i]$ and $C={\prod }_i[n_i,N_i]$, the closed interval convention givesEquivalently, reject as soon as $M_i<n_i$ or $N_i<m_i$ in any coordinate. The surviving set intersection has endpoints $\max (m_i,n_i)$ and $\min (M_i,N_i)$. This is an exact box test, while its conclusion about enclosed objects remains a conservative enclosure test.^[ref]

Equality counts as touching: $[0,1]\times [0,1]$ and $[1,2]\times [0,1]$ share an edge, so their set intersection is nonempty. Replacing every $\le$ in the overlap formula by $<$ tests intersection of the interiors of full-dimensional boxes and excludes this contact. A zero-width closed interval can represent a point or a lower-dimensional enclosure, and must not automatically be discarded when touching counts. A box with some $m_i>M_i$ is empty; test emptiness before applying rules intended for nonempty boxes. The broad phase must retain touching candidates whenever the narrow phase counts touching as a hit.

For nonempty boxes, the smallest enclosing axis-aligned bounding box of their set union isThis operation supplies the parent boxes in a bounding volume hierarchy. It is an enclosure of the set union, rather than generally the set union itself. In floating-point arithmetic, comparisons are conclusive only for endpoints that still enclose the intended exact objects; use certified bounds such as interval arithmetic with outward rounding when that guarantee is required.

// Target: analysis.bigb