Является ли точка A ближайшей точкой B в 3D - проверка расстояния

Question

Я ищу эффективный алгоритм для проверки, находится ли одна точка рядом с другой в 3D.

sqrt((x2-x1)^2 + (y2-y1)^2 + (z2-z1)^2) < radius

Это не кажется слишком быстрым, и на самом деле мне не нужна такая большая точность. Как еще я мог это сделать?

Answer 1

Вычеркните расстояние и отбросьте вызов до sqrt(), это намного быстрее:

(((x2-x1)^2 + (y2-y1)^2 + (z2-z1)^2 < radius * radius

Конечно, во многих случаях по крайней мере radius * radius может быть вычислено заранее и сохранено как, например, squaredRadius.

Answer 2

Что ж, если вы можете довольствоваться расстоянием куба, а не сферическим расстоянием, довольно наивная реализация будет такой:

Math.Abs(x2-x1) < radius && Math.Abs(y2-y1) < radius && Math.Abs(z2-z1) < radius 

Вы можете использовать свои любимые методы оптимизации Math.Abs, если это окажется узким местом.

Я также должен добавить, что если одно из измерений, как правило, отличается меньше, чем другие измерения, то использование этого последнего параметра должно привести к увеличению производительности. Например, если вы в основном имеете дело с объектами на «земле» плоскости x-y, проверьте последнюю ось z, так как вы должны быть в состоянии исключить столкновения ранее, используя проверки x и y.

Answer 3

Если вам не нужна большая точность, возможно, вы можете проверить, находится ли 2-я точка внутри куба (длина стороны '2a'), а не сфера, где 1-я точка находится в центре:

|x2-x1|<a && |y2-y1|<a && |z2-z1|<a

Answer 4

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

Итак, я бы предпочел путь вычисления, а не ответвления.

Answer 5

Если вам нужно сравнить многие другие точки, вы можете рассмотреть возможность использования метода пространственного упорядочения для быстрого обнаружения точек, находящихся рядом с определенным местоположением. Посмотрите на эту ссылку: ссылка на вики

Answer 6

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

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

эта техника также хорошо распространяется на более высокие измерения.

если вы хотите получить все точки рядом с другой, может также подойти некоторая форма пространственной индексации (возможно, kd-tree)

Answer 7

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

close = (abs(x2-x1) < r && abs(y2-y1) < r && abs(z2-z1) < r);

Answer 8

Если бы мы собирались оптимизировать это, потому что он запускался миллиарды раз, я бы решил это, используя метод unwind , и затем распараллеливая его, используя SIMD. Есть несколько разных способов сделать это. Вы можете просто сделать все вычитания (x2-x1, y2-y1, z2-z1) в одной операции, а затем умножить также в одной операции. Таким образом, вы парализуетесь внутри метода, не перепроектируя свой алгоритм.

Или вы можете написать массовую версию, которая вычисляет (x2-x1) ^ 2 + (y2-y1) ^ 2 + (z2-z1) ^ 2 - r ^ 2 для многих элементов и сохраняет результаты в массиве. Возможно, вы получите лучшую пропускную способность, но это означает пересмотр вашего алгоритма и зависит от того, для чего используются тесты.

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

Answer 9

После удаления квадратного корня, если значения становятся больше, лучше применить log.

Answer 10

Используйте максимум (абс (x1-x2), абс (y1-y2), абс (z1-z2))