Дешевый алгоритм для поиска меры угла между векторами

Ответ 1

Вы пробовали алгоритм CORDIC? Это общая основа для решения полярных & harr; прямоугольные задачи только с таблицей add/subtract/bithift + table, по существу делающие вращение под углами вида tan ^-1 (2 ^-n). Вы можете обменять точность с временем выполнения, изменив количество итераций.

В вашем случае возьмите один вектор как фиксированную ссылку и скопируйте другой во временный вектор, который вы вращаете, используя кордовые углы к первому вектору (грубо делясь пополам), пока не достигнете желаемой angular точности.

( изменить: использовать знак точечного продукта, чтобы определить на каждом шаге, нужно ли вращаться вперед или назад. Хотя если множители достаточно дешевы, чтобы разрешить использование точечного продукта, то не беспокойтесь о CORDIC, возможно, использовать таблицу пар sin/cos для матриц поворота углов & pi;/2 ⁿ для решения проблемы с делением пополам.)

( edit: Мне нравится предложение Эрика Бэйнвиля в комментариях: повернуть оба вектора к нулю и отслеживать разницу в углах.)

Ответ 2

Если вам не нужен фактический эвклидовый угол, но что-то, что вы можете использовать в качестве базы для сопоставлений углов, то выбор геометрии такси может быть выбором, потому что вы можете сбросить тригонометрию и ее медленность, ПОДДЕРЖИВАЯ ТОЧНОСТЬ ( или, по крайней мере, с действительно незначительным потере точности, см. ниже).

В основных современных браузерах коэффициент ускорения находится между 1,44 - 15,2 и точность почти такая же, как и в atan2. Расчет угла алмаза в среднем в 5,01 раза быстрее, чем atan2, и с использованием встроенного кода в Firefox 18 ускорение достигает коэффициента 15,2. Сравнение скорости: http://jsperf.com/diamond-angle-vs-atan2/2.

Код очень прост:

function DiamondAngle(y, x)
{
    if (y >= 0)
        return (x >= 0 ? y/(x+y) : 1-x/(-x+y)); 
    else
        return (x < 0 ? 2-y/(-x-y) : 3+x/(x-y)); 
}

Приведенный выше код дает вам угол между 0 и 4, тогда как atan2 дает угол между -PI и PI, как показано в следующей таблице:

Обратите внимание, что угол алмаза всегда положителен и находится в диапазоне 0-4, тогда как atan2 дает также отрицательные радианы. Таким образом, угол алмаза более нормализуется. И еще одно замечание: atan2 дает немного более точный результат, потому что длина диапазона 2 * pi (т.е. 6,283185307179586), а в углах алмаза - 4. На практике это не очень важно, например. рад 2.3000000000000001 и 2.3000000000000002 оба находятся под углом к ​​алмазу 1.4718731421442295, но если мы понижаем точность, сбросив один ноль, рад 2.300000000000001 и 2.300000000000002 дает оба разных угла алмаза. Эта "точность потери" в углах алмаза настолько мала, что имеет некоторое существенное влияние только в том случае, если расстояния огромны. Вы можете играть с конверсиями в http://jsbin.com/bewodonase/1/edit?output (старая версия: http://jsbin.com/idoyon/1):

Вышеприведенный код достаточно для быстрого сравнения углов, но во многих случаях необходимо преобразовать угол алмаза в радианы и вице-верку. Если вы, например. имеют некоторый толерант в виде радианских углов, а затем у вас есть цикл 100 000 раз, где этот перенос сравнивается с другими углами, нецелесообразно проводить сравнения с использованием atan2. Вместо этого, перед циклом, вы изменяете допуск радиана к допуску на такси (алмазные углы) и делаете внутрикорректные сравнения с использованием толерантности к алмазу, и таким образом вам не нужно использовать медленные тригонометрические функции в критически важных частях кода (= в петель).

Код, который делает это преобразование, таков:

function RadiansToDiamondAngle(rad)
{
  var P = {"x": Math.cos(rad), "y": Math.sin(rad) };
  return DiamondAngle(P.y, P.x);
}  

Как вы заметили, есть cos и sin. Как вы знаете, они медленны, но вам не нужно делать преобразование в цикле, но до цикла и ускорения огромны.

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

function DiamondAngleToRadians(dia)
{
  var P = DiamondAngleToPoint(dia);
  return Math.atan2(P.y,P.x);
}

function DiamondAngleToPoint(dia)
{
  return {"x": (dia < 2 ? 1-dia : dia-3), 
  "y": (dia < 3 ? ((dia > 1) ? 2-dia : dia) : dia-4)};
}

Здесь вы используете atan2, который медленный, но идея заключается в том, чтобы использовать это вне любых циклов. Вы не можете преобразовать угол алмаза в радианы, просто умножившись на какой-то фактор, но вместо этого найдя точку в геометрии такси, в которой угол алмаза между этой точкой и положительной осью X является рассматриваемым углом алмаза и преобразующим эту точку в радианы с использованием atan2.

