Sign in to follow this  
l0k0

Circle Distance and Distance Squared Issue

Recommended Posts

I am in the process of learning collision detection and am currently writing some bounding volumes for 2d applications. So far I have the AABB, OBB, and Bounding Sphere equivalents written in 2D for XNA. Unfortunately, I am having this odd issue in my BC (Bounding Circle) class when trying to compute the distance between the circle and a point. My circles are represented by c and r. c is a Vector2 defining the center point of the circle and r is a scalar float defining the radius of the circle. I know the distance between a point and the closest point on a circle to that point can be found in the following way. You find the distance between the center and the point by subtracting the two vectors and finding the length of the difference. Then, subtracting this distance by the radius. My source code for my DistanceToPoint(Vector2 point) method is shown below. Note, if the point is inside the circle, the distance should be returned as 0.
public float DistanceToPoint(Vector2 point) {
   float dist = (c - point).Length();
   if (dist <= r)
       return 0.0f;
   else
       return dist - r;
}


Now, I'd also like to have a squared version of the same query since the square root operation is pretty expensive and this can speed up some checks. I think this should be done by finding the squared length of the same difference and subtracting this by the squared radius. However, all my tests show my DistanceToPointSquared(Vector2 point) method is not producing the right results. Here is my source code for this method.
public float DistanceToPointSquared(Vector2 point) {
    float sqDist = (c - point).LengthSquared();
    float sqRadius = r * r;
    if (sqDist <= sqRadius)
        return 0.0f;
    else
        return sqDist - sqRadius;
}


If anyone knows what I'm doing wrong it would be greatly appreciated...because I'd really like to get going and try these out in a spatially partitioned scene :). Thank you for your time.

Share this post


Link to post
Share on other sites
You're committing a mathematical error.

The distance between a point and a circle (d) is the difference between the distance of the point and the center of the circle (p - c) and the radius (r).

So d = (p-c) - r;

Now square both sides, so the equation is still valid:

d^2 = (p-c)^2 - 2 * r * (p-c) + r^2;

The square of the distance between the point and the circle d^2 is NOT (p-c)^2 - r^2.

It's (p-c)^2 + r^2 - 2 * r * (p-c). This has the term (p-c) in it, so you'd have to calculate a square root anyway. You might as well use the square root in the first place and save yourself the trouble.

You're trying to avoid sqrt() to save time. That works for some algorithms (like comparing basic distances), but not other algorithms (such as figuring out exact distances based on the difference of other distances), which is what you're doing.

EDIT: sorry, mixed up my notation, but my original point stands.

Share this post


Link to post
Share on other sites
well lets see.
Yout first function returns dist-r.
Lets square that:

(dist-r)^2 = dist^2 - 2*dist*r + r^2

but your second function returns: dist^2 - r^2

Difference!

Are you sure you really need the squared distance from the point to the circle outline?

Share this post


Link to post
Share on other sites
It's not true unfortunately.

If d is the distance from point to the boundary of the circle, and r is the radius of the circle, then d+r is the distance to the center of the circle.

You wish to find d^2. You have done so by computing (d+r)^2 - r^2, which if you work out the math you'll find is d^2 + 2dr + r^2 - r^2 = d^2 + 2dr.

d^2 != d^2 + 2dr


I don't see an easy way around this, because it requires you to know d before you can compute d^2, which defeats the whole purpose.

Share this post


Link to post
Share on other sites
else
return sqDist - sqRadius;

You're assuming that
(dist-r)² == dist² - r²
When it actually is
dist² - 2 dist r + r²
As you could already see, obtaining a squared distance for two points is pretty straightforward, but I don't know of a way to do it as you want without resorting to a square root (directly or indirectly) somewhere.

Share this post


Link to post
Share on other sites
Thank you all for your quick responses. I've since fixed the math and am keeping this function...for now at least.

Some people seem to be wondering why I would use such a function in the first place. In Christer Ericson's Book, Real Time Collision Detection, he demonstrates some source code for doing an intersection test between a Sphere and an AABB. If the squared distance between the AABB center and the sphere center is less than the radius squared, the volumes are intersecting.

However, while the DistanceToPointSquared(Vector2 point) function makes sense in the AABB struct, and saves time over the standard DistanceToPoint(Vector2 point) function (also of the same struct), this is not the case in my Circle struct.

When doing an intersection test between the two it makes much more sense to call the function in the AABB struct and just pass in the center point of the circle.

For some reason, I wanted to make things consistent across all my bounding volumes. However, in this instance, the purpose of this function makes little sense...

Oh well, you live and you learn. Thanks again.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this