Sir Charles W. Shults III wrote:
>     To find the closest points on any pair of circles, simply draw a line from
> center to center.  Then locate the points on each circle that the line passes
> through.

This only works when both your circles are sitting on the same plane, 
not when they may take any orientation in 3D space.

Post a reply to this message

ABX wrote:
> No. Being in 2D consider circle located at <0,0> with radius 2 and circle
> located at <3,0> with the same radius 2. Closest points between circles are
> located in intersections which are not between centers.
> 
> ABX

Quite so, and furthermore my circles are not in 2D space, they are in 3D 
space. However I'm happy enough not to consider cases where they 
intersect one another.

Post a reply to this message

On Wed, 26 Mar 2003 01:14:02 +1100, Edward Coffey <eco### [at] alphalinkcomau>
wrote:
> This only works when both your circles are sitting on the same plane, 
> not when they may take any orientation in 3D space.

You have to define distance as function and then find where it has minimum.

http://mathworld.wolfram.com/Minimum.html

ABX

Post a reply to this message

Edward Coffey wrote:
...
> Does anyone possess a macro for calculating the points defining the 
> shortest path between two circles (not discs, circles)
...

Sorry, I should have been more clear - when I specified that I was 
dealing with circles not discs I did not mean to imply that I was 
working in a 2D space, only that the path had to connect to the 
circumference, not to any point within a disc.
My circles exist in 3D space and may take any position or orientation 
relative to one another.

Post a reply to this message

ABX wrote:
...
> You have to define distance as function and then find where it has minimum.
...

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 
quadratic equation with one variable. Certainly the mathematics of it is 
quite beyond my abilities, which is why I haven't asked anyone to solve 
it, simply that if they happen to have access to a solution (or if 
they're math mad and really want to create their own solution) to post 
it here.

Post a reply to this message

"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