Search code examples
c#geometrycollision-detection

Cone-Line Segment Intersection 2D

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:

Illustration

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.

Solution

  • 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: Link

    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.