Этого должно быть достаточно для быстрого сравнения углов.

Конечно, есть другие методы ускорения atan2 (например, CORDIC и таблицы поиска), но AFAIK все они теряют точность и все еще могут быть медленнее, чем atan2.

ПРЕДПОСЫЛКА: Я проверил несколько методов: точечные продукты, внутренние продукты, закон косинуса, единичные круги, таблицы поиска и т.д., но ничего не было достаточно, если важны скорость и точность. Наконец, я нашел страницу в http://www.freesteel.co.uk/wpblog/2009/06/encoding-2d-angles-without-trigonometry/, которая имела желаемые функции и принципы.

Вначале я предположил, что расстояния для такси могут быть использованы для точного и быстрого сравнения расстояний, поскольку большее расстояние в евклидове больше и в такси. Я понял, что вопреки эвклидовым расстояниям угол между начальной и конечной точками влияет на расстояние такси. Только длины вертикальных и горизонтальных векторов могут быть легко и быстро преобразованы между эвклидами и такси, но в каждом другом случае вы должны учитывать угол, а затем процесс слишком медленный (?).

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

Ответ 3

В один из дней нескольких К оперативной памяти и машин с ограниченными математическими возможностями я использовал таблицы поиска и линейную интерполяцию. Основная идея проста: создайте массив с таким большим разрешением, сколько вам нужно (больше элементов уменьшает ошибку, создаваемую интерполяцией). Затем интерполируйте между значениями поиска.

Вот пример в обработке (оригинальная мертвая ссылка).

Вы можете сделать это и с другими функциями триггера. На процессоре 6502 это позволяло вычислять полную 3D-графику кадра с увеличением скорости на порядок.

Ответ 4

Здесь на SO я до сих пор не имею права комментировать (хотя у меня есть на math.se), поэтому на самом деле это ответ на сообщение Timo по углам алмаза.

Вся концепция алмазных углов, основанная на норме L1, является наиболее интересной, и если это просто сравнение того, какой вектор имеет больший/меньший w.r.t. положительной оси X было бы достаточно. Тем не менее, OP действительно упомянул угол между двумя универсальными векторами, и я полагаю, что OP хочет сравнить его с некоторым допуском для поиска гладкости/углового статуса или sth, как это, но, к сожалению, кажется, что только с формулами, представленными на jsperf.com или freesteel.co.uk(ссылки выше), похоже, это невозможно сделать, используя алмазные углы.

Соблюдайте следующий результат из моей реализации Asymptote формул:

Vectors : 50,20 and -40,40
Angle diff found by acos      : 113.199
Diff of angles found by atan2 : 113.199
Diamond minus diamond         : 1.21429
Convert that to degrees       : 105.255
Rotate same vectors by 30 deg.
Vectors : 33.3013,42.3205 and -54.641,14.641
Angle diff found by acos      : 113.199
Diff of angles found by atan2 : 113.199
Diamond minus diamond         : 1.22904
Convert that to degrees       : 106.546
Rotate same vectors by 30 deg.
Vectors : 7.67949,53.3013 and -54.641,-14.641
Angle diff found by acos      : 113.199
Diff of angles found by atan2 : 113.199
Diamond minus diamond         : 1.33726
Convert that to degrees       : 116.971

Итак, дело в том, что вы не можете делать алмаз (альфа) -диамадон (бета) и сравнивать его с некоторым допуском, в отличие от того, что вы можете сделать с выходом atan2. Если все, что вы хотите сделать, это алмаз (альфа) > алмаз (бета), то я полагаю, что алмаз прекрасен.

Ответ 5

Решение было бы тривиально, если бы векторы были определены/сохранены с использованием полярных координат вместо декартовых координат (или "а также" с использованием декартовых координат ").

Ответ 6

точечное произведение двух векторов (x1, y1) и (x2, y2) есть

x1 * x2 + y1 * y2 

и эквивалентно произведению длин двух векторов, умноженных на косинус угла между ними.

Итак, если вы сначала нормализуете два вектора (разделите координаты на длину)

Where length of V1 L1 = sqrt(x1^2 + y1^2),  
  and length of V2 L2 = sqrt(x2^2 + y2^2),

Тогда нормированные векторы

(x1/L1, y1/L1),  and (x2/L2, y2/L2),  

И точечный продукт нормированных векторов (который совпадает с косинусом угла между векторами) будет

 (x1*x2 + y1*y2)
 -----------------
     (L1*L2)

конечно, это может быть так же сложно вычислить, как вычисление косинуса

Ответ 7

если вам нужно вычислить квадратный корень, тогда рассмотрите использование invsqrt hack.

acos((x1*x2 + y1*y2) * invsqrt((x1*x1+y1*y1)*(x2*x2+y2*y2)));

Ответ 8

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

а именно:

I1Q2-I2Q1 пропорционален углу между I1Q1 и I2Q2.

Ответ 9

dot product может работать в вашем случае. Он не пропорционален углу, но "связанному".