> For 4 dimensions and up, I can visualize [...]

Tell me more. I never quite managed to visualize 4D.

 > [...] that there could be more than one solution.

Already in 3D you can have exactly 2 solutions:
Circle A: center 0, normal y, radius 1
Circle B: center 0, normal z, radius 2


-- 
merge{#local i=-11;#while(i<11)#local
i=i+.1;sphere{<i*(i*i*(.05-i*i*(4e-7*i*i+3e-4))-3)10*sin(i)30>.5}#end
pigment{rgbt 1}interior{media{emission x}}hollow}//  Mark Weyer

Post a reply to this message

My two cents to this topic:

Find a parameterization of the circle in 3D (the one in u and the other in 
v). Then you can formulate the distance between the circles in the two 
unknows u and v: d[u,v] = ... All you have to do then is to minimize this 
function. You can either do this mathematicaly (partial deriviatives in u 
and v have to be 0) or numerically using something like steepest descent. 
The hardest part is to find the general parameterization in 3D.

- Micha


-- 
POV-Ray Objects Collection: http://objects.povworld.org

Post a reply to this message

Some things I can do in 4D, a trick I learned as a child when first
confronted with the possibility.  I read Abbot et al and a couple of other
fascinating stories, then tried the graphing and model constructing.  It seemed
pretty clear after a few days of tinkering.
    The real helper was the N-dimensional packing algorithm for spheres.  It is
closely related to information encoding and how to specify the maximum number of
clearly distinct messages that you can put into a given number of bits (which
relates to the dimensions, n).
    Yes, there are two solutions for the cases that are most easy to see in 3D,
but there are infinitely many cases where there are an infinite number of
solutions (or no solutions) for either or both circles.

Cheers!

Chip Shults
My robotics, space and CGI web page - http://home.cfl.rr.com/aichip

Post a reply to this message

Thanks for the suggestions everyone, looks like I'll just try to 
approximate it.

Post a reply to this message

Edward Coffey wrote:
>Thanks for the suggestions everyone, looks like I'll just try to
>approximate it.
>

You know, this has been bugging me, because it just seems like there's got
to be a way to do it with straight vector math, without resorting to
sin/cos parameterizations and taking partial derivatives (with respect
to each parameter) to find local minima.

The best I've been able to come up with so far is this.

Take two circles, centers at C and D, with respective normals M and N.  Pick
two points, one on each circle, P on circle C, and Q on circle D.

