Если вам не нужен фактический евклидов угол, а что-то, что вы можете использовать в качестве основы для сравнения углов, тогда выбор может быть изменен на геометрию такси, потому что вы можете отказаться от тригонометрии и ее медлительности при ПОДДЕРЖАНИИ ТОЧНОСТИ (или, по крайней мере, с очень незначительной потерей точности, см. ниже).
В основных современных браузерных движках коэффициент ускорения составляет от 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):
Приведенного выше кода достаточно для быстрого сравнения углов, но во многих случаях необходимо преобразовать ромбовидный угол в радианы и наоборот. Если вы, например. имеют некоторый допуск в виде углов в радианах, а затем у вас есть 100000-кратный цикл, в котором этот допуск сравнивается с другими углами, неразумно проводить сравнения с использованием 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) пространстве.
person
Timo Kähkönen
schedule
03.02.2013
