![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>
> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/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) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |