14
\$\begingroup\$

I am working on some vector logic, so am asking: can I save processor time by simplifying this inequality:

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

I see that vector1 is repeated in both cases.

\$\endgroup\$
  • 10
    \$\begingroup\$ Just a quick note: your current method is very readable and its function can be instantly understood. Some of these answers may accomplish the task you have requested, but are much less clear. This is fine if performance is of the essence, but make sure to comment it properly to account for the loss of clarity. \$\endgroup\$ – MikeS Aug 14 '13 at 17:25
  • 3
    \$\begingroup\$ To continue @MikeS's comment, performance should only be of the essence in cases like this if you have already done analysis or profiling and have identified this call as a bottleneck. Maintainability beats out raw performance if we're talking the difference between 305fps and 303fps. \$\endgroup\$ – Phoshi Aug 14 '13 at 19:55
24
\$\begingroup\$

Yes, you can simplify this. First, stop calling them vectors. They are points. Let’s call them A, B and C.

So, you want this:

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

Replace distances with distances squared, then with dot products (from the definition of the Euclidean length. Replace AC with AB + BC (now these are real vectors). Expand, simplify, factor:

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)

There you are:

dot(AB + AC, BC) > 0

With your vector notation:

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

That’s a few additions and one dot product instead of the previous two dot products.

\$\endgroup\$
  • \$\begingroup\$ Can you explain how you can replace aa + bb = aa + cc with the dot product version? \$\endgroup\$ – TravisG Aug 14 '13 at 16:11
  • 2
    \$\begingroup\$ @TravisG I am not sure of what you are asking. If your question is why dist(A, B)² is the same as dot(AB, AB), it comes from the very definition of the Euclidean length. \$\endgroup\$ – sam hocevar Aug 14 '13 at 16:20
  • 2
    \$\begingroup\$ Clearly this does (somewhat) simplify the equation mathematically, but wouldn't necessarily "save processor time" for the OP. It results in more complexity and more calculations than just removing the square root from the original distance equations. \$\endgroup\$ – MichaelHouse Aug 14 '13 at 17:57
  • 1
    \$\begingroup\$ Correct me if i´m wrong but the two dot-products are 5 operations per dot-product plus the two vec3 substractions which is a total of 16 operations, your way has 3 vec3 substractions plus an Addition which makes 12 operations plus the dot product makes 17. \$\endgroup\$ – Luis W Aug 14 '13 at 18:08
  • 2
    \$\begingroup\$ Interestingly enough, the result is the dot-product of the two opposite diagonals of a parallelogram. But that is irrelevant. What I wanted to say is that there isn't a tremendous amount to be gained from this full simplification; as others have mentioned it does a decent amount to obfuscate or complicate what you're actually trying to calculate. However, you definitely want to use the first step. Avoiding an unnecessary square root is always worth it. Just comparing the Squares of the distances is the same, as distance is positive definite, even in the complex plane. \$\endgroup\$ – TASagent Aug 14 '13 at 18:08
16
\$\begingroup\$

Yes. Assuming your distance function uses a square root, you can simplify this by removing the square root.

When trying to find the larger (or smaller) of a distance, x^2 > y^2 still holds true for x > y.

However, further attempts to simplify the equation mathematically are likely pointless. The distance between vector1 and vector2 is not the same as the distance between vector1 and vector3. While the equation can be simplified mathematically as Sam's answer shows, the form it's currently in is likely as simple as you'll get from the processor usage perspective.

\$\endgroup\$
  • \$\begingroup\$ I don't have enough rep, but I would as it is fundamentally incorrect, I believe: "can I save processor time by simplifying this inequality?" The answer is yes. \$\endgroup\$ – im so confused Aug 14 '13 at 17:59
  • \$\begingroup\$ The answer is only yes if the distance equation is using a square root. Which I mention. \$\endgroup\$ – MichaelHouse Aug 14 '13 at 18:00
  • \$\begingroup\$ Valid point, I'd retract my statement. However, it is 99% guaranteed that the user means euclidean distance sqrt(sum(dimensional differences squared)) \$\endgroup\$ – im so confused Aug 14 '13 at 18:05
  • \$\begingroup\$ @imsoconfused Fair enough, I've changed the order of my answer to state the most likely (99%) scenario first. \$\endgroup\$ – MichaelHouse Aug 14 '13 at 18:15
  • 2
    \$\begingroup\$ Yes, my experience is when you're dealing with this sort of stuff a DistanceSquared function is very useful. It's just as clear and avoids the expensive sqrt operation. \$\endgroup\$ – Loren Pechtel Aug 15 '13 at 0:50
0
\$\begingroup\$

Some maths could help.

What you are trying to do is:

<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

From what you can remove repeated variables and group some others. The operation that you have to check is:

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

Hope it helps.

\$\endgroup\$
-1
\$\begingroup\$

The real question seems to be how to reduce computation for determining the nearest object?

Optimising this is often done in games, although with all optimisations it should be profile-guided and, often, doesn't simplify things.

The way to avoid unnecessary distance computations to determine the nearest thing - or all things within a certain range - is to use a spatial index e.g. an octree.

This only pays off if there are a large number of objects. For just three objects, it is unlikely to pay off and certainly doesn't simplify the code.

\$\endgroup\$
  • 4
    \$\begingroup\$ I think the actual question is fairly straightforward, and this answer doesn't address that. If you wanted to speculate as to the OP's deeper, unstated questions that should really be done as a comment if you aren't going to actually answer the asked question. \$\endgroup\$ – user1430 Aug 14 '13 at 15:53
  • \$\begingroup\$ I am downvoting this because invoking a possible premature optimization is not an answer to a problem where explicit optimization does not hurt either readability, code maintainability, nor does it encourage obscure practices. When you can actually write simple and optimized code, why not do it? It certainly does not hurt to do it, even if you have a higher level plan (no game developer will ever refuse some extra microseconds per frame, esp. on consoles). \$\endgroup\$ – teodron Aug 14 '13 at 17:37
  • \$\begingroup\$ @teodron: "When you can actually write simple and optimized code, why not do it?" - Because OP (and now, us) has now spent a non-negligable amount of time optimizing something which may give him no benefit whatsoever. \$\endgroup\$ – BlueRaja - Danny Pflughoeft Aug 14 '13 at 19:17
  • \$\begingroup\$ @BlueRaja-DannyPflughoeft I agree with this to be a minor (hence insignificant optimization if used for a few hundred calls per frame, but if the factor of magnitude increases to thousands, things surely change). However, we are all free not to waste time trying to answer/optimize something we deem as not viable. The OP asked for one thing, people assumed the OP was not aware of higher level strategies and profiling practices. I personally prefer to make such remarks in comments, not in answers. Sorry for being so verbose :(. \$\endgroup\$ – teodron Aug 15 '13 at 8:18
-3
\$\begingroup\$

it depends on what the output of distance(v1,v2) is

if it is a decimal (float or double) over a vector it is likely that distancesquared would be a lot quicker

\$\endgroup\$
  • 5
    \$\begingroup\$ I don't see what it being a float has to do with anything. \$\endgroup\$ – MichaelHouse Aug 14 '13 at 13:28
  • \$\begingroup\$ i meant a float over another vector just not explained particularly well (and i think you knew that) \$\endgroup\$ – RoughPlace Aug 14 '13 at 14:12
  • 5
    \$\begingroup\$ I wasn't intentionally misunderstanding. I'm still not sure what you mean. I don't know why a distance function would return a vector. \$\endgroup\$ – MichaelHouse Aug 14 '13 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.