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

Question

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

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

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

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

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

2

c++computation-theory geometry vector

Решение

Другие решения

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

скаляр = 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)

х около 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)
это означает, что векторы равны

0

Источник

Accepted Answer

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

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

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

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

Так как вы позволяете векторам быть около параллельно нужно вычислять

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

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

Однако, как правильно отмечено Баум мит Ауген, достаточно проверить, что crossx, crossy а также crossz почти равны нулю, сокращая это до 6 умножений и 3 сложений, за счет еще двух сравнений. Что является более эффективным, зависит от деталей вашего языка и определения «почти» равных — например, если почти равен означает, что 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) оба варианта имеют пять из них. Однако, опять же, если вы должны знать именно так, измерить это!

5