In order for point P to be the closest point on circle C to point Q, the
plane defined by triangle CPQ must contain the normal vector M.  Put
another way, the triple product (is that what it's called?) of (CPxPQ).M
must equal zero.  That is, CP cross PQ is perpendicular to the plan CPQ,
and that vector dotted with the normal M (which is in CPQ) should be zero.

Ditto for (DQxQP).N=0

The only problem is how to find points P and Q.  So far I am still stuck
with parameterizing the circles.  I want something prettier involving the
center, normal, and radius, and maybe some cross products or something...
But I'm still drawing a blank.

But the advantage is, to find an exact solution, you don't need to take the
partial derivatives of the distance function between points P and Q
(i.e. take the partials of an ugly function involving sines, cosines,
and square roots).

You don't need derivatives, you just need to find the matching zeroes of two
vector problems (which reduce to scalars because of the nature of the
triple product).

So I know it's not an equation, but maybe for those still interested in a
better method than trial and error, it's a step in the right direction.
This will continue to bug me for days, so I might be back with more later.

Post a reply to this message

Retsam wrote:
>You know, this has been bugging me, because it just seems like there's got
>to be a way to do it with straight vector math, without resorting to
>sin/cos parameterizations and taking partial derivatives (with respect
>to each parameter) to find local minima.
>
>The best I've been able to come up with so far is this...


Okay, I think I may have a fast and much more accurate approach than most of
the others mentioned.  First of all, it will be a numerical approximation
approach, so no derivatives.

Instead of finding parameterizations of the two circles, and going through
all 360 degrees of both circles and comparing the distances (which leads to
360*360 comparisons), we will simply pick an "arbitrary" point P1 on circle
C, and find the closest point on circle D to that point; call it Q1.  Then
we find the closest point on circle C to Q1, and call that P2.  Repeat
until desired accuracy is found.

So how do we pick our arbitrary point P1.  I say just pick the center, C.
There's a complicated reason why point C is a really good point to start
with.  And yes, I realize that technically it's not on the circle.  Don't
worry, it still works.  The only drawback is it throws off your first
distance measurement, if you care to take it.

Anyway, once we have a point on one circle, to find the closest point on the
other circle to that point, we simply do the following.

Given point P1 (C in this case), find the vector U1 = P1-D.  Assuming N is a
unit normal, make U1 perpendicular to N as follows:
U1 = U1 - N*(U1.N)

But we need U1 to have a length of R2 (we're on circle D), so Q1 = U1 * R2 /
sqrt(U1.U1).  I know, a pesky square root.  in POV-Ray, vlength(U1) =
sqrt(U1.U1).  Oh, and of course, we have to make sure that Q1 is centered
at D, so Q1 = Q1 + D.

Now rinse and repeat :)

//arbitrary circles for testing.
#declare C = <-1, 6, 3>;
#declare Rot1 = <25, 15, 50>;
#declare R1 = 1.2;
#declare M = vrotate(y, Rot1);

#declare D = <6, 3, 4>;
#declare Rot2 = <-55, 0, 30>;
#declare R2 = 1.5;
#declare N = vrotate(y, Rot2);

//Here's the formula itself
#declare Iters=5;
#declare P1 = C;
#while (Iters>0)
  #declare U1 = P1-D;
  #declare U1 = U1 - N*vdot(U1, N);
  #declare Q1 = D + U1 * R2 / vlength(U1);
  #debug concat("Distance is: ", str(vlength(Q1-P1), 5, 9),"\n")

  #declare V1 = Q1-C;
  #declare V1 = V1 - M*vdot(V1, M);
  #declare P1 = C + V1 * R1 / vlength(V1);
  #debug concat("Distance is: ", str(vlength(P1-Q1), 5, 9),"\n")


  #declare Iters = Iters-1;
#end

Notice with the debug messages that three or four iterations should be
plenty, but five or six should give you very, very good accuracy.  In the
sample above, on my machine the accuracy maxes out at 10 significant digits
after the first part of the fifth iteration.

Like any of the formulas, there are probably scenarios that break this
formula, causing divide by zero errors or whatever.  But in general, it is
very, very fast.

Post a reply to this message

>Notice with the debug messages that three or four iterations should be
>plenty, but five or six should give you very, very good accuracy.  In the
>sample above, on my machine the accuracy maxes out at 10 significant digits
>after the first part of the fifth iteration.
>
>Like any of the formulas, there are probably scenarios that break this
>formula, causing divide by zero errors or whatever.  But in general, it is
>very, very fast.
>

Well, some combinations may require ten or fifteen iterations: if the
circles come close to touching, but at very oblique angles.

Post a reply to this message

Retsam wrote:
> Retsam wrote:
> 
>>You know, this has been bugging me, because it just seems like there's got
>>to be a way to do it with straight vector math, without resorting to
>>sin/cos parameterizations and taking partial derivatives (with respect
>>to each parameter) to find local minima.
>>
>>The best I've been able to come up with so far is this...
> 
> 
> 
> Okay, I think I may have a fast and much more accurate approach than most of
> the others mentioned.  First of all, it will be a numerical approximation
> approach, so no derivatives.

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

Post a reply to this message

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

Retsam wrote:
> 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.

Thankfully my circles are very well behaved. They never touch one 
another, never lie in parallel planes and always have exactly one pair 
of closest points.

Post a reply to this message