How to determine if two cones with vertices at origin, intersect?

Suppose I have two different sets of data points in 3d, that each are in a different tilted plane (different theta,phi,r of normal). I manage to find the enclosing circle for each of these sets of points (center and radius). Now imagine a solid angle (cone) with the vertex at origin and base at the enclosing circle. So I have two cones that have different heights, and their middle axis is at a different theta and phi. Now how can I figure out if these cones have any overlap (intersection) or not? And also if they are not overlapping how close are they, this is rather complicated to define and I still haven't figured out a suitable proximity measure. But maybe you guys out there have some ideas?

[Cedric]

EDIT: discard this comment; I wrote it before realizing that your cones have both their tip at the origin.

You will probably find a lib. that does it, but if you had to do it "by hand".. you could start by computing the distance between the axes of both cones. This is done by computing the scalar product between a vector made of two arbitrary points from the two axes respectively and a unit vector orthogonal to the two axes. You get the latter by normalizing the cross product between two arbitrary directional vectors defining the two axes.

It would not be too complicated then to find radii of both solid angles at closest locations between the two axes. However, what you call "overlapping" is vague. If the two cones have an intersect, its geometry will be quite complicated.

Answer 1

[Sven]

Hi again Doc,

First thing you can do is check the dot product between the normal vectors of both cones' planes. If the dot product is less than zero, the cones cannot intersect. If the dot product is one, then the cones must intersect.

An easier way to think about "nice" 3D shapes (like cones) is to ask if it can project to 2D. In this case, happily the problem can be reduced to 2D.

You've got two "plane normal vectors" that intersect at the origin. This means they are co-planar. If you find this plane (which is straight forward with a couple of cross products), then project the outline of the cones onto this plane, you've reduced the problem down to a question of "does triangle A intersect triangle B".

Or, more simply:

• Get the "apex angle" of each cone/triangle from its normal vector
• Get the angle subtended between the normals of each plane
• If the sum of the apex angles is greater than this subtended angle, your cones/triangles intersect.

So, let's say you know a few things:

1. The unit vectors of each plane's normal vector:

zVec1 = rand(1,3); zVec1 = zVec1/norm(zVec1)
zVec2 = rand(1,3); zVec2 = zVec2/norm(zVec2)

2. The "height" of each triangle (ie, the distance from your cone plane to the global origin:

ht1 = 10
ht2 = 7

3. The "width" of each triangle (ie, the radius of each cone):

wdth1 = 2
wdth2 = 3

Now you've got all you need to calculate the apex angle of each cone (ie, between the cone wall and the normal vector):

ang1 = atand(wdth1/ht1)
ang2 = atand(wdth2/ht2)

And the angle between the two plane normal vectors:

twoVecDotProd = dot(zVec1,zVec2)
angBetweenNormVecs = acosd(twoVecDotProd)

Now you've got your result:

conesIntersect = twoVecDotProd>0 && ang1+ang2 >= angBetweenNormVecs

Does that work for you?

Sven.

[Doctor61]

Hi Sven, thanks again for your valuable help.

This method is a very smart solution to my problem. But I have tried it on some random samples and it seems it does not perform correctly. BTW I have two questions about it: first, when you say "width of each triangle (ie, the radius of each cone)", do you basically mean the diameter of the circles I have as the base of the cones? Cause later you divide it by 2, in order to find the apex angle.

Also, I am a bit confused why you chose the inequality so that there is an intersection when ang1+ang2 is larger than angBetweenNormVecs, I would have assumed the opposite. Needless to say, I tried the opposite too and in some random runs it yields a wrong answer.

[Sven]

Oh, sorry, yes, I meant "diameter". I've updated the solution above to use the word "radius" and to not divide this by two.

[Sven]

Think of it this way, when angBetweenNormVecs is very small, the cones are pointing in the same direction and are more likely to intersect. When the ang1 or ang2 of the cones gets larger, that means that the cones are covering more space, and are similarly more likely to intersect. The greater-than sign is pointing the right way, and I'm quite confident that the above algorithm works correctly.

Anyway, it will always be better to show a specific example (with code to set up your zVecs/hts/wdths) rather than say that random samples don't work...

Thanks, Sven.