Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a line segment, denoted by it's $2$ endpoints $(X_1, Y_1)$ and $(X_2, Y_2)$, and a circle, denoted by it's center point $(X_c, Y_c)$ and a radius $R$, how can I tell if the line segment is a tangent of or runs through this circle? I don't need to be able to discern between tangent or running through a circle, I just need to be able to discern between the line segment making contact with the circle in any way and no contact. If the line segment enters but does not exit the circle (if the circle contains an endpoint), that meets my specs for it making contact.

In short, I need a function to find if any point of a line segment lies in or on a given circle.

EDIT:

My application is that I'm using the circle as a proximity around a point. I'm basically testing if one point is within R distance of any point in the line segment. And it must be a line segment, not a line.

share|improve this question
    
"Line segment" or "line"? How would you want the case of a line segment being entirely inside the circle handled? –  J. M. Aug 19 '10 at 23:31
2  
I do mean a line segment, with a given start and stop. If the Circle entirely contains the line, then it means the line makes contact with the circle. Although in my application this is not possible. I'm using the circle as a proximity around a point. So basically I'm looking for a way to see if one point is within a given distance of any point on the line segment. –  Corey Ogburn Aug 19 '10 at 23:37
1  
It must be a line segment determined by two points. An infinite line will not work. –  Corey Ogburn Aug 19 '10 at 23:42
1  
Now I'm confused... try this: how would a line segment that would have intersected the circle if extended in the right direction be treated? –  J. M. Aug 19 '10 at 23:48
2  
@J. Mangaldan, in that situation, it would not intersect because the line segment itself does not intersect with the circle. –  Corey Ogburn Aug 20 '10 at 14:32
show 3 more comments

8 Answers

Find the intersections of the line containing the segment and the circle. This amounts to solving a quadratic equation. If there are no intersections (i.e. the solutions of the corresponding equation are non-real), then your segment does not intersect the circle. Now, if there are intersections, see whether they are inside the segment or not.

To implement this, let $P$ and $Q$ be the endpoints of your segment and $C$ and $r$ be the center and the radius of your circle. Then every point of the line through $P$ and $Q$ is given by the formula $$t P + (1-t) Q$$ for exactly one value of $t\in\mathbb R$, and the points in the segment are precisely those for which the corresponding $t$ is in the interval $[0,1]$.

Now the point corresponding to $t\in\mathbb R$ is on the circle if and only if $$\langle t P + (1-t) Q - C,t P + (1-t) Q - C\rangle = r^2,$$ where $\langle\mathord\cdot,\mathord\cdot\rangle$ is the usual inner (dot) product of vectors. If you solve this equation—this is easy, as it is a quadratic equation for $t$—, you find the $t$'s corresponding to the points of intersection of the circle and the line, and if at least one of those $t$'s belong to the interval $[0,1]$, then the segment intersects the circle.

Later: I tried to have Mathematica do the computation for me. Assuming $C=(0,0)$ and $r=1$, as we may up to translation and rescaling, and letting $P=(p1,p2)$, $Q=(q1,q2)$, the following computes the $t$'s:

P = {p1, p2};
Q = {q1, q2};
ts = t /. Solve[Norm[t P + (1 - t) Q]^2 == 1, t];

This ends up with the variable ts having the value

$$\left\{\frac{-p_1 q_1-p_2 q_2-\sqrt{p_1^2 \left(-q_2^2\right)-2 p_1 q_1+2 p_2 p_1 q_1 q_2-p_2^2 q_1^2-2 p_2 q_2+p_1^2+p_2^2+q_1^2+q_2^2}+q_1^2+q_2^2}{-2 p_1 q_1-2 p_2 q_2+p_1^2+p_2^2+q_1^2+q_2^2},\frac{-p_1 q_1-p_2 q_2+\sqrt{p_1^2 \left(-q_2^2\right)-2 p_1 q_1+2 p_2 p_1 q_1 q_2-p_2^2 q_1^2-2 p_2 q_2+p_1^2+p_2^2+q_1^2+q_2^2}+q_1^2+q_2^2}{-2 p_1 q_1-2 p_2 q_2+p_1^2+p_2^2+q_1^2+q_2^2}\right\}$$

