Get nearest vector in 3D space

Question

I have a set of unit vector orignated from (0,0), distributed evenly with alpha and theta angle from 0 to 360 and 0 to 180. Alpha and Theta are used to index a 2D array of these vectors.

Given an arbitrary direction (another vector originated from (0,0)) how can i find the vector which is the nearest (lets say a floor operation) ?

I can make it using Cartesian to Spherical, then obtain the angles and make a floor on the both angles, then finally get the index of the vector in the original array set. This work perfectly...

But Cartesian to Spherical is using trigonometric function which are heavy on computer (ArcTan)... is there any tricks to get the same result without trigonometric computation ? maybe quaternion could help but i do not know about it..

what i'm doing is in pseudo code for one quadrant

        var alpha = Math.atan(direction.z / direction.x);
        var I = Math.floor(alpha / deltaAlpha);

        var x2 = direction.x * direction.x;
        var y2 = direction.y * direction.y;
        var z2 = direction.z * direction.z;

        var theta= Math.atan(  (x2 + z2) / y2);
        var J = Math.floor(beta / deltaTheta);

then i get the I,J index of my vector set... but again, how to avoid $$\alpha = atan(z/x)$$ and $$\theta=atan((x^2 + z^2)/ y^2)$$ which are GPU or CPU expensive when running over thousand of location on each frames..

Answer 1

I would treat the vectors as points on the unit sphere and use a k-d tree (or a variant) to store the points. This way, you can identify the vector (point) nearest some new unclassified point in time logarithmic in the number of stored points.

Answer 2

Distance between vectors on the unit sphere can be measured by angles between them, so you need a vector from the set with the smallest angle between it and your specified direction vector $\vec u$. Next, we can use the property of cosine being a decreasing function on angles in $[0, \pi]$: thus, the smaller the angle, the bigger the cosine. Finally, the cosine of two unit vectors is simply their scalar product.

If your vectors are defined by angles $\theta$ and $\alpha$, the simplest thing to do is to convert them to spherical coordinates, like

$$\vec v = \begin{pmatrix} \cos(\alpha)\cos(\theta) \\ \cos(\alpha)\sin(\theta) \\ \sin(\alpha) \end{pmatrix}$$

and then compute the scalar products as

$$\vec v \cdot \vec u = v_xu_x + v_yu_y + v_zu_z$$

The vector $\vec v$ with the biggest scalar product $\vec v \cdot \vec u$ is the one you are searching for.