I came across this computational geometry problem and have not been able to find a satisfactory solution for it. A ray is known to originate from within an n-dimensional hypercube (AABB) in any direction. I need to determine the vertices of the AABB closest to the ray in order of their distance to it.
The most obvious brute-force solution would be to calculate the distance of all vertices to the ray and then sort them. However, because the number of vertices is exponential ($2^n$, where n is the dimension), ideally it would be an online algorithm that generates one solution at a time, already in the correct order. Each iteration should run in polynomial time, and the algorithm can be stopped after a condition is met.
Here is a graphic illustrating the concept for the 2d and 3d cases.
An approach using an infinite line instead of a ray would also be acceptable.
The ray is given as an origin point and a directional unit vector. If anyone knows of an algorithm or relevant formula that fits the description or could point me in the right direction it would be greatly appreciated.
