Puis-je simplifier l'inégalité «distance (p1, p2) <distance (p1, p3)?»

Je travaille sur une logique vectorielle, alors je demande: puis-je gagner du temps au processeur en simplifiant cette inégalité:

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

Je vois que cela vector1se répète dans les deux cas.

Oui , vous pouvez simplifier cela. Tout d'abord, arrêtez de les appeler vecteurs. Ce sont des points. Appelons-les A, Bet C.

Donc, vous voulez ceci:

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

Remplacez les distances par des distances au carré, puis par des produits scalaires (à partir de la définition de la longueur euclidienne . Remplacez ACpar AB + BC(maintenant ce sont de vrais vecteurs). Développez, simplifiez, factorisez:

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)

Te voilà:

dot(AB + AC, BC) > 0

Avec votre notation vectorielle:

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

C'est quelques ajouts et un produit scalaire au lieu des deux précédents produits scalaires.

Oui. En supposant que votre distancefonction utilise une racine carrée, vous pouvez simplifier cela en supprimant la racine carrée.

Lorsque vous essayez de trouver la plus grande (ou la plus petite) distance, cela x^2 > y^2vaut toujours pour x > y.

Cependant, de nouvelles tentatives de simplification mathématique de l'équation sont probablement inutiles. La distance entre vector1et vector2n'est pas la même que la distance entre vector1et vector3. Bien que l'équation puisse être simplifiée mathématiquement comme le montre la réponse de Sam , la forme dans laquelle elle se trouve actuellement est probablement aussi simple que celle que vous obtiendrez du point de vue de l'utilisation du processeur.

Quelques maths pourraient aider.

Ce que vous essayez de faire, c'est:

<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 ce que vous pouvez supprimer les variables répétées et en regrouper d'autres. L'opération que vous devez vérifier est:

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

J'espère que cela aide.

La vraie question semble être de savoir comment réduire le calcul pour déterminer l'objet le plus proche?

L'optimisation est souvent effectuée dans les jeux, bien qu'avec toutes les optimisations, elle devrait être guidée par le profil et, souvent, ne simplifie pas les choses.

La façon d'éviter les calculs de distance inutiles pour déterminer la chose la plus proche - ou toutes les choses dans une certaine plage - est d'utiliser un index spatial, par exemple un octree .

Cela ne vaut que s'il y a un grand nombre d'objets. Pour seulement trois objets, il est peu probable que cela rapporte et ne simplifie certainement pas le code.

cela dépend de la sortie de la distance (v1, v2)

s'il s'agit d'une décimale (float ou double) sur un vecteur, il est probable que les distances au carré soient beaucoup plus rapides