Можно ли упростить неравенство «расстояние (p1, p2) <расстояние (p1, p3)?»

Я работаю над некоторой векторной логикой, поэтому спрашиваю: могу ли я сэкономить время процессора, упростив это неравенство:

distance(vector1, vector2) < distance(vector1, vector3)

Я вижу, что vector1это повторяется в обоих случаях.

Да , вы можете упростить это. Во-первых, перестань называть их векторами. Это очки. Давайте назовем их A, Bи C.

Итак, вы хотите это:

dist(A, B) < dist(A, C)

Замените расстояния квадратами расстояний, а затем точечными произведениями (из определения евклидовой длины . Замените ACна AB + BC(теперь это реальные векторы). Разверните, упростите, множите:

dist(A, B)² < dist(A, C)²
dot(AB, AB) < dot(AC, AC)
dot(AB, AB) < dot(AB + BC, AB + BC)
dot(AB, AB) < dot(AB, AB) + dot(BC, BC) + 2 dot(AB, BC)
0 < dot(BC, BC) + 2 dot(AB, BC)
0 < dot(BC + 2 AB, BC)

Вот ты где:

dot(AB + AC, BC) > 0

С вашей векторной нотацией:

dot(v2 - v1 + v3 - v1, v3 - v2) > 0

Это несколько дополнений и один точечный продукт вместо двух предыдущих.

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

При попытке найти большее (или меньшее) расстояние x^2 > y^2все равно остается в силе x > y.

Однако дальнейшие попытки математически упростить уравнение, скорее всего, бессмысленны. Расстояние между vector1и vector2не совпадает с расстоянием между vector1и vector3. Хотя уравнение может быть упрощено математически, как показывает ответ Сэма , форма, в которой оно находится в настоящее время, вероятно, будет такой же простой, как вы получите с точки зрения использования процессора.

Некоторые математики могут помочь.

То, что вы пытаетесь сделать, это:

<v1, v2> < <v1, v3> =>
sqrt((y2-y1)^2+(x2-x1)^2) < sqrt((y3-y1)^2+(x3-x1)^2) =>
y2^2 - 2*y2y1 + y1^2 + x2^2 - 2*x2x1 + x1^2 < y3^2 - 2*y3y1 + y1^2 + x3^2 - 2*x3x1 + x1^2

Из чего можно удалить повторяющиеся переменные и сгруппировать некоторые другие. Операция, которую вы должны проверить:

y3^2 - y2^2 - 2*y1(y3-y2) + x3^2 - x2^2 - 2*x1(x3-x2) > 0

Надеюсь, это поможет.

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

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

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

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

это зависит от того, что вывод расстояния (v1, v2)

если это десятичное число (число с плавающей запятой или двойное число) над вектором, вполне вероятно, что квадрат расстояний будет намного быстрее