2009-07-02 09:15:10 8 Comments

I have a line from A to B and a circle positioned at C with the radius R.

What is a good algorithm to use to check whether the line intersects the circle? And at what coordinate along the circles edge it occurred?

### Related Questions

#### Sponsored Content

#### 48 Answered Questions

#### 23 Answered Questions

### [SOLVED] Image Processing: Algorithm Improvement for 'Coca-Cola Can' Recognition

**2012-04-16 04:23:16****Charles Menguy****195713**View**1697**Score**23**Answer- Tags: c++ algorithm image-processing opencv

#### 7 Answered Questions

### [SOLVED] Ukkonen's suffix tree algorithm in plain English

**2012-02-26 11:30:09****Nathan Ridley****171161**View**1121**Score**7**Answer- Tags: string algorithm data-structures language-agnostic suffix-tree

#### 20 Answered Questions

### [SOLVED] What is the best algorithm for overriding GetHashCode?

**2008-11-04 20:53:19****bitbonk****220033**View**1481**Score**20**Answer- Tags: .net algorithm hashcode gethashcode

#### 16 Answered Questions

### [SOLVED] Equation for testing if a point is inside a circle

**2009-01-26 20:07:26****directedition****270221**View**319**Score**16**Answer- Tags: algorithm language-agnostic geometry

#### 35 Answered Questions

### [SOLVED] Fastest way to determine if an integer's square root is an integer

**2008-11-17 13:43:21****Kip****280419**View**1490**Score**35**Answer- Tags: java math optimization perfect-square

#### 14 Answered Questions

### [SOLVED] What is the optimal algorithm for the game 2048?

**2014-03-12 05:37:21****nitish712****944563**View**1935**Score**14**Answer- Tags: algorithm logic artificial-intelligence 2048

## 27 comments

## @Matthew Perlman 2020-05-14 12:22:29

You can take X evenly spaced points from the line and if any are inside the circle, there is a collision

## @Ian Douglas 2020-04-20 20:11:43

Solution in python, based on @Joe Skeen

## @Jorge Eduardo G 2019-12-04 02:24:39

I know it's been a while since this thread was open. From the answer given by chmike and improved by Aqib Mumtaz. They give a good answer but only works for a infinite line as said Aqib. So I add some comparisons to know if the line segment touch the circle, I write it in Python.

## @Joe Skeen 2019-04-16 05:35:31

Here is my solution in TypeScript, following the idea that @Mizipzor suggested (using projection):

## @chmike 2009-07-06 16:55:52

I would use the algorithm to compute the distance between a point (circle center) and a line (line AB). This can then be used to determine the intersection points of the line with the circle.

Let say we have the points A, B, C. Ax and Ay are the x and y components of the A points. Same for B and C. The scalar R is the circle radius.

This algorithm requires that A, B and C are distinct points and that R is not 0.

Here is the algorithm

## @Prashant 2014-12-12 10:33:30

if any line that is not intersecting the circle and its both point p1 and p2 are inside circle. in this case how your algorithm work??

## @chmike 2014-12-14 13:13:39

You have to test t-dt and t+dt. If t-dt < 0, than p1 is inside the circle. If t+dt > 1, than p2 is inside the circle. This is true if LEC < R of course.

## @punchcard 2015-05-12 14:15:20

Thanks. I liked this pgm comments as explanation because there was no use of the words "dot product" since my math is rusty. However t and dt are not between 0..1 so while changing this to python I changed t to be divided by LAB**2. My understanding is the first division by LAB is to project the center of the circle to the line AB, and the second division by LAB is to normalize it into the range 0..1. Also the dt needs to be divided by LAB so it is also normalized. Thus "if (t-dt >=0.0)" first intersection exists "if (t+dt <= 1.0)" second intersection exists. This worked with testing.

## @Mahmoud Ayman 2015-05-27 09:49:39

@chmike Can I please know why did you write in the part where LEC<R:

`t+dt`

once and`t-dt`

