Department of Energy Argonne National Laboratory Office of Science NEWTON's Homepage NEWTON's Homepage
NEWTON, Ask A Scientist!
NEWTON Home Page NEWTON Teachers Visit Our Archives Ask A Question How To Ask A Question Question of the Week Our Expert Scientists Volunteer at NEWTON! Frequently Asked Questions Referencing NEWTON About NEWTON About Ask A Scientist Education At Argonne Circle and Sphere Equation
Name: Daniel
Status: other
Age:  40s
Location: N/A
Country: N/A
Date: N/A 


Question:
I am trying to find an equation for the intersection of a circle and a sphere in 3 space. Here's the situation. I'm working on a computer program for drawing free flowing drapery in real time. I need to compute the 2 points on a plane that passes through the origin that are 1 unit distance from the origin and a second "center" not on the plane. I know the possibilities are that either there is 0, 1 or 2 intersects, but because of the rest of my algorithm I'm guaranteed that there will always be 2 intersections.

I've conceived the problem in 2 different ways. First I thought of the intersects as being the intersection of a unit radius circle on my plane and sphere around the center not on my plane. I solves for x,y and z in my plane and substituted these into a sphere at the origin to give me a formula for the circle on the plane. Then I'd solve for the x,y and zs of the sphere and substitute them into the circle. When I did so the algebra blew up into a horrendous problem with no solution in sight.

I also conceived of the problem as 2 unit radius spheres, one at the origin one at the other center that intersect in a circle, then this circle is intersected by my plane. It also became very cumbersome.

I know I could probably solve this if I rotate my centers into alignment with my 3D space, then rotate it back when I'm finished. I'm avoiding this solution as being to slow or inefficient to get the job done for a real time program. I need to solve this for thousands of points in a tiny fraction of second. That's why I'm hoping to find a straight forward formula for the x, y and z of the 2 intercepts. Any ideas?



Replies:
Well, this is a very interesting question, and I am inclined to spend a lot more time working on it than I ought to. Given that you're a computer programmer and I'm a scientist, you're probably paid a lot more than I am. However, I know from my own programming experience that the actual mathematical guts of a program take up only about 5% of the programming work, and the remaining 95% of the effort goes into I/O. So I'll give you an idea of how I'd address the problem, and leave it to you to work it out.

What you have is a fairly simple geometric problem made fairly opaque by its representation in Cartesian coordinates. You're trying to figure out the problem in the language of algebra, which is how you will eventually need to communicate it to your computer. But first, it would be best for you to think of it in terms of shapes, distances, and spaces, which is, after all, how you eventually want your computer to communicate it back to its user.

You are trying to avoid rotating the coordinates into alignment, because you think that transforming coordinates may be too computation intensive. True, transforming coordinates can be slow, especially if you have many different coordinate systems to address (one for each point, I imagine). But in this case you don't need to use trigonometric or exponential functions, which are the real hogs of CPU time, and in fact you won't actually need to transform coordinates in the code at all. You may still, however, be served well by at least thinking in terms of transformed coordinates when you set up your formulas.

Your system is fairly simple. (However, you might want to sketch along on a piece of paper to follow the discussion, as I'm not including pictures in my explanation.) You have two points in 3-space, A and B, and a plane that passes through A, but not through B. Around both A and B are spheres of unit radius. You already know that the distance |AB| < 2 (otherwise their spheres wouldn't intersect), and that the plane passes through the circle of intersection between these two spheres. (Here I am denoting the length of vector x as |x|.) You want to find the coordinates of the two points of intersection between the plane and this circle.

My recommendation is to first find the circle of intersection between the plane and the sphere around point B. (Don't panic! You don't need to write an x-y equation for it!) The first thing to do is express the vector between points A and B as a sum of two vectors, one of which is in the plane of your problem, and the other of which is orthogonal to the plane. (Bear with me, it will eventually become clear why I am doing this.) The vector in the plane points from point A to point B', which is the point in the plane nearest to point B. (Point B' is the projection of point B onto the plane; vector AB' is the projection of vector AB onto the plane.)