(This was a huge formula, which will likely not fit on your browser window...) If the expression inside the square roots is negative, there are no real $t$'s, so the line (hence, a fortiori the segment) and the circle are disjoint. If not, now we need to see if at least one of the roots in in $[0,1]$.

If I now tell Mma to tell me when then first of the roots is in $[0,1]$, by telling her to compute

Reduce[0 <= ts[[1]] <= 1, Reals]

it works for a while, and comes up with a huge answer, presumably equivalent to the original

0 <= ts[[1]] <= 1

Can anyone make sense of the huge answer? (if one asks instead for the more meaningful

Reduce[0 <= ts[[1]] <= 1 || 0 <= ts[[2]] <= 1, t, Reals]

the same thing happens)

PS: Please notice that I have made absolutely no attempt at being fast or particularly smart with this idea: it is just the straightforward was to set up the problem and solve it.

share|improve this answer
    
I got momentarily confused with the last formula until I realized you meant $\|tP+(1-t)Q-C\|_2=r$ ... :D –  J. M. Aug 19 '10 at 23:55
1  
I'm not much of a math person, I dabble in it, but I must admit that your notation is above my head. Layman's terms? –  Corey Ogburn Aug 20 '10 at 0:07
    
Two tiny notes: you did not have to square Norm[], and why did the multiplier for Q become (t-1)? –  J. M. Aug 20 '10 at 0:11
    
@J. Mangaldan, the $(t-1)$ was a typo copying the $Mma$ code here; I squared the norm because it is simpler for the computer to deal with the equation (and equivalent, of course :) ) –  Mariano Suárez-Alvarez Aug 20 '10 at 0:16
    
For common input distributions it is faster to check a bounding box before solving the quadratic. –  Dan Brumleve Aug 20 '10 at 5:55
show 4 more comments

Maybe this is what you are getting at... Given a line through points $(x_1,y_1)$ and $(x_2,y_2)$, and given a single point $p$ not necessarily on the line, we want to find out: If we draw a circle of radius $r$ around $p$, does that circle intersect the line?

If this is what you want then you are looking for the perpendicular distance from the point to the line.

The derivation on MathWorld may not be want you want to look at right now considering your stated familiarity with so many symbols - so let's just get right down to it.

Given that your line passes through the two points $(x_1,y_1)$ and $(x_2,y_2)$, a point $(a,b)$ not necessarily on the line, and some radius $r$ around the point $(a,b)$, in order to see if your point $(a,b)$ is within $r$ from the line, you need to check

if $r \geq \frac{|(x_1 - x_2)(a-x_1) + (y_2 - y_1)(b-y_1)|}{\sqrt{(x_1-x_2)^2 + (y_2-y_1)^2}}$

then $(a,b)$ is within $r$ of the line (taken as an orthogonal distance).

EDIT: I don't think this will work if you are working with just a line segment... This solution assumes your line is extended infinitely in both directions. (update: there are scenarios where this would fail) I think the case of the segment itself being further away than $r$ can be taken care of in cases before you arrive at the "if" statement above. It should be something along the lines of

if $r \leq \sqrt{(x_1 - a)^2 + (y_1 - b)^2}$ or $r \leq \sqrt{(x_2-a)^2 + (y_2 - b)^2}$

then the segment is too far away to even consider checking the longer inequality above. (again, the previous if/then is insufficient... still thinking)

Final Edit: This approach has been adapted and completed far more satisfactorily by Isaac. I will offer a second approach that may be exactly what Mariano did, but I'll try to keep it short sweet and simple.

share|improve this answer
1  
If I understand correctly what you say, it seems that a segment containing the center of the circle with endpoint outside the circle would pass your test: both distances between the points and the center are bigger than $r$, so that you do not check the condition in the original post... am I right? –  damiano Aug 20 '10 at 11:19
    
