This is a problem that comes up once in a while. I'm curious if anyone knows 
a good solution.

You have two objects and circles that bound them. For each circle, you know 
its position and its radius squared. (You don't have the radius unless you 
take the square root, which is undesirable because it's slow, and caching it 
isn't a good option.) You want to know if these circles intersect.

Obviously, it's easy to get the distance between the circle's centers 
squared. What you want to test is whether dist < radius1 + radius2, but all 
you have is distSq, radius1Sq, and radius2Sq.

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?

 - Slime
 [ http://www.slimeland.com/ ]

Post a reply to this message

If you're willing to tolerate an intersection function which has the 
possibility of error, it seems like just using bounding squares instead 
of bounding circles would give better error bounds if you expect your 
circles to often be of very different sizes.

With regard to the actual question you asked, I can't think of a good 
way without square roots off of the top of my head, but if you're 
willing to tolerate a bit of approximation error then computing them 
needn't be slow:

http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Approximations_that_depend_on_IEEE_representation

Post a reply to this message

> 
> 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?
> 
>  - Slime
>  [ http://www.slimeland.com/ ] 
> 
> 

If the loose test indicates possible intersection then perform the more 
expensive exact test using Sqrt().  If you can eliminate the majority of 
cases cheaply then the higher cost is amortised.

In a similar case but where I have radius1, radius2 I do the following 
to reduce the number of cases requiring more arithmetic operations:

float rSum = radius1 + radius2;

float xDiff = x1 - x2;
if (xDiff > rSum) return false;

float yDiff = y1 - y2;
if (yDiff > rSum) return false;

if (xDiff + yDiff) < rSum return true;

return (xDiff * xDiff + yDiff * yDiff < rSum * rsum)

Sqrt() isn't needed at all but of course this is a different scenario to 
yours.

As always, you would need to measure the performance of different 
schemes on your actual data and processor.  Too many condition tests and 
intermediate operations can end up being more expensive than Sqrt() 
given modern FP capabilities.

Post a reply to this message

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

> 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?

How about more simply:

distSq < 4 * max( radius1Sq, radius2Sq )

Followed by the expensive square root operation to check if they really 
intersect?

Obviously the benefits will depend on many factors, like how similarly sized 
your circles are, and what % of them intersect.

Is there any history to the comparisons that you could make use of?  Eg a 
large number of circles that are being repeatedly tested for intersection 
after they move a small amount?  If so you can get much bigger speed-ups 
using other methods (eg keeping the list of circles ordered by x 
coordinate).

Post a reply to this message

scott wrote:

> Obviously the benefits will depend on many factors, like how similarly 
> sized your circles are, and what % of them intersect.

I would imagine it's quite possible that the extra time required to 
perform a square root operation is more than made up for by the decrease 
in unecessary work due to false intersections. Square root isn't *that* 
slow... But you'd have to measure it to find out for sure.

Post a reply to this message

On 12/10/2009 04:34 AM, Slime wrote:

> 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?
>

Have you tried this condition?

((distSq < (radius1Sq+radius2Sq))
or (4*radius1Sq*radius2Sq > (distSq - (radius1Sq+radius2Sq))^2))

Post a reply to this message

I wrote a small bit of code to test what the speed of the various 
approximation methods was.  The code was complied with g++ and the times 
given for each method are for 100000000 calls to the function.  First, 
the functions I tested:

// Naive method
inline bool isect1(double aSq, double bSq, double dSq) {
     return sqrt(dSq) < sqrt(aSq) + sqrt(bSq);
}

// Slime's approximate method
inline bool isect2(double aSq, double bSq, double dSq) {
     return dSq < aSq + bSq + 2*std::max(aSq,bSq);
}

// Suggested by bart, but with a bugfix.
// Avoids a sqrt, but uses a few multiplies
inline bool isect3(double aSq, double bSq, double dSq) {
     double t1 = aSq+bSq;
     double t2 = dSq - t1
     return (dSq < t1) || (4*aSq*bSq > t2*t2);
}

// Naive method using a fast approximate sqrt
inline bool isect4(double aSq, double bSq, double dSq) {
     return fastSqrt(dSq) < fastSqrt(aSq) + fastSqrt(bSq);
}

and now the times under various optimization levels:


---------- O0
time for isect1 = 9.66935
time for isect2 = 2.03143
time for isect3 = 2.18224
time for isect4 = 7.03525

---------- O1
time for isect1 = 5.13777
time for isect2 = 0.413757
time for isect3 = 0.413756
time for isect4 = 0.0376559

---------- O2
time for isect1 = 0.564358
time for isect2 = 0.276049
time for isect3 = 0.305847
time for isect4 = 0.0381372

---------- O3
time for isect1 = 0.564529
time for isect2 = 0.159936
time for isect3 = 0.206905
time for isect4 = 0.0376384


It looks like my initial suggestion implemented in isect4 is the fastest 
when you have optimization turned on, by a margin which rather surprises 
me.  It takes about as long as simply computing the incorrect formula 
'dSq < aSq + bSq', which seems almost impossibly fast.  Nevertheless 
I've checked the results and it seems to work pretty well despite the 
approximation in the sqrt call.  If you don't want to live with the 
approximation, however, bart's method seems to be the best choice.

Post a reply to this message

Kevin Wampler wrote:
> // Suggested by bart, but with a bugfix.

On second glance, the bug was in how I read his math, and his equation 
was entirely correct.

Post a reply to this message

Kevin Wampler wrote:

> I wrote a small bit of code to test what the speed of the various
> approximation methods was.  The code was complied with g++ and the times
> given for each method are for 100000000 calls to the function.  First,
> the functions I tested:
> 
> // Naive method
> inline bool isect1(double aSq, double bSq, double dSq) {
>      return sqrt(dSq) < sqrt(aSq) + sqrt(bSq);
> }
> 
> // Slime's approximate method
> inline bool isect2(double aSq, double bSq, double dSq) {
>      return dSq < aSq + bSq + 2*std::max(aSq,bSq);
> }
> 
> // Suggested by bart, but with a bugfix.
> // Avoids a sqrt, but uses a few multiplies
> inline bool isect3(double aSq, double bSq, double dSq) {
>      double t1 = aSq+bSq;
>      double t2 = dSq - t1
>      return (dSq < t1) || (4*aSq*bSq > t2*t2);
> }
> 
> // Naive method using a fast approximate sqrt
> inline bool isect4(double aSq, double bSq, double dSq) {
>      return fastSqrt(dSq) < fastSqrt(aSq) + fastSqrt(bSq);
> }
> 
> and now the times under various optimization levels:
> 
> 
> ---------- O0
> time for isect1 = 9.66935
> time for isect2 = 2.03143
> time for isect3 = 2.18224
> time for isect4 = 7.03525
> 
> ---------- O1
> time for isect1 = 5.13777
> time for isect2 = 0.413757
> time for isect3 = 0.413756
> time for isect4 = 0.0376559
> 
> ---------- O2
> time for isect1 = 0.564358
> time for isect2 = 0.276049
> time for isect3 = 0.305847
> time for isect4 = 0.0381372
> 
> ---------- O3
> time for isect1 = 0.564529
> time for isect2 = 0.159936
> time for isect3 = 0.206905
> time for isect4 = 0.0376384
> 
> 
> It looks like my initial suggestion implemented in isect4 is the fastest
> when you have optimization turned on, by a margin which rather surprises
> me.  It takes about as long as simply computing the incorrect formula
> 'dSq < aSq + bSq', which seems almost impossibly fast.  Nevertheless
> I've checked the results and it seems to work pretty well despite the
> approximation in the sqrt call.  If you don't want to live with the
> approximation, however, bart's method seems to be the best choice.

How are you doing the "run 100000000 times" part?

The compiler may be optimizing knowing you're runing it on the same input 
values each time. For example, only calling sqrt() 3 times and not 
300000000.

Post a reply to this message