Line Segment Circle Intersection

Question

I am trying to determine the point at which a line segment intersect a circle. For example, given any point between P0 and P3 (And also assuming that you know the radius), what is the easiest method to determine P3?

Circle

score 20 · Answer 1 · answered May 23 '11 at 00:28

20

Generally,

find the angle between P0 and P1
draw a line at that angle from P0 at a distance r, which will give you P3

In pseudocode,

theta = atan2(P1.y-P0.y, P1.x-P0.x)
P3.x = P0.x + r * cos(theta)
P3.y = P0.y + r * sin(theta)

answered May 23 '11 at 00:28

Greg Hewgill

951,095
183
1,149
1,285

This is exactly what I was looking for - trying to draw lines between two circles with the lines directed at the center, but with the endpoints on the *outside* of the circles rather than the actual centers. – Krease Jun 03 '13 at 21:02
This method is good, but re-structuring it to use rsqrt & normals, instead of atan2+cos+sin & angles, was the ticket for performance for me. Hope it helps someone! :) – MickLH Sep 03 '13 at 01:06
2

this is correct when p0 is the center of the circle, as the drawing above shows, but the question doesn't seem to be about that – Martijn Scheffer May 08 '17 at 16:09
Maaaan... thanks alot, this answer was really helpful. – MattCodes Sep 26 '22 at 19:40

score 11 · Answer 2 · edited Jun 20 '20 at 09:12

From the center of the circle and the radius you can write the equation describing the circle. From the two points P0 and P1 you can write the equation describing the line.

So you have 2 equations in 2 unknowns, which you can solved through substitution.

Let (x0,y0) = coordinates of the point P0

And (x1,y1) = coordinates of the point P1

And r = the radius of the circle.

The equation for the circle is:

(x-x0)^2 + (y-y0)^2 = r^2

The equation for the line is:

(y-y0) = M(x-x0)  // where M = (y1-y0)/(x1-x0)

Plugging the 2nd equation into the first gives:

(x-x0)^2*(1 + M^2) = r^2

x - x0 = r/sqrt(1+M^2)

Similarly you can find that

y - y0 = r/sqrt(1+1/M^2)

The point (x,y) is the intersection point between the line and the circle, (x,y) is your answer.

P3 = (x0 + r/sqrt(1+M^2), y0 + r/sqrt(1+1/M^2))

Would that work for perfectly horizontal and vertical lines? I am not good at math, but it does not seem to work. — Martin Melichar, Jun 30 '23 at 19:20

Tofeeq Ahmad · Answer 3 · 2019-12-10T09:42:54.460

8

Go for this code..its save the time

private boolean circleLineIntersect(float x1, float y1, float x2, float y2, float cx, float cy, float cr ) {
      float dx = x2 - x1;
      float dy = y2 - y1;
      float a = dx * dx + dy * dy;
      float b = 2 * (dx * (x1 - cx) + dy * (y1 - cy));
      float c = cx * cx + cy * cy;
      c += x1 * x1 + y1 * y1;
      c -= 2 * (cx * x1 + cy * y1);
      c -= cr * cr;
      float bb4ac = b * b - 4 * a * c;

         // return false  No collision
         // return true Collision
      return bb4ac >= 0;
    }

edited Dec 10 '19 at 09:42

answered Feb 22 '12 at 11:09

Tofeeq Ahmad

11,935
4
61
87

1

This is for line which if different than line-segment. – Stritof Dec 14 '15 at 14:51
this just returns a boolean that says IF there is an intersection, it doesn't return the intersection itself – Martijn Scheffer May 08 '17 at 16:11
1

Why not replace the bottom 5 lines of the function with `return bb4ac >= 0`? – Water Sep 27 '19 at 15:29

score 5 · Accepted Answer · answered May 23 '11 at 00:29

5

You have a system of equations. The circle is defined by: x^2 + y^2 = r^2. The line is defined by y = y0 + [(y1 - y0) / (x1 - x0)]·(x - x0). Substitute the second into the first, you get x^2 + (y0 + [(y1 - y0) / (x1 - x0)]·(x - x0))^2 = r^2. Solve this and you'll get 0-2 values for x. Plug them back into either equation to get your values for y.

answered May 23 '11 at 00:29

Shea Levy

5,237
3
31
42

When you get two solutions, how will you tell which one is P3 and which one is the corresponding point on the other side of the circle? – Greg Hewgill May 23 '11 at 01:32
Find the distance between each point and P1. You can calculate the square of the distance by (x3-x1)^2 + (y3-y1)^2, whichever of those is smallest is closer to P1. – Shea Levy May 23 '11 at 01:42
Please note that this solution does not work for the case where x1-x0 is zero! – Eddie's Jul 05 '21 at 14:43

score 2 · Answer 5 · answered Jun 24 '17 at 07:11

MATLAB CODE

function [ flag] = circleLineSegmentIntersection2(Ax, Ay, Bx, By, Cx, Cy, R)

% A and B are two end points of a line segment and C is the center of the circle, % R is the radius of the circle. THis function compute the closest point fron C to the segment % If the distance to the closest point > R return 0 else 1

Dx = Bx-Ax;
Dy = By-Ay;

LAB = (Dx^2 + Dy^2);
t = ((Cx - Ax) * Dx + (Cy - Ay) * Dy) / LAB;

if t > 1
    t=1;
elseif t<0
    t=0;
end;


nearestX = Ax + t * Dx;
nearestY = Ay + t * Dy;

dist = sqrt( (nearestX-Cx)^2 + (nearestY-Cy)^2 );

if (dist > R )
 flag=0;
else
 flag=1;
end

end

Line Segment Circle Intersection

5 Answers5

Linked