Vitaly Budovski wrote:
Vitaliy Margolen wrote:
Vitaly Budovski wrote:
Vitaliy Margolen wrote: Thanks for the tip. Unfortunately in this instance it will not work as I do in fact query more than a < b. See the nearest function in patch 2.
And what is so special about subtracting one from the other?
A lot actually. As an example with squared distances: a^2 - b^2 <= c^2. If a^2 = 27, b^2 = 16, c^2 = 9, then 27 - 16 <= 9 is false. However, if we use the square root in distance calculations, sqrt(27) - 4 <= 3 is true. As you can see, we get entirely different results.
I didn't really read your code, but answering on above, it's still possible in this case to avoid sqrt. A bit of math: You want to check if a-b <= c. Assuming a>=b (otherwise it's always true), it's equal to: (a-b)^2 <= c^2 is equal to a^2 + b^2 - 2ab <= c^2 is equal to a^2 + b^2 - c^2 <= 2ab is equal to (assuming a^2 + b^2 - c^2 >= 0) (a^2 + b^2 - c^2)^2 <= (2ab)^2 is equal to (a^2 + b^2 - c^2)^2 <= 4 a^2 b^2 so if you store a^2, b^2 and c^2 instead of a, b, c you may compare it using a few integer operations. In C it would look like:
BOOL abccmp(int a2, int b2, int c2) { int tmp = a2+b2-c2; return a2 <= b2 || tmp <= 0 || tmp*tmp <= 4*a2*b2; }
It may be not so easy in a real code, but in most cases it should be possible to use such tricks.
Jacek