3

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?

Jacob
  • 1,423
  • 16
  • 29
  • "A point on one circle lies in the other disk" is not enough to conclude the rings are linked. Consider for example two (non-linked) finger rings of equals size. You can put one "side" of one of the rings a bit through the disk spanned by the other one. But the rings are still non-linked. As another example, two concentric co-planar circles of unequal sizes are not linked; however, the disk of the larger one contains all of the smaller one. – Jeppe Stig Nielsen Jul 28 '16 at 15:44

4 Answers4

3

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.

Community
  • 1
  • 1
Codie CodeMonkey
  • 7,669
  • 2
  • 29
  • 45
1

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.

Stephen B Gray
  • 11
  • 3
1

Is this the 3D circle-disk intersection problem? Or, is it the circle-circle intersection problem?

If it's the former, there is a fast, closed form algorithm. First, weed out the circles-too-distant case: dist(CIR1.c, CIR2.c) > CIR1.r + CIR2.r

Handle the edge case: coplanar circles.

Extrude the disk into its plane, then intersect the circle with this plane. If there are 1 or 2 intersection points, test to see if they meet pointInDisk(p, CIR) logic. Report out any surviving intersection points.

Nathan Tuggy
  • 2,237
  • 27
  • 30
  • 38
pbierre
  • 276
  • 1
  • 8
0

A computational geometry textbook might have a good solution!

But I don't have a computation geometry textbook handy at the moment. If I were going to roll my own right now, based on my own (very limited) intuition, I think I'd start with 3d axis-aligned bounding boxes.

e.g., create an "just inside the circle" bounding box, as well as a "just outside the circle" bounding box. I believe it's trivial to figure out if two axis-aligned boxes overlap (section 2.1 of a homework assignment I once did talks about a related problem in the 2D situation --- finding the nearest rectangle to a point: http://juliusdavies.ca/uvic/report.html ).

I suspect the following assertions would hold (but I could be wrong):

  • If the inner-boxes overlap, then the rings are definitely connected. (I now think this is wrong...)

  • If the outer-boxes DO NOT overlap, then they are definitely not connected --- I am very confident this assertion holds! :-) :-)

  • If the outer-boxes overlap, but the inner-boxes do not, then they might be connected.

That's where I'd start, if I were rolling my own.

Conclusion: uhhh, I hope you have better luck with the other answers. :-)

Julius Musseau
  • 4,037
  • 23
  • 27