in another point? Why did you one time plus and the other subtract?## @chmike 2015-05-27 15:57:43

Because the intersection point with the circle are at "distance"

`t+dt`

and`t-dt`

on the line.`t`

is the point on the line closest to the center of the circle. The intersection points with the circle are at a symmetric distance from`t`

. The intersection points are at "distances"`t-dt`

and`t+dt`

. I quoted distance because it it's not the euclidian distance. To get the euclidian distance from`A`

where`t=0`

, you have to multiply the value by`LAB`

.## @Matt W 2015-10-11 00:38:10

This code calculates intersections on the line's vector. How can you determine if the intersection occurs on the line between the end points rather than outside the line?

## @Marconius 2015-12-08 18:59:56

@Matt W You mean "How to determine if the intersection occurs outside the end points of the line section AB"? Just think about t as a measure of distance along the line. Point A is at

`t=0`

. Point B at`t=LAB`

. When both intersection points (`t1=t-td`

and`t2=t+td`

) have negative values than intersections are outside the section (behind point A looking from the section side of the point). When t1 and t2 are bigger than LAB then they are outside too (this time behind B point). Intersection t1 (or t2) occurs between A and B only when t1 (or t2) it is between 0 and LAB.## @fishinear 2018-10-25 16:44:57

There is a small fault in the equations. t is divided by LAB, and therefore lies between 0 (at A) and 1 (at B). But dt is not divided by LAB. Either both t and dt should be divided by LAB, or neither should.

## @chmike 2018-10-25 17:14:59

@fishinear you are right. I should have divided by LAB. I'll fix it.

## @fishinear 2018-10-25 19:11:10

@chmike Actually, I think I was wrong in my remark. You divide D by LAB, not t, which means that t is actually between 0 and LAB (the comment in the code is incorrect in that respect). That means again that dt should not be divided by LAB either, and your original code was correct.

## @fishinear 2018-10-26 07:41:24

@chmike Suppose Ax == Bx == Cx, then Dx is zero and Dy is equal to 1. That means that t must be equal to By - Ay at point B, not 1.

## @chmike 2018-10-26 09:41:23

@fishinear you are right. If I want t to be 0 at A and 1 at B, then Dx = Bx - Ax and Dy = By - Ay. In this case t

Dx + Ax = x and tDy+Ay = y is correct. There is another error. The scalar product between AC and AB computed as Dx*(Cx-Ax)+Dy*(Cy-Ay) = LACLABcos θ. The value t for the point E is cos θ. I must thus divide the result of the scalar product by (LAC*LAB). This can be verified when C = B. In this case t = 1. We can then compute the coordinates of the point E. This solution to the question is not very efficient.## @fishinear 2018-10-26 10:56:41

@chmike Actually, in your original code, you divide Dx and Dy by LAB. That means that Dx*(Cx-Ax)+Dy*(Cy-Ay) is already divided by LAB, and therefore is equal to LAC*cos θ = LAE. And that is exactly what t needs to be if it needs to equal LAB at B. So your original code was actually correct, just not the comment that t is 1 at B. I still think it is an excellent solution.

## @chmike 2018-10-26 12:13:07

@fishinear It should now be fixed. You're first comment confused me.

## @martin 2018-07-24 19:53:33

I just needed that, so I came up with this solution. The language is maxscript, but it should be easily translated to any other language. sideA, sideB and CircleRadius are scalars, the rest of the variables are points as [x,y,z]. I'm assuming z=0 to solve on the plane XY

## @Steller 2018-03-20 23:26:20

Here is a solution written in golang. The method is similar to some other answers posted here, but not quite the same. It is easy to implement, and has been tested. Here are the steps:

The values for A, B, and C for the quadratic are derived here, where (n-et) and (m-dt) are the equations for the line's x and y coordinates, respectively. r is the radius of the circle.

Therefore A = ee+dd, B = - 2(en + dm), and C = nn + mm - rr.

Here is the golang code for the function:

I tested it with this function, which confirms that solution points are within the line segment and on the circle. It makes a test segment and sweeps it around the given circle:

