"Edward Coffey" <eco### [at] alphalinkcomau> wrote in message
news:3E8### [at] alphalinkcomau...

> Yes, but as I stated in my original post, the mathematics of this is
> quite complex, it's not as though you're finding the minimum of a

Does the solution need to be proper math, and does the result have to be
perfect?

For a kludge, IMHO it shouldn't be too hard to write a macro that will return
the two points using a brute force approach. i.e. (approx. code, won't parse)

#declare Len = 10000000000000
#declare R1 = 0
#while (R1 < 360)
    #declare R2 = 0
    #while(R2 < 360)
       #if(distance between R1 on 1st circle and R2 on 2nd circle < Len)
            Len = that distance
        #end
        #declare R2 = R2 +1
    #end
    #declare R1 = R1 + 1
#end

Post a reply to this message

"Tom Melly" <tom### [at] tomandlucouk> wrote in message
news:3e8068ae@news.povray.org...

That should have been (sort of)

        #if(distance between R1 on 1st circle and R2 on 2nd circle < Len)
                BestR1 = R1
                BestR2 = R2
             Len = that distance
         #end

Post a reply to this message

Then you will have cases where you *cannot* find a closest point on the
circumference.  How do you define that case where the circles' planes may be
perpendicular?  There is no solution then for one of the circles, because *all*
points on one will be equidistant to the most extended point on the other.  And
what about coplanar circles with perpendicular centers, such as occurring on a
cone or cylinder?  Then *neither* will have a closest point!
    You can do some simple geometric tests to throw those cases out, then
proceed to construct a truncated conic section that contains the two circles as
limits.  That is, as long as the circles to not intersect!  Now you open a new
can of worms.
    If you have the circles on a single plane, the solution is obvious- draw a
line from center to center as long as they are no concentric.  If they are
non-coplanar and non-intersecting, construct a conic section using the two
circles as caps, and the shortest path on the surface will yield your answer.
    For more than two dimensions, the ways this process can go wrong are
numerous.  For 4 dimensions and up, I can visualize that there could be more
than one solution.  In 3 dimensions, you can always treat any two non-coplanar
planes as you might any two non-colinear lines in a plane.  They will always
have an angle of intersection, which can be seen as being between 0 and 90
degrees.  In some such cases, you might have one closest point on one circle and
*two* closest points on the second- think of one circle passing through the line
of intersection of the two planes.
    This is a mathematically non-trivial problem.

Cheers!

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

Post a reply to this message

On Wed, 26 Mar 2003 01:32:53 +1100, Edward Coffey <eco### [at] alphalinkcomau>
wrote:
> Yes, but as I stated in my original post, the mathematics of this is 
> quite complex

I would go for approximation. If it has to be calculated once you probably can
use approximation as Tom Melly suggested. Otherwise I think there is possible
fast approximation using functions. Consider your circles as toruses with minor
radius = 0. Then construct two functions which represent your circles
  #declare torus1=function(x,y,z){...}
  #declare torus2=function(x,y,z){...}
using transformations and shapes available in IsoCSG library. Then define space:
  #declare space=function(x,y,z){torus1(x,y,z)*torus2(x,y,z)};
I imagine the edge with nearest distance has probably lowest possible values
larger than 0. IIRC there are some analyze methods for finding that path but I
can't recall exact names.

ABX

Post a reply to this message

> Does the solution need to be proper math, and does the result have to be
> perfect?

If approximations suffice, I would go the following way:

1. Choose some point X on circle A
2. Choose some (the) point Y on circle B closest to X
3. Re-choose X to be closest to Y
4. Re-choose Y to be closest to X
5. Continue, until you are happy with the precision.

Caution: This is not yet guaranteed to find the optimum.


-- 
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

> 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