For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

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.
I looked out across the river today …
Just Cool Enough for School

Posts: 1375
Joined: Mon Jan 24, 2011 10:39 pm UTC

Re: Linked Circles in Three Dimensions

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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

jestingrabbit

Posts: 5397
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Linked Circles in Three Dimensions

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.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
mike-l

Posts: 2626
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Linked Circles in Three Dimensions

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.
"If you can't control your peanut butter, you can't expect to control your life." - Bill Watterson
willaaaaaa

Posts: 79
Joined: Thu Jun 21, 2012 5:09 pm UTC

Re: Linked Circles in Three Dimensions

mike-l wrote: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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

jestingrabbit

Posts: 5397
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Linked Circles in Three Dimensions

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.
I looked out across the river today …
Just Cool Enough for School

Posts: 1375
Joined: Mon Jan 24, 2011 10:39 pm UTC

Re: Linked Circles in Three Dimensions

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.
Small Government Liberal

Qaanol

Posts: 2399
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Linked Circles in Three Dimensions

Qaanol wrote: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.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
mike-l

Posts: 2626
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Linked Circles in Three Dimensions

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

SteveG

Posts: 28
Joined: Sun Nov 02, 2008 1:31 am UTC

Re: Linked Circles in Three Dimensions

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

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

Posts: 824
Joined: Thu Jan 08, 2009 7:48 pm UTC