5

enter image description here

  • I have a line segment (begin x1,y1, end x2,y2 (D=5 lets say) ) and a circle (radius R, center x3,y3)

How can I check that if my line segment intersects my circle?

lacas
  • 13,928
  • 30
  • 109
  • 183

4 Answers4

5

As a preliminary check, you can just calculate the distance between a point and a line using a cross product:

(x1,y1) = p1, (x2,y2) = p2
(cx, cy) = c = circle center
delta = p2 - p1 (the difference vector)
unit = delta/norm(delta) (the unit vector along the line segment)
(c-p1) x unit = (cx-x1) * unity - (cy-y1) * unitx = d (distance of the circle center to the line)

Note that d has a direction (sign).

if d is outside the range [-R,R], then the line segment can not intersect the circle.

If your line segments don't move around so much, you can save the unit vector for later reuse.

If the circle does indeed intersect with the line (as opposed to the line segment) it might still not intersect with the line segment. Check these three conditions:

  • p1 lies within the circle; norm(p1-c) < R
  • p2 lies within the circle; norm(p2-c) < R
  • the closest point from the line to the circle center lies between p1 and p2:

(unit . p1 < unit . c < unit . p2) or (unit . p2 < unit . c < unit . p1) where . is vector dot product.

If none of these conditions hold, then they don't intersect.

You might also need to know where they intersect:

perp = (-unity, unitx) (The perpendicular vector)
pclosest = perp * d + c (The point on the line closest to the circle center)
dline = sqrt(R^2 - d^2) (The distance of the intersection points from pclosest)
i{1,2} = ±dline * unit + pclosest

You obviously need to check separately whether i{1,2} lie between p1 and p2, just like we did in the third condition above.

szotsaki
  • 684
  • 7
  • 16
enobayram
  • 4,650
  • 23
  • 36
  • c x unit is not the distance of the circle to the line. instead of c you have to use (c-p1). The rest should be correct. – D-rk May 14 '14 at 08:31
2

If you have a Line2D for your line segment, and a Point2D for the center of the circle, then just check if line.ptSegDist(center) <= radius.

Louis Wasserman
  • 191,574
  • 25
  • 345
  • 413
  • I think it's not entirely correct. You should use `ptSegDist` method, as for `ptLineDist` "the distance measured is the distance between the specified point and the closest point on the infinitely-extended line defined by this Line2D". Question poster asked specifically about line segment intersection. – madej Oct 08 '12 at 19:22
0

You have two implicit equations: (x-x0)^2+(y-y0)^2-r^2=0 for the circle, and v2*x-v1*y=v2*x0-v1*y0 for the line (where v1=x1-x2, v2=y1-y2). Just solve the system of equations, than check whether the solution is on your line segment (for example check that the x and y coordinates of the solution are between the two corner point's corresponding coordinates).

WebMonster
  • 2,981
  • 2
  • 22
  • 29
0

Derive (x, y) from (y2-y1)/(x2-x1)*x + D = y and (x-x3)^2 + (y-y3)^2 = R^2. Then find out if (x, y) belongs to your line segment.

clime
  • 8,695
  • 10
  • 61
  • 82