I recently did an AABB (Axes Aligned Bounding Box) Intersection implementation on 2D and 3D objects for which I came up with such a short (and very fast) solution as follows.
The demonstration below is for
2D rectangles, nevertheless the algorithm promises extension to
nD spaces as well, with no additional effort.
AABB has been a standard part of many small and huge computational geometry packages in order to speed up intersection and collision detection, for years. For me, not fan of large complicated libraries, I preferred however to do it myself with no consultation with any of them.
With the above introduction, it is quite possible that I might have missed some situations on those the following simplistic algorithm might fail. If there was no such failure this algorithm looks like the fastest intersection test for AABB and the most easy-to-extend to nD as well as it requires only few simple numeric comparison.
An AABB is usually defined by two points as
(mins,maxs), e.g., in 2D
(0,0) are the minimums for
Y axes, and
(1,1) are the maximums for
Y axes respectively. Similarly for
nD it could be as follows.
P = (x1,y1,z1,...,x2,y2,z2,...)
Let's P and Q be two AABB:
P(mins,maxs) % e.g., in 2D (0,0,1,1) Q(mins,maxs) % e.g., in 2D (0.1,-1,3,2)
Intersection between the two P and Q happens only if:
P(mins) <= Q(maxs) & Q(mins) <= P(maxs)
So for the 2D example given above,
P(mins) = (0,0) and
P(maxs) = (1,1)
and for Q:
Q(mins) = (0.1,-1) and
Q(maxs) = (3,2)
Now if we check the conditions mentioned above:
(0,0) <= (3,2) i.e.,
(0 <= 3) and
(0 <= 2) and
(0.1,-1) <= (1,1) i.e.,
(0.1 <= 1) and
(-1 <= 1), we see that all conditions satisfy which means the two AABB P and Q intersect.
Therefore the algorithm requires only few simple comparisons which can be implemented in various forms efficiently. Furthermore, the algorithm can easily be extended into nD.
I wonder if this such simple algorithm is the fastest, the most elegant and extendable to nD for finding intersection between AABBs?
Any comment about potential shortcoming or any discussion or share of experiences would be helpful.