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

> Have you tried this condition?
>
> ((distSq < (radius1Sq+radius2Sq))
> or (4*radius1Sq*radius2Sq > (distSq - (radius1Sq+radius2Sq))^2))

Smart. I feel stupid now! =) I see the equivalence, but I'm curious how long 
you took to come up with that. Was it obvious?

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

Post a reply to this message

> How about more simply:
>
> distSq < 4 * max( radius1Sq, radius2Sq )
>
> Followed by the expensive square root operation to check if they really 
> intersect?

Well, I'd have to weigh the cost of doing the square root against the cost 
of just going forward and doing the more expensive test. Although I posed 
this as a stand-alone question, the actual work I am doing is checking if a 
line segment intersects a triangle.

There's probably a bunch of ways to make my code faster, but I became 
curious about this particular problem.

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

Post a reply to this message

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

Is there a way to quickly get n for a given number?

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

Post a reply to this message