|
![](/i/fill.gif) |
Slime wrote:
> The best I can do is to square both sides of the test:
>
> distSq < (radius1 + radius2)^2
>
> And then use the fact that (a+b)^2 = a^2 + 2*a*b + b^2 to get:
>
> distSq < radius1Sq + radius2Sq + 2 * radius1 * radius2
>
> And then, since the radii are positive, the right hand side can be changed
> to the following, but the test will now succeed more often than it should:
>
> distSq < radius1Sq + radius2Sq + 2 * max( radius1Sq, radius2Sq )
>
> So now we have a test that doesn't require taking any square roots, but it
> isn't as "tight" as it could be - it will return true sometimes when the
> circles aren't intersecting.
>
> Can this be improved?
If you're that hell-bent on avoiding the square root, it can be
approximated as follows:
Suppose that the most significant non-zero digit of x is in the 2^n
place. Let y = x / 2^(n/2). Now Sqrt(x) is approximately x / y.
Usually this estimated value is greater than the true square root (but
always by less than 45%). However, exact powers of 2 seem to come out
slightly below the true value. (By about 10^-16.) I don't know if that's
a glitch in my test program or what... It shouldn't be insummountable
though.
Post a reply to this message
|
![](/i/fill.gif) |