¿Puedo simplificar la desigualdad "distancia (p1, p2) <distancia (p1, p3)?"

14

Estoy trabajando en una lógica vectorial, por lo que pregunto: ¿puedo ahorrar tiempo en el procesador al simplificar esta desigualdad?

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

Veo que vector1se repite en ambos casos.

vector Filip Dimitrovski
fuente
10
Solo una nota rápida: su método actual es muy legible y su función puede entenderse al instante. Algunas de estas respuestas pueden cumplir la tarea que ha solicitado, pero son mucho menos claras. Esto está bien si el rendimiento es esencial, pero asegúrese de comentarlo correctamente para tener en cuenta la pérdida de claridad.
MikeS
3
Para continuar con el comentario de @ MikeS, el rendimiento solo debe ser esencial en casos como este si ya ha realizado análisis o perfiles y ha identificado esta llamada como un cuello de botella. La mantenibilidad supera el rendimiento bruto si hablamos de la diferencia entre 305 fps y 303 fps.
Phoshi

Respuestas:

24

Sí , puedes simplificar esto. Primero, deja de llamarlos vectores. Son puntos. Llamémosles A, By C.

Entonces, quieres esto:

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

Reemplazar distancias con distancias al cuadrado, luego con productos de punto (de la definición de la longitud euclidiana . Reemplazar ACcon AB + BC(ahora estos son vectores reales). Expandir, simplificar, factorizar:

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)

Ahí tienes:

dot(AB + AC, BC) > 0

Con su notación vectorial:

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

Esas son algunas adiciones y un producto de punto en lugar de los dos productos de punto anteriores.

sam hocevar
fuente
¿Puede explicar cómo puede reemplazar a a + b b = a a + c c con la versión del producto dot?
TravisG
2
@TravisG No estoy seguro de lo que está preguntando. Si su pregunta es por qué dist(A, B)²es igual dot(AB, AB), proviene de la definición misma de la longitud euclidiana .
sam hocevar
2
Claramente esto (algo) simplifica matemáticamente la ecuación, pero no necesariamente "ahorrará tiempo de procesador" para el OP. Resulta en más complejidad y más cálculos que simplemente eliminar la raíz cuadrada de las ecuaciones de distancia originales.
MichaelHouse
1
Corríjame si estoy equivocado pero los dos productos de punto son 5 operaciones por producto de punto más las dos sustracciones vec3, que son un total de 16 operaciones, su camino tiene 3 sustracciones vec3 más una suma que hace 12 operaciones más el producto punto hace 17.
Luis W
2
Curiosamente, el resultado es el producto punto de las dos diagonales opuestas de un paralelogramo. Pero eso es irrelevante. Lo que quería decir es que no se puede obtener una gran cantidad de esta simplificación completa ; Como otros han mencionado, hace una cantidad decente para ofuscar o complicar lo que realmente está tratando de calcular. Sin embargo, definitivamente quieres usar el primer paso. Evitar una raíz cuadrada innecesaria siempre vale la pena. Simplemente comparar los cuadrados de las distancias es lo mismo, ya que la distancia es positiva definida, incluso en el plano complejo.
TASagent
16

Si. Suponiendo que su distancefunción usa una raíz cuadrada, puede simplificar esto quitando la raíz cuadrada.

Cuando se trata de encontrar la distancia más grande (o más pequeña), x^2 > y^2sigue siendo válido para x > y.

Sin embargo, otros intentos de simplificar matemáticamente la ecuación probablemente no tengan sentido. La distancia entre vector1y vector2no es la misma que la distancia entre vector1y vector3. Si bien la ecuación se puede simplificar matemáticamente como muestra la respuesta de Sam , la forma en que se encuentra actualmente es tan simple como la que se obtiene desde la perspectiva del uso del procesador.

