Эффективный способ определения расстояния между двумя трехмерными точками

Question

Я пишу код на C ++ и хочу вычислить расстояние между двумя точками. Вопрос 1:

У меня есть две точки P (x1, y1, z1) и Q (x2, y2, z2), где x, y и z являются числами с плавающей запятой / двойными числами.

Я хочу найти расстояние между этими двумя точками. Один из способов сделать это:

square_root (x_diff x_diff + y_diff y_diff + z_diff * z_diff)

Но это, вероятно, не самый эффективный способ. (например, лучшая формула или готовая утилита в math.h и т. д.)

Вопрос 2:

Есть ли лучший способ, если я просто хочу определить, являются ли P и Q на самом деле одинаковыми точками?

Мои входные данные - координаты x, y и z обеих точек.

Спасибо

Answer 1

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

Answer 2

Есть ли лучший способ, если я просто хочу определить, являются ли P и Q на самом деле одинаковыми точками?

Тогда просто сравните координаты напрямую!

bool areEqual(const Point& p1, const Point& p2) {
     return fabs(p1.x - p2.x) < EPSILON &&
            fabs(p1.y - p2.y) < EPSILON &&
            fabs(p1.z - p2.z) < EPSILON;
}

Answer 3

Нет, более эффективного способа вычислить расст. Любое лечение в особых случаях p.x == q.x и т. Д. Будет в среднем медленнее.

Да, самый быстрый способ узнать, являются ли p и q одинаковыми точками, - это просто сравнить x, y, z. Поскольку они являются плавающими, вам не следует проверять ==, но следует учитывать некоторую конечную небольшую разницу, которую вы определяете.

Answer 4

Вы можете попробовать использовать расширения SSE.Например, вы можете инициировать два вектора A (x1, y1, z1) и B (x2, y2, z2):

_m128 A = _mm_set_ps(x1, y1, z1, 0.0f)
_m128 B = _mm_set_ps(x2, y2, z2, 0.0f)

Затем вычислить diff с помощью _mm_sub_ps:

__m128 Diff = _mm_sub_ps(A, B)

Следующее вычисление sqr из diff:

__m128 Sqr = __mm_mul_ps(Diff, Diff)

И наконец:

__m128 Sum = add_horizontal(Sqr)
__m128 Res = _mm_sqrt_ss(Sum)

Res [0] будет заполнен вашим ответом.

PS add_horizontal - это место дляоптимизация

Answer 5

Нет, лучшего способа нет.

Реализация square_root может быть оптимизирована.

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

Answer 6

Обратите внимание, что при использовании sqrt(dx*dx+dy*dy+dz*dz) сумма квадратов может быть переполнена. hypot(dx, dy) вычисляет расстояние напрямую без какой-либо вероятности переполнения. Я не уверен в самом скоростном 3d-эквиваленте, но hypot(dx, hypot(dy, dz)) справится с работой и не переполнится.

Answer 7

Вы можете найти эту статью интересной:

http://www.codemaestro.com/reviews/9

Он описывает, как был вычислен квадратный корень в движке Quake 3, утверждая, что на некоторых процессорах он работал в 4 раза быстрее, чем функция sqrt (). Не уверен, что это даст вам прирост производительности в C ++ в наше время - но все же интересно читать

Answer 8

Q2 ответ: x1 = x2 и y1 = y2 и z1 = z2, если точки совпадают.

Учитывая, что вы сохраняете очки как числа с плавающей запятой / двойные, вам может потребоваться сравнение с некоторыми эпсилонами.

Answer 9

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

Answer 10

Есть более быстрые способы получить приблизительное расстояние , но ничего не встроено в стандартные библиотеки. Взгляните на эту статью на FlipCode, которая описывает метод для быстрых 2D-расстояний. По сути, она свернула функцию sqrt в составную линейную функцию, которая может быть быстро вычислена, но не на 100% точна. Тем не менее, на современных машинах в наши дни fpmath довольно быстр, поэтому не оптимизируйте слишком рано, вы можете обнаружить, что у вас все в порядке с простым подходом.