Если вам не нужен фактический эвклидовый угол, но что-то, что вы можете использовать в качестве базы для сопоставлений углов, то выбор геометрии такси может быть выбором, потому что вы можете отказаться от тригонометрии, и это медлительность, ПОДДЕРЖИВАЯ ТОЧНОСТЬ (или, по крайней мере, с действительно незначительным потере точности, см. ниже).
В современных современных браузерах коэффициент ускорения находится в диапазоне от 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):
Приведенный выше код достаточно для быстрого угловыми сравнений, но во многих случаях возникает необходимость преобразовать угол бриллиантом в радианы и вице verca. Если вы, например. имеют некоторый толерант в виде радианских углов, а затем у вас есть цикл 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) пространство.
hmm: important question: являются компонентами векторов, хранящихся в формате с фиксированной или плавающей запятой? –
Ничего. Поскольку координаты, о которых идет речь, являются пиксельными координатами, они всегда являются целыми. Не требуется плавающая точка/фиксированная точка. Итак, я думаю, вы могли бы сказать, что они фиксированные точки с множителем 1 :) – Jeroen