Cone-Line Segment Intersection 2D

Question

I would like to know if is there any way to determine if a cone is intersecting with a (finite) line segment. The cone is actually a circle located at P(x,y) with theta degree field of view and radius r:

I'm trying to do it in C# but I don't have any idea how to that, so for now this is what I'm doing:

1. Check if the line segment is intersecting with the circle;
2. If the line segment is intersecting with the circle then I check every single point in the line segment using a function I found here.

But I don't think this is the best way to do it. Does anyone have an idea?

For additional info, I need this function to make some kind of simple vision simulator.

Answer 1

I'd Google around for line/convex polygon intersection algorithms, your field of view is composed of a triangle and a part of a circle which can be approximated to any degree of accuracy by a convex polygon. Your first step might still be useful to rule out lines which go nowhere near the field of view.

Answer 2

If you keep it 2D like above, intersection can be calculated as follows:

Starting point of line segment is S1, ending is S2. Left edge of code is a vector along the edge C1, right edge is C2, Origin of code is O.

Take the sign of the Z component of the cross product of the vector formed from (O to S1) and C1.

Take the sign of the Z component of the cross product of the vector fromed from (O to S2) and C1. If the signs differ, your starting and ending points are on opposite sides of C1 and therefore they must intersect. If not, do the same comparisons with C2 instead of C1.

If neither side's signs differ, no edge intersection.

In 3D, it's a bit more complicated. I've googled and found cone sphere intersection any number of times. Doing it for lines, would be very similiar, I just need to think about it for a bit :)

A quick google of 'cone line intersection' got all sorts of hits. The basic idea is to form a plane from the cone's origin and the starting and ending point of the line. Once you have that, you can take the angle between that plane and the cone's direction normal. If that angle is less than the angle of the spread on the cone, you have an intersection.

Answer 3

Working with Polar Co-ordinates might help. Here, instead of representing a point as (x,y) you represent it as (r, angle), where r is distance from origin and angle is the angle made with a chosen axis (which corresponds to angle 0).

In your case, if you set P(x,y) to be origin and one of the rays of the cone as angle = 0 and find polar co-ordinates of the end points of the line segment, say (r1, ang1) and (r2, ang2) then you need the following four conditions to be true for the line segment to be completely within (including boundary) of the cone.

r1 <= r
r2 <= r

ang1 <= theta
ang2 <= theta

where r is the radius of the cone and theta is the angle of view and you chose the axis so that rotating counter-clockwise gives a corresponding positive angle.

Switching between polar and (x,y) (called rectangular) coordinates is easy, and you can find it on the wiki link I gave above.

In order to determine if any point of the line segment intersects the curve you can use the polar equation of a line give here: http://mathforum.org/dr.math/faq/formulas/faq.polar.html

We can use the Polar normal form

R = p sec(ang - omega)

We can figure out p and omega given the two end-points of the line segment as follows:

We have

p = r1 * cos(ang1-omega) = r2*cos(ang2-omega)

Using cos(x-y) = cos(x)*cos(y) + sin(x)*sin(y) we get

[r1*cos(ang1) - r2*cos(ang2)] * cos(omega) =  [r2*sin(ang2) - r1*sin(ang1)] * sin(omega)

Thus you can calculate tan(omega) = sin(omega)/cos(omega) and use arctan (the inverse function of tan) to get the value of omega. Once you know what omega is, you can solve for p.

Now we need to know if there is some (R, ang) combination on this line such that

R <= r
0 <= ang <= theta
min{ang1, ang2} <= ang <= max{ang1, ang2}

(Note r was radius of cone, and theta was the angle of view, ang1 was angle of P1 and ang2 was angle of P2).

The equation can be rewritten as

Rcos(ang-omega) = p

Now cos(ang-omega) is a very nicely behaved function in terms of monotonicity and you only need to consider it in the interval [min{ang1, ang2}, max{ang1, ang2}].

You should be able to do some manual manipulations first in order to simplify your code.

I will leave the rest to you.