10
$\begingroup$

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.

  • 0
    Thanks for clarifying! I think I (and this question's respondents) can now carry out a thorough analysis.2010-08-20

8 Answers 8

-1

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.

  • 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.)2010-09-25
9

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.

  • 0
    @J. Mangaldan: Solve is doing a very good job: *Mma* has many issues, but its equation solving function deals with quadratic equations with as much grace as can be expected. The "problem" I had is that when having it simplify the condition (that's what Reduce is for) that one of the roots (the first one in the list) be in $[0,1]$, the condition became unmanageable.2010-08-20
7

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.

  • 0
    @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.2010-08-20
3

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

3

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.

  • 0
    Isaac's answer seems to do the same as mine!2010-08-20
2

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.

  • 0
    Oops sorry I forgot to replace h with k in the y elements of B. B would be $B = 2x_{1}x_{2} - 2x_{2}^{2} - 2hx_{1} + 2hx_{2} + 2y_{1}y_{2} - 2y_{2}^{2} - 2ky_{1} + 2ky_{2}$2015-05-13
1

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.

0

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/