@damiano: I don't follow you exactly, but if you are referring to any part of this answer past the first EDIT then you are correct that it is wrong! –  Tom Stephens Aug 20 '10 at 13:37
    
I see now that you have a further edit: I will wait to see a final version! –  damiano Aug 20 '10 at 13:54
    
@damiano: I have essentially given up in this strategy. It seems that just examining distances will require a long list of cases. I went algebraic in an alternative to this answer. –  Tom Stephens Aug 20 '10 at 16:29
add comment

If I understand your edit correctly, you have a point $C=(x_c,y_c)$ and the line segment with endpoints $P=(x_1,y_1)$ and $Q=(x_2,y_2)$ and you want to know whether or not $C$ is within a distance $r$ of any point on the line segment $\overline{PQ}$.

Working from Tom Stephens's answer, let's look at the whole line $\overleftrightarrow{PQ}$ containing the line segment $\overline{PQ}$. The distance between $C$ and $\overleftrightarrow{PQ}$ is $d=\frac{|(x_1 - x_2)(x_c-x_1) + (y_2 - y_1)(y_c-y_1)|}{\sqrt{(x_1-x_2)^2 + (y_2-y_1)^2}}$.

(1) If $d>r$, then $C$ is too far from $\overleftrightarrow{PQ}$ to be within $r$ of any point on $\overline{PQ}$, finished.

If $d\le r$, then $C$ is close enough to $\overleftrightarrow{PQ}$, but may not be close enough to $\overline{PQ}$. $d$ is the perpendicular distance from $C$ to $\overleftrightarrow{PQ}$. Consider two cases—first, that $C$ and $\overline{PQ}$ are arranged such that the perpendicular distance is to a point on $\overline{PQ}$; second, that the perpendicular distance is to a point not on $\overline{PQ}$.

(2) In the first case, $\angle PQC$ and $\angle QPC$ each have measure ≤90°, so the cosine of each angle must be nonnegative so $\frac{(x_1-x_2)^2-(x_1-x_c)^2+(x_2-x_c)^2+(y_1-y_2)^2-(y_1-y_c)^2+(y_2-y_c)^2}{2\sqrt{((x_1-x_2)^2+(y_1-y_2)^2)((x_2-x_c)^2+(y_2-y_c)^2)}}\ge 0$ and $\frac{(x_1-x_2)^2+(x_1-x_c)^2-(x_2-x_c)^2+(y_1-y_2)^2+(y_1-y_c)^2-(y_2-y_c)^2}{2\sqrt{((x_1-x_2)^2+(y_1-y_2)^2)((x_1-x_c)^2+(y_1-y_c)^2)}}\ge 0$ (from the Law of Cosines). [ edit 2: After a more careful reading of damiano's answer, it occurred to me that these are much more hideously complicated than necessary. The denominators do not affect the sign at all and the numerators are somewhat simpler when expanded, so the two inequalities can be replaced by: $x_1x_2-x_1x_c+x_2x_c-x_2^2+y_1y_2-y_1y_c+y_2y_c-y_2^2\ge0$ and $x_1x_2+x_1x_c-x_2x_c-x_1^2+y_1y_2+y_1y_c-y_2y_c-y_1^2\ge0$. These are more clearly equivalent to damiano's vector-dot-product criteria. ] If both of these inequalities hold, then $d\le r$ is the distance from $C$ to $\overline{PQ}$, so $C$ is within $r$ of $\overline{PQ}$.

(3) If those two inequalities from the Law of Cosines do not both hold, then $d$ is not the distance from $C$ to any point on $\overline{PQ}$, so the shortest distance from $C$ to any point on $\overline{PQ}$ is the distance to the closer of $P$ and $Q$: $d'=\min(\sqrt{(x_1-x_c)^2+(y_1-y_c)^2},\sqrt{(x_2-x_c)^2+(y_2-y_c)^2})$. If $d'\le r$, then $C$ is within $r$ of $\overline{PQ}$.

edit (adding the numbers above, also):

Given Corey Ogburn's answer, I thought it might be helpful to add a diagram and discuss what parts of my original answer address which regions. The numbers below discuss the correspondingly-numbered part of my original answer, above.

