How to tell if two rings (circles in 3d) are linked

Question

I have two rings in 3 space each represented by a normal vector, center coordinate, and a radius. How can I determine if the rings are linked. I.e. a point on one circle lies in the other disk.

This will be implemented in a tight loop so I am concerned about performance. I feel like there should be a closed form solution. So far I've only thought iterative solutions.

Any help?

Answer 1

Outline of the algorithm:

1. Handle the cases where the planes of the circles are parallel or concurrent.
2. Find the line of intersection of the planes of the circles.
3. Find the intersections of the circles with this line.
4. All the circle intersections with the line are on both planes. We can now do distance checks to see if the circles are linked.

Details:

I'll assume that the circles C1 and C2 are given by a center point (p1, p2), unit normal axis vector (n1, n2) and radii (r1, r2).

If n1 == k n2 for some scalar k, then the planes are parallel or concurrent. If they're concurrent this becomes the trivial 2d problem: check whether dist(p1, p2) < r1+r2.

Otherwise, the planes intersect at a line L. If the circles are linked, then they must both intersect L since linking implies that they mutually pass through each other's plane of definition. This gives you your first trivial rejection test.

L is given by a point q and a vector v. Finding v is easy: It's just the cross product of n1 and n2. q is a little trickier, but we can choose a point of nearest approach of the lines

l1(s) = p1 + s (v X n1)
l2(t) = p2 + t (v X n2)

These lines are perpendicular to v, n1 and n2, and are on the planes of C1 and C2. Their points of nearest approach must be on L.

You can refer to this post to see how to find the points of nearest approach.

Finally, the only way the circles can intersect is if they both have points on L. If they do, then consider the intersection points of C1 and L as they relate to C2. The circles are linked if there are two intersection points q11 and q12 of C1 and L and exactly one of them are inside of C2. Since L is on the plane of C2, this becomes a planar point-in-circle test:

IF dist(p1, q11) < r1 THEN
    linked = (dist(p1, q12) > r1)
ELSE
    linked = (dist(p1, q11) < r1)
ENDIF

Of course this pseudo-code is a little sloppy about handling the case that the circles actually intersect, but how that should be handled depends on your application.

Answer 2

A straightforward solution that is relatively easy to code: compute the line of intersection of the two planes and rotate and translate everything (in my case the six points defining the two circles) together so that the line becomes the Z axis (x=y=0). Then the planes can be rotated separately around Z so that the first circle, C1, lies on the XZ plane and C2 lies on the YZ plane. Now the centers and radii are easy to find (in my situation I don't initially have them). These rotations do not change the link/no link property and the link or lack of it can be easily determined from the order of the four intersections of the circles with the Z axis. (If either of the circles does not intersect x=y=0, there is no link.) (I may have confused the axes but I think this will work.) Thank you.