how to check if a line segment intersects a circle

47 views (last 30 days)
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

Accepted Answer

Jan
Jan on 21 May 2018
Edited: Jan on 21 May 2018
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));
  3 Comments
Enrico de Marinis
Enrico de Marinis on 3 Oct 2020
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
Jan on 4 Oct 2020
Edited: Jan on 4 Oct 2020
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.

Sign in to comment.

More Answers (1)

Truong Nhu
Truong Nhu on 12 Apr 2022
Edited: Truong Nhu on 12 Apr 2022
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

Products


Release

R2016a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!