MichaelHouse
fuente
No tengo suficiente representante, pero creo que, como es fundamentalmente incorrecto, "¿puedo ahorrar tiempo al procesador al simplificar esta desigualdad?" La respuesta es sí.
Estoy tan confundido
La respuesta es solo sí si la ecuación de distancia está usando una raíz cuadrada. Lo cual menciono.
MichaelHouse
Punto válido, retiraría mi declaración. Sin embargo, se garantiza en un 99% que el usuario se refiere a la distancia euclidiana sqrt (suma (diferencias dimensionales al cuadrado))
im tan confuso
@imsoconfused Bastante justo, he cambiado el orden de mi respuesta para indicar primero el escenario más probable (99%).
MichaelHouse
2
Sí, mi experiencia es cuando se trata de este tipo de cosas, una función DistanceSquared es muy útil. Es igual de claro y evita la costosa operación sqrt.
Loren Pechtel
0

Algunas matemáticas podrían ayudar.

Lo que estás tratando de hacer es:

<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

De lo que puede eliminar variables repetidas y agrupar algunas otras. La operación que debe verificar es:

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

Espero eso ayude.

j4nSolo
fuente
-1

La verdadera pregunta parece ser cómo reducir el cálculo para determinar el objeto más cercano.

La optimización de esto a menudo se realiza en los juegos, aunque con todas las optimizaciones debe guiarse por el perfil y, a menudo, no simplifica las cosas.

La forma de evitar cálculos de distancia innecesarios para determinar la cosa más cercana, o todas las cosas dentro de un cierto rango, es usar un índice espacial, por ejemplo, un octree .

Esto solo vale la pena si hay una gran cantidad de objetos. Por solo tres objetos, es poco probable que valga la pena y ciertamente no simplifica el código.

Será
fuente
44
Creo que la pregunta real es bastante sencilla, y esta respuesta no aborda eso. Si desea especular sobre las preguntas más profundas y no expresadas del OP que realmente deberían hacerse como un comentario si no va a responder realmente a la pregunta formulada.
Estoy rechazando esto porque invocar una posible optimización prematura no es una respuesta a un problema donde es explícito optimización no perjudica ni la legibilidad, ni la capacidad de mantenimiento del código, ni alienta prácticas oscuras. Cuando realmente puedes escribir código simple y optimizado, ¿por qué no hacerlo? Ciertamente no hace daño hacerlo, incluso si tiene un plan de nivel superior (ningún desarrollador de juegos rechazará algunos microsegundos adicionales por cuadro, especialmente en consolas).
teodron
@teodron: "Cuando realmente puedes escribir código simple y optimizado, ¿por qué no hacerlo?" - Debido a que OP (y ahora, nosotros) ha pasado una cantidad de tiempo no despreciable optimizando algo que puede no brindarle ningún beneficio.
BlueRaja - Danny Pflughoeft
@ BlueRaja-DannyPflughoeft Estoy de acuerdo con que esto sea menor (por lo tanto, optimización insignificante si se usa para unos pocos cientos de llamadas por cuadro, pero si el factor de magnitud aumenta a miles, las cosas seguramente cambiarán). Sin embargo, todos somos libres de no perder el tiempo tratando de responder / optimizar algo que consideramos no viable. El OP pidió una cosa, la gente asumió que el OP no estaba al tanto de las estrategias de nivel superior y las prácticas de creación de perfiles. Personalmente prefiero hacer tales comentarios en los comentarios, no en las respuestas. Perdón por ser tan detallado :(.
teodron
-3

depende de cuál es la salida de distancia (v1, v2)

Si es un decimal (flotante o doble) sobre un vector, es probable que la distancia al cuadrado sea mucho más rápida

RoughPlace
fuente
55
No veo qué floattiene que ver eso con nada.
MichaelHouse
Me refería a un flotador sobre otro vector que no se explicaba particularmente bien (y creo que lo sabías)
RoughPlace
55
No estaba malentendido intencionalmente. Todavía no estoy seguro de lo que quieres decir. No sé por qué una función de distancia devolvería un vector.
MichaelHouse