The Gilbert-Johnson-Keerthi convex shape intersection algorithm. It can take any two convex sets and tell you if they overlap, while converging on a separating

The Gilbert-Johnson-Keerthi convex shape intersection algorithm. It can take any two convex sets and tell you if they overlap, while converging on a separating axis or a penetration point, if it exists. All you need is a support function that returns a point in the set that is furthest along a given direction vector. The algorithm works in an arbitrary number of dimensions. Basically, it operates on a new shape which is the Minkowski difference of the two intersected sets. If the difference-shape contains the origin, then the two shapes overlap. The algorithm iteratively constructs simplexes inside the Minkowski difference, trying to build one that encompasses the origin. This allows it to have essentially constant memory for a given dimension of problem. It's a very elegant formulation of a very general problem. It's so pleasing that you can intersect cylinders with cones, or oriented cubes with frustums, or polytopes with superellipses all with the exact same single algorithm. The Wikipedia writeup is terrible, so I may do my own with nice illustrations at some point.