how to check if a line segment intersects a circle

is there any formula to check whether a line intersects a circle in matlab.can someone help me out. suppose i have got a line segemtn with ends x,y and x1,y2 and there is a circle with centre h,k with radius r. how can i know if the line segement intersects the circle or not

[Stephen23]

http://mathworld.wolfram.com/Circle-LineIntersection.html

[Borison ningthoujam]

that was very helpfull....can i get the program as an example

Answer 1

[Jan]

Calculate the distance between the line and the center of the circle:

P1 = [-2, -2];  % Point 1 of the line
P2 = [2, 2];    % Point 2 of the line
C  = [0, 0];    % Center of circle
R  = 2;         % Radius of circle

P12 = P2 - P1;
N   = P12 / norm(P12);  % Normalized vector in direction of the line

P1C = C - P1;           % Line from one point to center
v   = abs(N(1) * P1C(2) - N(2) * P1C(1));  % Norm of the 2D cross-product

doIntersect = (v <= R);

The geometrical explanation is easy: The cross-product replies the area of the parallelogram build by the normal of the line and the vector fro P1 to C. The area of this parallelogram is identical to the area of the rectangle build by the normal N and the vector orthogonal to N through C. The value of this area is the distance multiplied by 1 (the length of the N). Summary: The distance between the line and a point in 2D is the absolute value of the 3rd component of the cross-product between N and the vector from P1 (or P2) to C.

All you have to do is to compare, if this distance is smaller or equal to the radius.

In 3D the norm of the 3D cross-product is needed:

v = norm(cross(N, P1C));

[John Medina]

Nice!!

[Enrico de Marinis]

The solution is very attractive, (and the geometric interpretation is nice) but the test should completed by taking into account the three situations not handled by the method:

1) P1 lies inside the circle and P2 outside;

2) P2 lies inside the circle and P1 outside:

3) both P1 and P2 lie inside the circle.

This can be handled by extending the proposed method in the following way.

% this code example is not optimised 

C = [xc; yc]; % centre of the circle
R = r; % is the radius of the circle
P1 = [x1; y1]; % 1st point of the segment
P2 = [x2; y2]; % 2nd point of the segment

d1c = norm( [(x1-xc); (y1-yc)] ); % distance of P1 from the centre
d2c = norm( [(x2-xc); (y2-yc)] ); % distance of P2 from the centre
if (d2c<R) && (d1c<R)
    flag_intersect = false ;
elseif (d1c<R) && (d2c>R)
     flag_intersect = true;
elseif (d2c<R) && (d1c>R)
    flag_intersect = true;
else
    P12 = [(x2-x1) ; (y2-y1)];
    uP12 = P12/norm(P12);
    P1C = [(xc - x1); (y2 - yc)];
    v = abs( uP12(1)*P1C(2) - uP12(2)*P1C(1) );
    flag_intersect = (v < R);
end

[Jan]

You are right: My code does not consider, that it is a line segment, not a line. But then there is a further problem: If both P1 and P2 are outside the circle, but on the same side, there is no intersection. If both points are inside, it matters if a circle or disk is meant.

Answer 2

[Truong Nhu]

I have a more rounded solution for anybody who need it. For your information, I found this on Stackoverflow. If you want to understand the math behind it follow this link Behind-the-scene Math.

P1, P2 is the two points of the line segment. C is then center of the circle.

function flag_intersect = intersect_line_cir(P1,P2,C,radius)
d = P2 - P1;
f = P1 - C;
r = radius;
a = dot(d,d);
b = 2*dot(f,d);
c = dot(f,f) - r^2;

discriminant = b*b-4*a*c;
if( discriminant < 0 )

%   // no intersection
    flag_intersect = false;
    return
else

%   // ray didn't totally miss sphere,
%   // so there is a solution to
%   // the equation.
  
  discriminant = sqrt( discriminant );

%   // either solution may be on or off the ray so need to test both
%   // t1 is always the smaller value, because BOTH discriminant and
%   // a are nonnegative.
  t1 = (-b - discriminant)/(2*a);
  t2 = (-b + discriminant)/(2*a);

%   // 3x HIT cases:
%   //          -o->             --|-->  |            |  --|->
%   // Impale(t1 hit,t2 hit), Poke(t1 hit,t2>1), ExitWound(t1<0, t2 hit), 

%   // 3x MISS cases:
%   //       ->  o                     o ->              | -> |
%   // FallShort (t1>1,t2>1), Past (t1<0,t2<0), CompletelyInside(t1<0, t2>1)
  
  if( t1 >= 0 && t1 <= 1 )
  
%     // t1 is the intersection, and it's closer than t2
%     // (since t1 uses -b - discriminant)
%     // Impale, Poke
    flag_intersect = true;
    return
  end

%   // here t1 didn't intersect so we are either started
%   // inside the sphere or completely past it
  if( t2 >= 0 && t2 <= 1 )
  
%     // ExitWound
    flag_intersect = true;
    return
  end
  
%   // no intn: FallShort, Past, CompletelyInside
    flag_intersect = false;
  return 
end