Line Segment Circle Intersection

问题:

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?

回答1:

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.

回答2:

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)

回答3:

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))

回答4:

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;

      if(bb4ac<0){
          return false;    // No collision
      }else{
          return true;      //Collision
      }
    }

回答5:

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