Самый эффективный способ проверить, параллельны ли два вектора

Question

Учитывая два вектора u=(ux,uy,uz) и v=(vx,vy,vz),, какой вычислительно самый дешевый способ проверить, параллельны ли они или почти параллельны (учитывая некоторое пороговое значение для аппроксимации), предполагая, что векторы не нормированы?

Относительно почти параллели: например, мы принимаем порог с точностью до первой десятичной части, например, если их перекрестное произведение равно 0.01, мы можем смело предположить, что они параллельны. Мы можем аналогичным образом ослабить условие для других методов, которые мы можем захотеть использовать.

Если для ответа предпочтительнее придерживаться языка программирования, давайте предположим, что мы хотим сделать это на c ++.

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

Answer 1

Я думаю, что это неправильно

скаляр = l1 * l2 * cos (r) = ux * vx + uy * vy + uz * vz скаляр ^ 2 = (l1 * l2 * cos (r)) ^ 2 = (ux * vx + uy * vy + uz * vz) ^ 2

(l1 * l2) ^ 2 = (ux * ux + uy * uy + uz * uz) * (vx * vx + vy * vy + vz * vz) так cos (x) ^ 2 = скалярный ^ 2 / (ux * ux + uy * uy + uz * uz) * (vx * vx + vy * vy + vz * vz) = (ux * vx + uy * vy + uz * vz) ^ 2 / (ux * ux + uy * uy + uz * uz) * (vx * vx + vy * vy + vz * vz)

x около 0 или 180, когда cos равно 1 или -1, поэтому cos (x) ^ 2 -> 1

когда это

Формила около 1

(ux * vx + uy * vy + uz * vz) ^ 2 / (ux * ux + uy * uy + uz * uz) * (vx * vx + vy * vy + vz * vz) это означает, что векторы равны

Answer 2

Краткий ответ: Теоретически это не имеет значения. Практически: измерить

Длинный ответ:

Соглашаясь с тем, что об обратных тригонометрических функциях не может быть и речи, давайте сравним наиболее эффективные способы вычисления последних двух вариантов.

Вычисление их перекрестного произведения

Поскольку вы допускаете, чтобы векторы были почти параллельными, вам необходимо вычислить

crossx := uy * vz + uz * vy;
crossy := ...;
crossz := ...;
crossNorm = crossx * crossx + crossy * crossy + crossz * crossz;

, который включает в себя 9 умножений и 5 сложений. Если векторы (почти) параллельны, тогда crossNorm должен быть (почти) нулем.

Однако, как правильно заметил Baum mit Augen , достаточно проверить, что crossx, crossy и crossz почти равны нулю, уменьшив это до 6 умножений и 3 сложений, при за счет еще двух сравнений. Что является более эффективным, зависит от деталей вашего языка и определения «почти» равных & ndash; например если «почти равно» означает, что fabs(...) < 1E-6 может стоить сделать это только один раз.

Расчет скалярного произведения

Скалярное произведение

scalar = ux * vx + uy * vy + uz * vz;

Если векторы (почти) параллельны, тогда

scalar * scalar

должно (почти) равняться

(ux * ux + uy * uy + uz * uz) * (vx * vx + vy * vy + vz * vz).

Это сводится к 10 умножениям и 6 сложениям.

Нормализация их и проверка, является ли их скалярное произведение единицей.

Это только вышеприведенный расчет, но с двумя дополнительными double делениями. Это не добавляет никакой ценности, фактически может привести к проблемам с округлением.

Заключение

Количество двойных операций практически одинаково для обоих вариантов. Если вы действительно хотите знать, вы можете сравнить сборку https://godbolt.org/z/nJ9CXl, но разница будет минимальной для всех практических целей. На самом деле, если считать только «дорогие» инструкции (mulsd, addsd, subsd) и сравнения (ucomisd), оба варианта имеют пять из них. Однако, опять же, если вы должны точно знать , измерьте его!