> 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