diagram

(1) If $d>r$, then the point $C$ is in the beige region.

(2) $d\le r$, so if $\angle PQC$ and $\angle QPC$ each have measure ≤90°, then $C$ is in the purple region.

(3) $C$ is not in the beige or purple regions, so we only need to see whether it's in the blue or red regions (based on whether $C$ is close enough to the endpoints of the segment).

share|improve this answer
add comment

If I understood what you want correctly, you need to find conditions on a line segment so that it lies entirely outside a circle; a possible reason for confusion is that mathematicians tend to call "circle" just the one-dimensional boundary of the "disk" and they call "disk" its interior. In this terminology, I think that you want the segment to lie completely outside of the closed disk; this is the question that I will an answer.

First, a geometric description of the answer. Let $P$ and $Q$ be the endpoints of the segment, let $C$ be the center of the circle and let $r$ be the radius of the circle $C$.

1) We rule out the possibility that at least one among $P$ and $Q$ is contained inside the closed disk.

2) If in the triangle $PQC$ one of the two angles on the segment $PQ$ is not acute, then moving along the segment $PQ$ and away from the non-acute angle the distance from the center $C$ increases, so that there is no intersection in this case because of 1). Otherwise, the two angles on the segment $PQ$ are acute, so that the minimum distance between the center $C$ and the points on the segment $PQ$ is achieved inside the segment. In this case (i.e. when the two angles on $PQ$ are acute), we make sure that the distance between the center $C$ and the line joining $P$ and $Q$ is larger than $r$. In view of 1) and the previous discussion this implies that there is no contact between the segment and the disk.

Translation into formulas:

1) $dist(P,C)>r$ and $dist(Q,C)>r$;

2) if the inequalities $PC \cdot PQ > 0$ and $QC \cdot QP > 0$ hold, then also the inequality $||PC \times PQ|| > r ||PQ||$ must hold (in the formulas, we denote by $\cdot$ the scalar product, by $\times$ the cross product, and by $||-||$ the length of a vector).

Explicit equations, assuming that $C$ is the origin (which you can always achieve by translations):

1) $x_P^2+y_P^2 > r^2$ and $x_Q^2+y_Q^2 > r^2$;

2) if both $x_P^2 + y_P^2 \geq x_P x_Q + y_P y_Q$ and $x_Q^2 + y_Q^2 \geq x_P x_Q + y_P y_Q$ hold, then check that also $(x_Py_Q-x_Qy_P)^2 > r^2 ((x_P-x_Q)^2 + (y_P-y_Q)^2)$ holds.

share|improve this answer
    
Isaac's answer seems to do the same as mine! –  damiano Aug 20 '10 at 11:44
add comment

Well, what the heck... there has been so much virtual ink spilled at this point that what's another gallon, really?

(update: This is precisely the solution Mariano proposed long before I did, it just happens that I couched this in a different notation.)

The principle behind this approach is that we can find out algebraically whether the set of coordinates defining the perimeter of a circle with center $(h,k)$ and radius $r$ contains any point of the line segment connecting the points $(x_1,y_1)$ and $(x_2,y_2)$.

In other words, writing the set of points $(x,y)$ lying along the line segment as $$tx_1 + (1-t)x_2 = x$$ $$ty_1 + (1-t)y_2 = y$$

where $t$ ranges between $0$ and $1$ inclusive, and writing the equation for the circle centered at $(h,k)$ with radius $r$ as $$(x-h)^2 + (y-k)^2 = r^2,$$

then we can simply substitute our expressions for $x$ and $y$ into the equation for the circle, and then figure out if there at least one such $t \in [0,1] \subset \mathbb{R}$. If there is, then the perimeter of the circle and the line segment share at least one point.

Since we agreed that we have seen enough virtual ink today, I will simply write down what that substitution looks like and then the final computation that needs to be done.

The substitution:

$$\left(tx_1 + (1-t)x_2 - h \right)^2 + \left(ty_1 + (1-t)y_2 - k \right)^2 = r^2.$$

