Самый быстрый способ найти угол между двумя точками

Чтобы увеличить скорость, на которой я нахожу синус/косинус угла, я построил справочную таблицу вместо вычисления их на лету. У меня есть та же идея с поиском угла от одной точки к другой.

Я создал таблицу из 3600 нормализованных векторов (3600/10 = точность одной десятой градуса). Всякий раз, когда мне нужно знать угол от одной точки к другой, я просматриваю стол, чтобы найти лучший матч. Однако я обеспокоен тем, что это может быть медленнее, чем использование math.atan2().

Вот код, который я использую:

Создайте векторную таблицу:

// 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);
}

Найти угол из двух точек:

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)));
}

Как вы можете видеть, моя забота - это все строки кода, которые он просматривает, и количество записей в таблице, которые они просматривают. Я хотел бы узнать самый быстрый способ найти угол, независимо от того, какой метод.

Ответы

Ответ 1

Как angle(v1, v2) = acos( (v1x * v2x + v1y * v2y) / (sqrt(v1x^2+v1y^2) * sqrt(v2x^2+v2y^2)) ), и мы знаем 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;

где v - вектор [point2.x - point1.x , point2.y - point1.y]

Изменить - я просто понял, что вы, возможно, имели в виду рассматривать каждую точку как вектор, и в этом случае это было бы

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;

где v1 - вектор [point1.x , point1.y], а v2 - [point2.x , point2.y]

Редактировать 2
Чтобы ускорить работу, если вы используете длину векторов много раз, сохраните ее, например. v.length = ..., чтобы вы могли получить его без повторного вычисления снова. Если вы знаете, что каждому вектору потребуются его вычисления, рассчитанные несколько раз, используйте первый метод, который я написал, и кешируем его, т.е. v.angle = .... Затем вы можете сделать v2.angle - v1.angle, чтобы найти угол между ними и т.д.
то есть

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 предварительного вычисления и нахождения в массиве элементов 3601 против acos напрямую

Ответ 2

Это определенно будет меньше вызова atan2, так как это квадратный корень, а затем линейный поиск по 3600 возможностям. Наоборот, многие процессоры реализуют atan2 напрямую - это FPATAN на территории Intel.