From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Min. distance between two circles in 3D Date: 25 Aug 1997 16:41:45 GMT In article <33FBFE2E.67D@geguri.kjist.ac.kr>, Ilian Bonev wrote: >I am looking for the best algorithm computing the distance between >two circles in 3D space, given their centers, radii, and the lines >passing through the centers of the circles and being perpendicular >to the planes in which the cicles lay. Use the data given to express each circle as the set of points P_i = C_i + V_i cos(theta_i) + W_i sin(theta_i) (i=1 or 2), that is, C_i is the center point of the circle, V_i is a vector from the center to a point, and W_i is another such, perpendicular to V_i. (You can use cross products to get W_i from V_i and the normal to the plane of the circle.) Then you want to minimize the distance d(P_1, P_2) as theta_1 and theta_2 vary over [0,2pi]. It's sufficient to minimize its square, which is the dot product of P_1 - P_2 with itself. Expand, simplify, take the gradient, set equal to zero, and solve for (theta_1, theta_2). Inelegant? Yes, I suppose so, but I didn't see any way to do this synthetically. You can do this much: to find the point of closest approach between a fixed point P and a circle centered at C, let X1 be the plane perpendicular to line PC at C, and let X2 be the plane containing the circle. Let L be the intersection of those two planes (a line, assuming "general position"). Then there is a plane perpendicular to L which passes through both P and C. It meets the circle at two points, one of which ("Q" say) gives the minimal distance (the other gives the maximal distance). So now you need to let P vary over the other circle until you find a point where the situation is symmetric with respect to the two circles; this will give a minimal distance. Unfortunately, I don't see any elegant way to pick out the right P in the first place. (I suppose this qualifies as an iterative method of finding the points of closest approach: pick P at random on one circle and find Q as above. Then reverse roles of the circles and use Q as the fixed point ("P", above) and repeat the process; let P' be the resulting point ("Q" above) found to be closest to Q. Then of course dist(P',Q) is at most equal to dist(P,Q). Now iterate to find sequences of points P, P', P", ... and Q, Q', Q", ... with decreasing separations. The limits of these sequences will be the points of closest approach. But I doubt that this would give a numerically superior method of locating the points than would, say, Newton's method on the numerical problem of solving gradient=0.) dave ============================================================================== From: "Dr.Matthew Kuhn" To: Subject: Min. distance between two circles in 3D Date: Tue, 6 Nov 2001 10:57:55 -0800 (PST) Dave Rusin, I have begun working on a paper "Smooth convex particles for DEM analyses", which presents some new methods for Discrete Element Analysis (sometimes called Molecular Dynamics). Among the many challenges was the problem of finding the distance between two circles in 3D (as part of a torus-torus contact problem). I did a Google search and came across an email message that you had written in 1997 to the sci.math newsgroup. You suggested a wonderful iterative approach to the problem (isn't the internet just amazing!). I used your suggestion and several refinements in an algorithm for the distance problem. The result is very stable. The algorithm is part of a much larger code, but the distance problem is used repeatedly for millions of cases, perhaps hundreds of millions so far. It is incredibly fast. In the paper, I would like to refer to your original suggestion. Have you published it? If not, I could cite your original email message. Matthew Kuhn -- ***************************************************************** * Matthew R. Kuhn phone (503) 943-7361 fax (503) 943-7316 * * Department of Civil and Env. Engineering * * University of Portland * * 5000 N. Willamette Blvd. * * Portland, Oregon 97203 kuhn@up.edu * ***************************************************************** ============================================================================== From: rusin@math.niu.edu To: kuhn@egr.up.edu Subject: Re: Min. distance between two circles in 3D Date: Tue, 6 Nov 2001 20:49:45 -0600 (CST) No, it's not published, except over the web. If you would like to refer to it, I would prefer you cite it as math-atlas.org/97/2circles rather than at math.niu.edu . Interestingly I would give a different answer today; not sure whether it's better -- depends in part on how the data are presented to you. One presentation would be to have the circles presented as the intersections of planes and either cylinders or spheres, that is, each means of a linear and a quadratic equation. If so, then the set of pairs of points on the circles can be expressed as a 6-tuple of numbers (x1,y1,z1,x2,y2,z2) which are constrained by the two linear and two quadratic equations. On that constrained set you are trying to minimize (the square of) the distance, i.e. (x1-x2)^2+(y1-y2)^2+(z1-z2)^2 . Well, that's an absolutely standard Lagrange Multipliers problem: for this function and each of the four constraint polynomials, take derivatives with respect to each of 5 variables. This gives a 5x6 matrix all six of whose 5x5 minors must vanish. Some of them have common factors; extracting those common factors we find a couple of quadratic equations which the coordinates must satisfy in addition to the two linear and two quadratic equations we had before. That's enough equations to locate the points. Indeed, it can easily be shrunk to four quadratic equations in four unknowns, although the algebra gets a little hairy at that point. So it is possible to describe the solution in a completely algebra way, using little geometry and no iteration (except of course to actually solve some polynomial equations). This depends on the circles being presented in a certain way. There are other presentations which might arise, and these might be more easily handled in other ways. For example, if the two circles are parameterized by trig or rational functions, we can reduce things pretty quickly with some algebra. Just to try an example, I picked numbers at random and got something very interesting. I chose one of the circles to be described by x1^2 + y1^2 = 1, z1 = 0 . The other I chose to be described by 2 x2 + 3 y2 + 5 z2 + 7 = 0 x2^2 + y2^2 + z2^2 + 11 x2 + 15 y2 + 17 z2 + 19 = 0 (the latter a sphere whose center does not lie on the plane given). This is "random", right? Well, it's surprisingly subtle! There is a point at about [-4.109, -4.208, 2.768] on that circle, and a point near [.698, .715, 0] on the unit circle which are about 7.418 units apart. That's the furthest pair. There are _two_ local minima: the points [1.167642550, -.8397923181, -1.363181627] and [.8118343546, -.5838878151, 0] are 1.431904504 apart (the absolute minimum) and the points [-.8186810732, .8809588968, -1.601102908] and [-.6807402986, .7325248433, 0] are 1.613874475 apart (a local minimum). (There are also three saddle points in the distance function: the pairs of points are [-4.011566879, -4.293237287, 2.780569124] and [-.6827315784, -.7306692766, 0] [ .2264828613, .2283724396, -1.627616607] and [-.7041632064, -.7100381530, 0] [0.1623470783, .2803956870, -1.633176245] and [ .5010657194, .8654092353, 0] and the distances between the pairs are 5.612895859, 2.096628824, 1.767550793 respectively.) So I repeat: it depends on how the data are given in the first place. Seems to me there are interesting ways to approach this besides the one in that previous post. dave PS - I suppose I will add this message to that file. ============================================================================== From: "Dr.Matthew Kuhn" To: Subject: Re: Min. distance between two circles in 3D Date: Wed, 7 Nov 2001 13:44:25 -0800 (PST) Dave, Thanks for the citation. I've been thinking about the new method, but from a computational point of view, I think that your original iterative method is more attractive. (There are two published methods for the circle-circle problem which are also related.) In applying the iterative method, I have been using a first "guess" of simply the vector that connects the centers of the two circles. Very primative and perhaps vulnerable to certain pathologic cases. I have been using a technique called "Stephensens acceleration", and wow, the convergence has been very fast (I have to do this for millions of cases). On average about 5 trials to a achieve a relative error (ala Cauchy convergence) of only 1e-15. I knew about the two local minima/maxima, as these have some significance in the torus-torus contact problem. But I didn't realize that there are saddle points as well. [deletia --djr] ============================================================================== From: rusin@math.niu.edu To: kuhn@egr.up.edu Subject: Re: Min. distance between two circles in 3D Date: Wed, 7 Nov 2001 16:34:06 -0600 (CST) About the saddles: I realized later this was almost a given. Draw a large circle and a smaller circle crossing it on a sheet of paper. Now imagine the smaller one perturbed a little off the plane of the paper so that there is no intersection. It's clear you have two local minima roughly where the two circles used to cross. There's also an absolute maximum between the two most distant ends of the figure (one on each circle). The line segment joining these is pretty much the union of a diameter of the small circle and a diameter of the large circle. Well, when you compute the distances between (either of the ends of the small circle) and (either of the ends of the large circle), those are saddle points, except for the most distant pairs. So it's obviously 2 minima, 1 maximum, 3 saddles. Duh. I should've guessed. dave