(This is a quadratic equation in $t$, note that the values of $x_1,x_2,y_1,y_2,h,k,$ and $r$ are known.)

The computation: $$At^2 + Bt + C = 0$$ with

$A = x_{1}^{2} - 2x_{1}x_{2} + x_{2}^{2},$
$B = 2x_{1}x_{2} - 2x_{2}^{2} - 2hx_{2} + 2hx_{2},$ and
$C = x_{2}^{2} - 2hx_{2} + h^{2} - r^{2}.$

Solve for $t$ using the quadratic formula and then test whether at least one $t$ is a real number between $0$ and $1$, inclusive.

PS: If I have stomped on another's solution that has already been posted it is because I have not done due diligence and verified all of the solutions given previously. Please let me know in the comments.

share|improve this answer
    
If the segment $PQ$ is entirely contained in the circle, you will not find a value of $t$ in the interval $[0,1]$, but the configuration should be nevertheless discarded. You have to check that if there are real solutions to the degree two equation, then the two endpoints are on the same side with respect to the interval between the solutions. Besides, shouldn't the coefficient $A$ be the square of the distance between the two points? –  damiano Aug 20 '10 at 16:41
    
@damiano: I agree that if the segment lies entirely in the circle this is useless. The coefficient $A$ is just the collection of all terms with a factor of $t^2$ after I did the algebra on the substitution... I hope that was correct because it was about a page of junk! Thank you for continuing to look over my answers (seriously). –  Tom Stephens Aug 20 '10 at 18:47
add comment

There are too many answers already, but since no one mentioned this, perhaps this might still be useful.

You can consider using Polar Coordinates.

Translate so that the center of the circle is the origin.

The equation of a line in polar coordinates is given by

$r = p \sec (\theta - \omega)$

See the above web page for what $\omega$ is. You can compute $p$ and $\theta$ by using the two endpoints of the segment.

If R is the radius of the circle, you need to find all $\theta$ in $[0, 2\pi]$ such that

$R = p \sec (\theta - \omega)$

Now all you need to check is if this will allow the point to fall within the line segment.

share|improve this answer
add comment
up vote -1 down vote accepted

Dear God you guys over complicated things...

Not being a math expert along the lines of you guys, I set the problem down and came back to it later. Upon looking it over again, I realized I could really simplify this by using the given data to look at it as different geometry. Instead of a line segment and a circle and testing for intersection, I used the radius of the circle to convert the line to a rectangle and then checked if the center of the circle (as just a point, no longer as a circle) is inside the new rectangle. Line Circle Intersect Using New Geometry

Please excuse my rectangle not having perfect dimensions.

EDIT:

Although my answer meets my needs for my specific application, to better answer my own question, about the semi circles at the end of the rectangle (to test if an endpoint of the line segment is contained in the circle), I can compare the distance between an endpoint and the center of the circle, if that distance is less than the radius of the circle, the circle contains the end point.

My application was for a Tower Defense game. The line represented some sort of laser stretched across the trail that enemies (the circle) would walk past, I needed to know when the laser contacted the enemy. The laser endpoints are attached to towers that are not positioned on the path the enemy walks down, so the enemy's circle could not contain an endpoint. I realize I was unclear during the original question about some of these details.

share|improve this answer
3  
This misses the cases where the center of the circle is outside your rectangle, but close enough to the endpoints of the line segment to be within R of the line segment. That is, there should be semicircles added at the 2R-long sides of the rectangle. –  Isaac Sep 22 '10 at 18:33
1  
Ahh, given your application, yes, methods like my full answer are overkill. I don't know how you specifically implemented the test in the end, but given the coordinates of the point and the endpoints of the line segment, the explicit formula for the distance between that point and the line containing the segment would make for a relatively simple-to-program test. (This is the step labeled (1) in my answer, using the formula immediately above that step.) –  Isaac Sep 25 '10 at 21:41
add comment

This dude have some nice info about this topic! Click his name to see more math stuff.

http://local.wasp.uwa.edu.au/~pbourke/geometry/sphereline/

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.