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

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

У меня есть две точки P (x1, y1, z1) и Q (x2, y2, z2), где x, y и z - float/double.

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

square_root (x_diffx_diff + y_diffy_diff + z_diff * z_diff)

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

Вопрос 2:

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

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

Спасибо

Ответ 1

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

Ответ 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;
}

Ответ 3

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

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

Ответ 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] будет заполнен вашим ответом.

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

Ответ 5

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

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

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

Ответ 6

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

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

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

Ответ 7

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

Ответ 8

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

Принимая во внимание, что вы храните точки как float/double, вам может потребоваться сравнение с некоторым epsilon.

Ответ 9

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

Ответ 10

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

Ответ 11

Что касается вопроса 1, то штраф за производительность - это вычисление самого квадратного корня. Формула для вычисления расстояния с использованием квадратного корня парных разностей координат является тем, чем она является.