Fastest way to find the angle between two points

Question

To increase the speed at which I find the sine/cosine of an angle, I have built a reference table instead of calculating them on the fly. I have the same idea with finding the angle from one point to another.

I have created a table of 3600 normalized vectors (3600 / 10 = accuracy of one tenth of a degree). Whenever I need to know the angle from one point to the next, I look through the table to find the best match. However, I am concerned that this might be slower than using math.atan2().

Here is the code I am using:

Create the vector table:

// vector to angle table
var vectorToAngleTable = new Array();
for (i = 0; i < 3600; i += 1) {
    vectorToAngleTable[i] = new Vector2();
    vectorToAngleTable[i] = RotatePoint(forwardVector, i / 10);
}

Find the angle from two points:

function NormalizeVector(vector) {
    var toReturn = vector;
    var dist = Math.sqrt(vector.x * vector.x + vector.y * vector.y);
    toReturn.x /= dist.x;
    toReturn.y /= dist.y;
    return toReturn;
}

function PointDirection(position, target) {
    var vector = target;
    var toReturn = 0;
    var smallest = 1.0;
    vector.x -= position.x;
    vector.y -= position.y;
    vector = NormalizeVector(vector);
    for (i = 0; i < 3600; i += 1) {
        if (PointDistance(vectorToAngleTable[i], vector) < smallest) {
            smalllest = PointDistance(vectorToAngleTable[i], vector);
            toReturn = i;
        }
    }
    return toReturn;
}

function PointDistance(point1, point2) {
    return Math.sqrt(((point2.x - point1.x) * (point2.x - point1.x)) + ((point2.y - point1.y) * (point2.y - point1.y)));
}

As you can see, my concern is all the lines of code it is going through, and how many entries there are on the table that it looks through. I would love to know the fastest way to find the angle, no matter what the method is.

Answer 1

As angle(v1, v2) = acos( (v1x * v2x + v1y * v2y) / (sqrt(v1x^2+v1y^2) * sqrt(v2x^2+v2y^2)) ) and we know v2 = [1, 0]

var v = {x: 0, y: 1},
    angleRad = Math.acos( v.x / Math.sqrt(v.x*v.x + v.y*v.y) ),
    angleDeg = angleRad * 180 / Math.PI;

where v is the vector [point2.x - point1.x , point2.y - point1.y]

---

Edit - I just realised you may have meant treat each point as a vector, in which case it'd be

var v1 = {x: 0, y: 1}, v2 = {x: 1, y: 0},
    angleRad = Math.acos( (v1.x * v2.x + v1.y * v2.y) / ( Math.sqrt(v1.x*v1.x + v1.y*v1.y) * Math.sqrt(v2.x*v2.x + v2.y*v2.y) ) ),
    angleDeg = angleRad * 180 / Math.PI;

where v1 is the vector [point1.x , point1.y] and v2 is [point2.x , point2.y]

---

Edit 2
To speed up if you're using the vectors length many times, save it as e.g. v.length = ... so you can get it without re-calculating again. If you know every vector will need it's angles calculated multiple times, use the first method I wrote and cache it, i.e. v.angle = .... You can then you can do v2.angle - v1.angle to find angle between the two, etc.
i.e. have

function Vector(x, y){
    this.x = x;
    this.y = y;
    this.length = Math.sqrt(x*x + y*y);
    this.angle = Math.acos( x / this.length );
}

---

jsperf of pre-computing and finding in an array of 3601 items vs using acos directly

Answer 2

That's definitely going to be smaller than a call to atan2, since it's a square root and then a linear search through 3600 possibilities. Conversely many processors implement atan2 directly — it's FPATAN in Intel land.