You can find the vector B'B by first finding the unit vector perpendicular to the plane, k. If you have expressed the plane as an equation ax + by + cz = d, then a (non-unit) vector perpendicular to this plane is (a,b,c). The unit vector then is k = (a,b,c)/|(a,b,c)|. Once you have k, it is very simple to find the vector B'B: it is B'B = (k dot AB)k, where "x dot y" denotes the inner (dot) product between vectors x and y, e.g., (x1,x2,x3)dot(y1,y2,y3) = x1y1 + x2y2 + x3y3. (This is a very simple mathematical operation!)

Once you have vector B'B, all you must do to find AB' is subtract it from AB. Thus, AB' = AB - B'B.

The shortest distance between point B and the plane is the length of the vector B'B. Point B' is the center of the circle defined by the intersection between the plane and the sphere about B. The radius r of this circle can be found by the Pythagorean Theorem: |B'B|^2 + r^2 = 1. (You can use this formula because the vectors AB' and B'B are perpendicular.)

Now your problem consists of two points in a plane, A and B', a circle of radius 1 about A, and a circle of radius r about B'. You want to find the points of intersection between these two circles. This problem reduces to finding the position of the third vertex of a triangle in which one side is vector AB', with length |AB'|, and the other two sides have lengths 1 and r.

To get this in a manner that makes sense, it is wise to define a new coordinate system. RELAX! This won't be very computation intensive. You want your coordinate system to be such that point A lies at (0,0) and point B' lies at (a,0), where a = |AB'|, the distance from A to B'. This means that the x-axis goes along the vector AB'. The y-axis of your new coordinates must be perpendicular to the x-axis, and must fall within the plane that defines your problem. Thus, the x and y axes of this coordinate system define the plane or your problem.

It will be computationally easiest if you find the orthonormal basis vectors i and j of this coordinate system. In the new coordinates, they are simply i = (1,0) and j = (0,1). In the old coordinates, they are i = AB'/|AB'|, and j must be defined as the unit vector perpendicular to i that falls within the plane of your problem. This is easy to find. It is just the cross product of vectors i and k (recall that k is the unit vector perpendicular to your plane): j = k x i. (The "x" here denotes vector cross product, not the letter x. Everywhere else in this discussion it is the letter x.)

Why did I have you find i and j? Because you will use them to convert answers from the simple coordinate system into the original one. In the new, simple coordinate system, your geometry problem is this: Find the two points of intersection between the circle of radius 1 about (0,0) and the circle of radius r about (a,0). This is done by solving the two simultaneous equations

x^2 + y^2 = 1 and
(a-x)^2 + y^2 = r^2

which gives the easy answers of x = 0.5*(a + (1 - r^2)/a) and y^2 = 1 - x^2. (We are operating in these transformed coordinates so that this algebra is easy.) The points of intersection are A + ix + jy and A + ix - jy. This is true in both coordinate systems. So, without thinking any more about converting between coordinates, you can just apply these formulas to get the points you need. The unit vectors i and j will have fewer zeroes in their components in the original coordinate system, but that will be no trouble at all for your computer. You should also be happy to know that the toughest mathematical operation you need to use is a square root.

If this doesn't answer your question, or if it's not clear to you, ask again if you want.

Richard E. Barrans Jr., Ph.D.
Assistant Director
PG Research Foundation, Darien, Illinois



Click here to return to the Mathematics Archives

NEWTON is an electronic community for Science, Math, and Computer Science K-12 Educators, sponsored and operated by Argonne National Laboratory's Educational Programs, Andrew Skipor, Ph.D., Head of Educational Programs.

For assistance with NEWTON contact a System Operator (help@newton.dep.anl.gov), or at Argonne's Educational Programs

NEWTON AND ASK A SCIENTIST
Educational Programs
Building 360
9700 S. Cass Ave.
Argonne, Illinois
60439-4845, USA
Update: June 2012
Weclome To Newton

Argonne National Laboratory