Here is the output of the test:

Finally, the method is easily extendable to the case of a ray starting at one point, going through the other and extending to infinity, by only testing if t > 0 or t < 1 but not both.

## @FunDeveloper89 2018-03-17 13:10:21

In this post circle line collision will be checked by checking distance between circle center and point on line segment (Ipoint) that represent intersection point between normal N (Image 2) from circle center to line segment.

(https://i.stack.imgur.com/3o6do.png)

On image 1 one circle and one line are shown, vector A point to line start point, vector B point to line end point, vector C point to circle center. Now we must find vector E (from line start point to circle center) and vector D (from line start point to line end point) this calculation is shown on image 1.

(https://i.stack.imgur.com/7098a.png)

At image 2 we can see that vector E is projected on Vector D by "dot product" of vector E and unit vector D, result of dot product is scalar Xp that represent the distance between line start point and point of intersection (Ipoint) of vector N and vector D. Next vector X is found by multiplying unit vector D and scalar Xp.

Now we need to find vector Z (vector to Ipoint), its easy its simple vector addition of vector A (start point on line) and vector X. Next we need to deal with special cases we must check is Ipoint on line segment, if its not we must find out is it left of it or right of it, we will use vector closest to determine which point is closest to circle.

(https://i.stack.imgur.com/p9WIr.png)

When projection Xp is negative Ipoint is left of line segment, vector closest is equal to vector of line start point, when projection Xp is greater then magnitude of vector D then Ipoint is right of line segment then closest vector is equal to vector of line end point in any other case closest vector is equal to vector Z.

Now when we have closest vector , we need to find vector from circle center to Ipoint (dist vector), its simple we just need to subtract closest vector from center vector. Next just check if vector dist magnitude is less then circle radius if it is then they collide, if its not there is no collision.

(https://i.stack.imgur.com/QJ63q.png)

For end, we can return some values for resolving collision , easiest way is to return overlap of collision (subtract radius from vector dist magnitude) and return axis of collision, its vector D. Also intersection point is vector Z if needed.

## @xakepp35 2018-02-25 16:58:38

Circle is really a bad guy :) So a good way is to avoid true circle, if you can. If you are doing collision check for games you can go with some simplifications and have just 3 dot products, and a few comparisons.

I call this "fat point" or "thin circle". its kind of a ellipse with zero radius in a direction parallel to a segment. but full radius in a direction perpendicular to a segment

First, i would consider renaming and switching coordinate system to avoid excessive data:

Second, index h in hvec2f means than vector must favor horisontal operations, like dot()/det(). Which means its components are to be placed in a separate xmm registers, to avoid shuffling/hadd'ing/hsub'ing. And here we go, with most performant version of simpliest collision detection for 2D game:

I doubt you can optimize it any further. I am using it for neural-network driven car racing collision detection, to process millions of millions iteration steps.

## @Chris 2020-06-17 13:44:14

If the line segment intersects the circle but only slightly so it does not pass its center point, won't this function return false when it should return true? The t value might be outside the range 0..1.

## @will.fiset 2017-07-07 16:02:33

Here's an implementation in Javascript. My approach is to first convert the line segment into an infinite line then find the intersection point(s). From there I check if the point(s) found are on the line segment. The code is well documented, you should be able to follow along.

You can try out the code here on this live demo. The code was taken from my algorithms repo.

## @nazar kuliyev 2017-06-08 11:07:35

Here is good solution in JavaScript (with all required mathematics and live illustration) https://bl.ocks.org/milkbread/11000965

Though

`is_on`

function in that solution needs modifications:## @Eric Ouellet 2016-05-12 17:44:48

Another one in c# (partial Circle class). Tested and works like a charm.

Required:

## @ercang 2015-08-19 11:25:34

I wrote a small script to test intersection by projecting circle's center point on to line.

http://jsfiddle.net/ercang/ornh3594/1/

If you need to check the collision with the segment, you also need to consider circle center's distance to start and end points.

https://jsfiddle.net/ercang/menp0991/

## @Duq 2015-08-13 23:42:21

Weirdly I can answer but not comment... I liked Multitaskpro's approach of shifting everything to make the centre of the circle fall on the origin. Unfortunately there are two problems in his code. First in the under-the-square-root part you need to remove the double power. So not:

`var underRadical = Math.pow((Math.pow(r,2)*(Math.pow(m,2)+1)),2)-Math.pow(b,2));`

but:

`var underRadical = Math.pow(r,2)*(Math.pow(m,2)+1)) - Math.pow(b,2);`

In the final coordinates he forgets to shift the solution back. So not:

`var i1 = {x:t1,y:m*t1+b}`

but:

`var i1 = {x:t1+c.x, y:m*t1+b+c.y};`

The whole function then becomes:

## @Gino 2016-01-12 18:05:35

suggestions: First, have it handle the case where line segment is vertical (i.e. has infinite slope). Secondly, have it only return those points that actually fall within the range of the original line segment -- i believe it's happily returning all points that fall on the infinite line, even if those points lie outside of the line segment.

## @Mike 2019-02-22 14:05:06

Note: This works well for lines, but does not work for line segments.

## @Aqib Mumtaz 2014-11-24 13:30:23

I have created this function for iOS following the answer given by

`chmike`

## @multitaskPro 2014-03-01 04:42:22

This solution I found seemed a little easier to follow then some of the other ones.

Taking:

I would solve for the equation of the line in slope-intercept form. However, I didn't want to have to deal with difficult equations with

`c`

as a point, so I just shifted the coordinate system over so that the circle is at`0,0`

By the way, whenever I subtract points from each other I am subtracting the

`x`

's and then subtracting the`y`

's, and putting them into a new point, just in case someone didn't know.Anyway, I now solve for the equation of the line with

`p3`

and`p4`

:Ok. Now I need to set these equations equal. First I need to solve the circle's equation for

`x`

Then I set them equal:

And solve for the quadratic equation (

`0 = ax^2 + bx + c`

):Now I have my

`a`

,`b`

, and`c`

.So I put this into the quadratic formula:

And substitute in by values then simplify as much as possible:

This is almost as far as it will simplify. Finally, separate out to equations with the ±:

Then simply plug the result of both of those equations into the

`x`

in`mx + b`

. For clarity, I wrote some JavaScript code to show how to use this:I hope this helps!

P.S. If anyone finds any errors or has any suggestions, please comment. I am very new and welcome all help/suggestions.

## @Prabindh 2014-03-01 05:01:05

If possible, also post with some sample values so that we can quickly grasp the flow.

## @byJeevan 2016-02-25 06:54:13

With

`underRadical`

extra ')'## @A.J.Bauer 2014-02-24 13:34:27

## @bobobobo 2009-07-05 21:54:39

Taking

Eis the starting point of the ray,Lis the end point of the ray,Cis the center of sphere you're testing againstris the radius of that sphereCompute:

d= L - E ( Direction vector of ray, from start to end )f= E - C ( Vector from center sphere to ray start )Then the intersection is found by..

Plugging:

P = E + t * dThis is a parametric equation:

P

_{x}= E_{x}+ td_{x}P

_{y}= E_{y}+ td_{y}into

(x - h)^{2}+ (y - k)^{2}= r^{2}(h,k) = center of circle.

to get:Expandx

^{2}- 2xh + h^{2}+ y^{2}- 2yk + k^{2}- r^{2}= 0Plugx = e

_{x}+ td_{x}y = e

_{y}+ td_{y}( e

_{x}+ td_{x})^{2}- 2( e_{x}+ td_{x})h + h^{2}+ ( e_{y}+ td_{y})^{2}- 2( e_{y}+ td_{y})k + k^{2}- r^{2}= 0e

_{x}^{2}+ 2e_{x}td_{x}+ t^{2}d_{x}^{2}- 2e_{x}h - 2td_{x}h + h^{2}+ e_{y}^{2}+ 2e_{y}td_{y}+ t^{2}d_{y}^{2}- 2e_{y}k - 2td_{y}k + k^{2}- r^{2}= 0Groupt

^{2}( d_{x}^{2}+ d_{y}^{2}) + 2t( e_{x}d_{x}+ e_{y}d_{y}- d_{x}h - d_{y}k ) + e_{x}^{2}+ e_{y}^{2}- 2e_{x}h - 2e_{y}k + h^{2}+ k^{2}- r^{2}= 0Finally,t

^{2}( _d * _d ) + 2t( _e * _d - _d * _c ) + _e * _e - 2( _e*_c ) + _c * _c - r^{2}= 0*Where _d is the vector d and * is the dot product.*

And then,t

^{2}( _d * _d ) + 2t( _d * ( _e - _c ) ) + ( _e - _c ) * ( _e - _c ) - r^{2}= 0Letting _f = _e - _ct

^{2}( _d * _d ) + 2t( _d * _f ) + _f * _f - r^{2}= 0So we get:

t^{2}* (d DOT d) + 2t*( f DOT d ) + ( f DOT f - r^{2}) = 0So solving the quadratic equation:

## @Mizipzor 2009-07-06 12:17:33

Seems to work if I do straight copy and paste, but Im looking to understand it to. In (x-h)^2+(y-k)^2=r^2 what is h and k? Is k to constant by which the line/ray increases on y over x? And what is t? Looking at the code it seems you have assumed its 1 (so its just "removed"). Do these formulas have a name or something? Maybe I can look them up in detail on Wolfram.

## @bobobobo 2009-07-06 13:22:19

h and k are the center of the circle that you're intersecting against. t is the parameter of the line equation. In the code, t1 and t2 are the solutions. t1 and t2 tell you "how far along the ray" the intersection happened.

## @chmike 2009-07-10 06:17:14

Very elegant solution that requires only one square root computation and should in principle work in 3D. What would be the 3D equation and how do we find the roots ?

## @chmike 2009-07-10 06:23:04

Ok, got it. The dot product is simply computed over the three elements (x,y,z) vectors. I will switch my code to this algorithm.

## @Jason 2009-10-16 21:47:21

Can someone fully explain how we're going from (x - h)^2 + (y - k)^2 = r^2 to t^2 * (d DOT d) + (2t * (f DOT d)) + (f DOT f - r^2) = 0? I tried plugging in the parametric equivalent of x and y and got something I couldn't reduce. Thanks very much.

## @Andrew Stacey 2012-06-02 18:18:28

(I just came across someone using this method and getting false negatives. Looking at the code, I saw that it is only testing

oneintersection point to see if it is on the line segment, but it needs to test both. I edited in the second test as well.)## @bobobobo 2012-06-02 19:42:21

@AndrewStacey Good edit, I had thought that would be straight forward. I'd also like to add that the smaller of t1/t2 is going to be closer to the ray start position, but I left it out.

## @Andrew Stacey 2012-06-02 20:01:07

@bobobobo I figured one way of reading "t2 is the other intersection point" as "you also need to test t2" but as I'd just seen someone not realise that I thought it worth editing in (make the internet a better place, and all that). Your second sentence is misleading as the smaller of t1/t2 is not necessarily on the line (indeed, this was the problem I saw: the edge case of when one point is on the line segment and the other isn't; I know it's obvious but sometimes the obvious isn't obvious until it's been pointed out).

## @Derek 朕會功夫 2012-06-09 01:49:18

`P = E + t * d`

What is`t`

?## @Nicolas Mommaerts 2013-04-03 22:54:13

Not sure why, but the code doesn't seem to work for the Impale case. It does when I add if t1 <= 0 && t1 >= -1 && t2 <= 0 && t2 >= -1 as true condition, but then it also gives a false positive on one side of the finite line, when the circle is on the "infinite" part. I don't understand the math yet, but copy/pasters, beware.

## @async 2014-05-11 10:29:25

This seems to compute the intersection of a circle with a

line, not asegment.## @Rialgar 2014-08-24 11:37:03

I just came up with a better way of understanding the final formula. (P-C)^2 equals r^2, since P is on the circle; C+f equals E by definition; E + t

d equals P by definition; so C + f + td equals P; so (f + td)^2 equals r^2; so t^2*d^2 + t*2*fd equals r^2; so we get our quadratic formula## @b1nary.atr0phy 2016-07-17 21:28:57

"E is the starting point of the ray, L is the end point of the ray"Rays only have one point, extending infinitely along a vector. What you're describing is aline segment.## @sliders_alpha 2016-11-16 13:00:46

What language is this? I need to read the documentation of Impale(), Past(), etc.

## @TommasoF 2017-03-24 10:06:16

Have a look at this link math.stackexchange.com/questions/311921/… for theoretic explanation.

## @ickydime 2017-07-28 00:37:27

For those asking what is t... You need to implement the code example where he finds t1 and t2. Then drop that into: P = E + t * d For example at // ExitWound you could then write (C#): var intersection = new Vector3(E.x + t1 * d.x, secondPoint.y, E.y + t1 * d.y); Worked great. Thanks!

## @Minestrone-Soup 2017-12-10 19:28:21

@NicolasMommaerts really old question, but if people are having the same problem as Nicolas as I did, it's because you did f = C - E instead of f = E - C

## @Anthony 2018-07-08 13:59:02

Note that this algorithm requires the line and the circle lie on the same plane, which is always the case in 2D.

## @bobobobo 2019-11-05 02:05:13

@Derek朕會功夫

`t`

is a parameter. In`P = E + t * d`

,`P`

is some point in space we will get to BY STARTING at`E`

, then moving`t`

units along the direction vector`d`

.`t`

is a variable that describes how far along the direction vector`d`

we are## @Mizipzor 2009-07-03 13:57:28

No one seems to consider projection, am I completely off track here?

Project the vector

`AC`

onto`AB`

. The projected vector,`AD`

, gives the new point`D`

.If the distance between

`D`

and`C`

is smaller than (or equal to)`R`

we have an intersection.Like this:

## @ADB 2010-09-01 14:42:33

There are many details to take into consideration: does D lie between AB? Is C perpendicular distance to the line larger than the radius? All of these involve magnitude of vector, i.e. square root.

## @Ben 2012-02-29 15:39:00

Good idea, but how do you then compute the two intersection points?

## @Spider 2014-11-04 14:30:40

@Mizipzor. bit late, but I dont agree with this point. Coz, it does not consider that AB segment line position at all. Your point is true when only AB is perpendicularly located against CD point! Consider AB segment line where CD is not perpendicular to AB at all. What is your opinion on that?

## @user719662 2014-12-07 00:02:24

@Ben the two intersection points (let's call them

`P1`

&`P2`

,`Px`

in general) are points on`AB`

that are exactly`r`

distance from`C`

- simply calculate |CD| distance and from Pyth's you know that |CD|^2+|PxD|^2 = r^2 - making this trivial if you know how to calculate line's parametric equation (which I assume you should).## @user719662 2014-12-07 00:03:35

@Spider it doesn't matter. In general, since this is a variant of sphere-line intersection problem, Mizipzor's strategy is perfectly valid.

`CD`

is a projection, it is perpendicular by definition.## @Andrew 2015-01-10 11:00:03

It's an old question, but there's a good resource on this and related algorithms at this website: paulbourke.net/geometry/pointlineplane

## @ShawnFeatherly 2018-01-24 01:52:05

A great explanation of this answer: scratchapixel.com/lessons/3d-basic-rendering/…

## @unlut 2018-07-18 17:58:56

Isn't this answer in incomplete? It finds whether a circle and line intersect, not a line segment. In my opinion correct check should be something like:

`(projectionPointInCircle and projectionPointOnLine) or endPointsInCircle`

Last check is necessary since line segment may penetrate circle and finish before it goes past center. endPoints refer to starting and ending points of line segment.## @GMartigny 2018-12-20 16:05:40

@unlut You're right. It even depend on the kind of calculation you use to project C on AB. I made a simulation if someone want to play around : desmos.com/calculator/gb7hk2dfwp

## @a_m0d 2009-07-02 09:21:48

Okay, I won't give you code, but since you have tagged this algorithm, I don't think that will matter to you. First, you have to get a vector perpendicular to the line.

You will have an unknown variable in

`y = ax + c`

(`c`

will be unknown)To solve for that, Calculate it's value when the line passes through the center of the circle.

That is,

Plug in the location of the circle center to the line equation and solve for

`c`

.Then calculate the intersection point of the original line and its normal.

This will give you the closest point on the line to the circle.

Calculate the distance between this point and the circle center (using the magnitude of the vector).

If this is less than the radius of the circle - voila, we have an intersection!

## @Mizipzor 2009-07-02 09:25:29

That was, in fact, what I wanted. I want the theory, a google search of line-circle collision algorithm turns up only code as far as I can see.

## @Mizipzor 2009-07-03 13:26:44

Ok, c is unknown in your equation, but what is "a"? The other answers seem to refer to that variable as "alpha" and "t". Although, this is just a linear function (y=kx+m), quite basic math, so I suddenly feel a bit rusty. Isnt k also unknown? Or do you mean we can assume m=0 and solve k? Wouldnt then m (that is, c) always be zero for our solved k?

## @a_m0d 2009-07-03 21:22:35

Oh, sorry - I am using the simple equation of a line with a gradient and offset (the cartesian equation). I assumed that you were storing the line as such an equation - in which case you use the negative of the gradient for k. If you don't have the line stored like this, you could calculate k as (y2-y1)/(x2-x1)

## @a_m0d 2009-07-03 21:24:36

We don't assume that m is zero; we calculate the gradient first (so that the equation of the line then looks like y=2x+m as an example), and then once we have the gradient we can solve for m by plugging in the center of the circle for y and x.

## @chmike 2009-07-08 06:31:00

I suggest another method below (with code) that uses the triangle area to compute the distance of the circle center to the line.

## @Ivaylo Strandjev 2012-01-22 12:19:52

The sign of b must be the opposite.

## @Hassan 2012-06-01 22:01:16

+1 Awesome explanation! But I think this assumes a line, not a line segment. So, if the nearest point on this line to the circle's center wasn't between points A and B, it would still be counted.

## @chmike 2009-07-07 07:05:25

Another method uses the triangle ABC area formula. The intersection test is simpler and more efficient than the projection method, but finding the coordinates of the intersection point requires more work. At least it will be delayed to the point it is required.

The formula to compute the triangle area is : area = bh/2

where b is the base length and h is the height. We chose the segment AB to be the base so that h is the shortest distance from C, the circle center, to the line.

Since the triangle area can also be computed by a vector dot product we can determine h.

UPDATE 1 :You could optimize the code by using the fast inverse square root computation described here to get a good approximation of 1/LAB.

Computing the intersection point is not that difficult. Here it goes

If h = R then the line AB is tangent to the circle and the value dt = 0 and E = F. The point coordinates are those of E and F.

You should check that A is different of B and the segment length is not null if this may happen in your application.

## @Mizipzor 2009-07-07 11:00:19

I like the simplicity in this method. Maybe I could adapt some of the surrounding code to not need the actual collision point itself, Ill see what happens if I use A or B rather than the calculated point in between.

## @Stonetip 2012-06-21 15:02:13

t = Dx*(Cx-Ax) + Dy*(Cy-Ax) should read t = Dx*(Cx-Ax) + Dy*(Cy-Ay)

## @chmike 2012-06-22 16:17:54

This is right. Thank you for pointing it out. I corrected it in the post.

## @ericsoco 2013-06-01 15:26:03

just edited -- first line calculates triangle area using a

crossproduct, not a dot product. verified with code here: stackoverflow.com/questions/2533011/…## @ericsoco 2013-06-21 18:40:43

note also, the first half of this answer tests for intersection with a line, not a line segment (as asked in the question).

## @Rob 2012-05-01 02:30:42

Just an addition to this thread... Below is a version of the code posted by pahlevan, but for C#/XNA and tidied up a little:

## @bobobobo 2012-11-26 20:34:06

In C#/XNA you can use

`Ray.Intersects(BoundingSphere)`

## @Juozas Kontvainis 2009-07-03 13:59:42

You can find a point on a infinite line that is nearest to circle center by projecting vector AC onto vector AB. Calculate the distance between that point and circle center. If it is greater that R, there is no intersection. If the distance is equal to R, line is a tangent of the circle and the point nearest to circle center is actually the intersection point. If distance less that R, then there are 2 intersection points. They lie at the same distance from the point nearest to circle center. That distance can easily be calculated using Pythagorean theorem. Here's algorithm in pseudocode:

EDIT: added code to check whether found intersection points actually are within line segment.

## @ADB 2010-09-01 14:47:54

You missed one case since we are talking about a line segment: when the segment ends in the circle.

## @Juozas Kontvainis 2010-09-02 06:52:15

@ADB actually my algorithm only works for infinite lines only, not line segments. There are many cases that it does not handle with line segments.

## @msumme 2017-01-13 18:35:29

The original question was about line-segments, not circle-line intersection, which is a much easier problem.

## @pahlevan 2009-07-19 11:12:57

This Java Function returns a DVec2 Object. It takes a DVec2 for the center of the circle, the radius of the circle, and a Line.

## @Martin 2009-07-02 09:20:14

If you find the distance between the center of the sphere (since it's 3D I assume you mean sphere and not circle) and the line, then check if that distance is less than the radius that will do the trick.

The collision point is obviously the closest point between the line and the sphere (which will be calculated when you're calculating the distance between the sphere and the line)

Distance between a point and a line:

http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html

## @Martijn 2009-07-02 09:21:48

It's in 2D, not 3D; as you say, this doesn't really matter

## @Martin 2009-07-02 09:30:20

I'm no mathematician so I thought I'd be better outlining a general approach and leaving it to others to figure out specific maths (although I does look rather trivial)

## @Jason S 2009-07-02 19:03:40

+1 with a strong upvote. (though I would have linked to another site, the pbourke site looks confusing) All the other answers so far are overcomplicated. Although your comment "That point is also the intersection point on the line" is incorrect, there is no point that has been constructed in the computation process.

## @Jason S 2009-07-02 19:05:04

mathworld.wolfram.com/Point-LineDistance3-Dimensional.html and mathworld.wolfram.com/Point-LineDistance2-Dimensional.html are better & from a more reputable site

## @Martin 2009-07-02 21:19:48

I explained a little better about the closest point, and linked to mathworld instead of pbourke :)

## @Gábor Hargitai 2009-07-02 09:24:00

If the line's coordinates are A.x, A.y and B.x, B.y and the circles center is C.x, C.y then the lines formulae are:

x = A.x * t + B.x * (1 - t)

y = A.y * t + B.y * (1 - t)

where 0<=t<=1

and the circle is

(C.x - x)^2 + (C.y - y)^2 = R^2

if you substitute x and y formulae of the line into the circles formula you get a second order equation of t and its solutions are the intersection points (if there are any). If you get a t which is smaller than 0 or greater than 1 then its not a solution but it shows that the line is 'pointing' to the direction of the circle.

## @Martijn 2009-07-02 09:29:10

You'll need some math here:

Suppose A = (Xa, Ya), B = (Xb, Yb) and C = (Xc, Yc). Any point on the line from A to B has coordinates (alpha*Xa + (1-alpha)

Xb, alphaYa + (1-alpha)*Yb) = PIf the point P has distance R to C, it must be on the circle. What you want is to solve

that is

if you apply the ABC-formula to this equation to solve it for alpha, and compute the coordinates of P using the solution(s) for alpha, you get the intersection points, if any exist.