Linked Circles in Three Dimensions

[Radical_Initiator]

This may be more suited to Comp. Sci., and it may be fantastically simple, but I'm not seeing it outright.

I'm looking for an algorithm to determine whether two rings (circles, or tori of vanishingly small minor radius and fixed major radius) of equal major radius, R, in a three-dimensional space are "linked", given the radius R and the positions of the ring centers. I want to essentially ensure that the rings created don't link together, which I could probably do quite easily by rotating the rings into spheres and ensuring the spheres don't intersect (which is fairly easy), but I want to allow for the possibility of two rings that are parallel to one another, with only a short distance separating the centers.

I hope that's enough to at least engender more questions, if not to point me in the right direction. I'd draw a picture, but my drawing skills, especially when dealing with perspective, are mediocre at best. Any help you can offer is most appreciated.

[jestingrabbit]

So, your initial condition is having the centres within radius + radius distance (with a bit of thought you can avoid squareroots here). If they're further than that away, nothing else needs doing, they don't link. This is what you already have.

One way to describe the rest of the problem is to have two planes, with particular points on the planes, and radii, specified. Planes are either parallel, intersect in a line, or coincide. If you store your planes as a normal vector, n, and a special value, v, (so that the plane is the set of points \{ x :\ x \cdot n = v\}) then you have a good basis for working out which case you're in: form the augmented matrix composed of the normal vectors as rows, and the augmented vector is just (value1, value2), then solve the system.

In the parallel case, you're done: no collision. In the coincide case, having the centres within radius + radius distance: you're... well, you tell me.

The final case is the tricky one. The distance from the line to the two centres is important: if either centre is too far away, stop, no interesection. Points on the line are describable with one parameter. If a and b are vectors, L = \{ a + tb :\ t\in R\} is a line, and this is the form that the row reduction should spit it out in. You should be able to find values for t, t1, t2 and s1, s2, which correspond to points on the line that are also on the two circles, t1 and t2 on one circle with t1<t2, s1 and s2 on the other with s1<s2. Linking corresponds to s1 < t1 < s2 < t2, or something similar (there's lots of cases here, some are already ruled out (s1 < s2 < t1< t2 etc), but there are plenty of others to think about). Note that s1< t1< t2< s2 is *not* linking. in the sense that the rings can be pulled apart, but it might be linking by some other standard.

No guarantees that this is floating point safe: lots of differences in the row reduction etc.

[mike-l]

Off the top of my head. You could take the planes defined by the rings and find the line of their intersection (If the rings are coplanar then it's just the distance to the distance between the centres that matters. If the rings are parallel but not in the same plane then they don't intersect), then pick one ring and take the 2 points on the line that are exactly a radius away from its centre (If those points don't exist then the rings don't intersect), and see if it's within a radius of the other centre.

Edit: Ninja'd, but slightly different in that JR finds all 4 points and looks at their order, while I find 2 points and see if they are within a radius of the other.

[willaaaaaa]

Here's an outline of a solution I came up with while walking to and from the office bathroom...haven't thought through it rigorously, but it's something to consider:

Find the intersection of the planes of the circles. (If the planes are parallel, then the circles aren't linked and you're done.) If the planes are not parallel, then the intersection is a line. You want to check whether any segment of this line intersects with the interior of both circles. To do so, find the segment of the line that is within circle A, and check whether it intersects with circle B.

EDIT: Oops, looks like I've been beat. Oh well, I'll post anyway in case there are subtle differences.

[jestingrabbit]

Edit: Ninja'd, but slightly different in that JR finds all 4 points and looks at their order, while I find 2 points and see if they are within a radius of the other.

Yeah, yours is the better approach here I think, so long as everything is stable ie safe from floating point weirdness. But that's the real issue imo: its easy to see a way, its hard to be sure that you're stable. Like thousands before you OP, the idea is typically to assume stability until you have reason to suspect otherwise.

[Radical_Initiator]

Much appreciated; I had envisioned using the line of intersection of the ring planes (if it exists), but was not quite clear on how to use it on the trickier cases.

[Qaanol]

With the 2-point method, you need to have one of the points inside the other circle, and the other point outside the other circle.

[mike-l]

With the 2-point method, you need to have one of the points inside the other circle, and the other point outside the other circle.

Quite right. One ring could be 'dipped' inside the other and not be linked.

[SteveG]

You could parametrize the circles and compute an integral, which will be one if the circles are linked, and zero if they are not:

http://en.wikipedia.org/wiki/Linking_number

[mfb]

You could parametrize the circles and compute an integral, which will be one if the circles are linked, and zero if they are not:

http://en.wikipedia.org/wiki/Linking_number

While this was my first idea, too, the methods to analyse the plane are much simpler.

If you have many small circles in a large volume, I would check the distance between the central points first, as this is sufficient to rule out most of the circle pairs.