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