Edward Coffey wrote:
>
>Thanks for the code, that's pretty much the approach I was looking at,
>but hadn't got around to implementing it yet.
>

I said there were probably scenarios that break my code, and I found one.
Take two circles, where the plane containing points C and D and vector M
also contains or very nearly contains vector N.  I.e. N ~= M + a*(D-C),
where a is arbitrary.  The easiest example is if M=N.

Now assume that the distance between C and D is less than (R1+R2), and that
the two circles are in very close parallel planes.  If this is true, then
the first point found by my algorithm, Q1, will lie roughly on a line
between C and D.  But the closest points (two of them) will be where the
circles would intersect if they were in the same plane.

If you moved point Q1 just a degree to the left or right, the algorithm
would eventually get one of the closest points.  But in this example, it
would bounce back and forth between two points on the line between the two
centers.

The only way I can think of to efficiently get around this is to make three
tests.  Start with a point between the centers C and D, and bail out when
the change in the distance is less than 1 part in 10^6 or 10^8 or whatever.

Then try two other starting points, at 90 degree angles to the original
starting point.  The easiest way to find these points would be to find:

Q1 = D-(Nx(Q1-D)) and Q1 = D+(Nx(Q1-D))

in this case, x means cross product.  Since N is a unit vector, the new
vector should still have a length of R2 (should... I haven't tried it yet).

These other two starting points should move much more quickly toward an
answer.

Also, since there can be two closest points, or two almost equally close
points, the original method might find a "local minimum" that is actually
not the minimum, so using this three point approach (or hell, just do the
two 90 degree off-center points, that might be even better) should
guarantee that you get the "most closest" point.

Post a reply to this message