Comparing angles, efficiently
So recently, I came across another interesting puzzle on Twitter:
And of course it would be possible to throw a bunch of sine and cosine functions at this problem to solve it, but whenever possible, I try to avoid trig functions, as they tend to be a lot slower than ordinary multiplications, additions, etc.
The problem can basically be expressed as comparing angles, more specifically, we’re dealing with 45° sections, and we just have to find out for a given input angle, in which 45° segment does it fit. Once we know the segment, it’s all about finding out how close to either border of the segment the input is.
It would be nice to get a smooth linear interpolation for this comparison, but that quickly requires using
atan, so we’ll look at a good approximation that can be achieved using the dot product.
I’m calling it an approximation, because while the method will output the correct segment, the linear interpolation of the angle, how far it is through the segment, will only be kinda linear if you like wonky lines..
The basic idea is to use the dot product to figure out how aligned two vectors are. If we have two normalized vectors, their dot product is just the cosine of the angle between them (note that this works for 2d as well, not just in 3d, since you could just set the z component of a 3d vector to always be zero and you’d get the same result).
We precompute 8 normalized vectors, one pointing to every adjacent cell, and then take the input vector and calculate the dot product with these 8 vectors. Plotting the results, we should get something like this.
We can clearly see that the input lies between the 6th and the 7th vector, as these are the highest values. We also know that the value of the 2nd highest result must be at least sqrt(2)/2, since that’s the cosine of 45°, so let’s subtract sqrt(2)/2 from all the results.
The only positive results that remain now must be from vectors adjacent to the segment in which the input lies. After that, we can simply figure out some interpolation from the two positive values by normalizing them such that their sum is 1. That way we’re forcing the cosine curve that lies between them in to the range [0,1].
We can try to figure out how the resulting value would behave when the input vector moves within the segment. In the plot below, x represents an angle from 0° to 45° (0 to pi/4), and the two curves are the outputs we get with this method on either ends of the segment.
This looks roughly like what we need. One of the values is at zero and the other at 1 when the input is completely to one end of the segment, and vice versa when it’s at the other end of the segment.
I haven’t used Mathematica in a while by the way, so if anyone knows a nicer way to express that last formula, please tell me :)
I hope this was helpful, feel free to ask questions if anything wasn’t clear!