# Algorithm to find a line segment is passing through a circle or not?

I have a line segment between two points P1 (X1,Y1) and P2 (X2,Y2). And I have a circle at point Q(Xq , Yq) with radius R . Can I have an equation in which I can put these values and the result shows me either that line segment passes through the circle or not.

Any help would be greatly appreciated. Thanks in advance.

• What is a circle at a point? Centred at that point? By a line segment through the circle, I suppose you mean a line segment that intersects the circle? – Bernard Jun 8 '15 at 8:44
• we dont know line segment intersects the circle or not, this what we need to find out. And yes Circle is centred at point Q. – M Abdul Sami Jun 8 '15 at 9:05
• M Abdul Sami -- I saw your comment on my answer and deleted it, since it's now clear you want the line segment to cross the circle at some point between the ends of the segment. Do you also count as an intersection when the line segment is entirely inside the circle, not crossing the boundary of the circle? – coffeemath Jun 8 '15 at 10:00
• yeah that is an intersection too if the line is entirely inside the circle. – M Abdul Sami Jun 8 '15 at 15:27
• Separate the problem into 3 questions. First, find the equation of the circle and the line. Second, find the intersection points of those 2 equations. Third, determine if the intersection points are between P1 and P2. Which part can you not do? – DanielV Jun 9 '15 at 21:43

## 2 Answers

Here is another suggestion.

1. Form the equation of the straight line $P_1P_2$, which is an equation involving $x, y, x_1, y_1, x_2, y_2$.

2. Calculate $d$, the perpendicular distance of $P_1P_2$ from $Q$, which is an expression involving $x_1, y_1, x_2, y_2, x_q, y_q$

3. Do $R – d$, and make appropriate conclusion.

Added the following further detection mechanism

If d > R, there will be no intersection at all.

We now concentrate on the case when d < R and discuss the various types of the “could-be” intersections

Type-1 If both $O_1P_1 – R$ and $O_1P_2 – R$ are negative, then the line segment lies completely inside the circle and therefore there is no intersection.

Type-2 If $(O_1P_1 – R)*(O_1P_2 – R)$ is negative, then there is an intersection.

Type3 and Type-4 together

They both have the characteristic of both $O_1P_1 – R$ and $O_1P_2 – R$ are positive. Using the standard result of 2-point survey, we have

$$\frac {L}{d} = (\frac {1}{\tan \beta} - \frac {1}{\tan \alpha})$$

Re-arranging terms, we have $$\tan \alpha = (\frac {1}{\tan \beta} - \frac {L}{d})^{-1}$$

Substituting the values in it and if $\tan \alpha$ is positive, we have Type-3 result. That is no intersection.

Otherwise is Type-4 with two intersection points.

Note-1 With the values given, one can always determine which angle is $\beta$.

Note-2 The tangential case can be treated in a similar fashion, and hence skipped.

• In my answer the $d$ you mention is obtainable as $|s|\cdot d(P_1,P_2)$ with $s$ from relation $(2).$ I also think one needs to know not only $d$ but also whether that distance is realized for some point on the segment $P_1P_2.$ – coffeemath Jun 15 '15 at 3:49
• @coffeemath The sign of (R – d) is sufficient to determine whether there are intersection (between the line and the circle) or not explicitly. – Mick Jun 15 '15 at 4:06
• Agreed, if e.g. $R-d<0$ so $R<d$ then the entire circle of radius $R$ lies strictly on one side of the line, so the entire line doesn't meet the circle, thus neither does the segment. However there are cases where $d<R$ yet the two points determining the line segment may ether lie on the "same side" of the circle and each be outside the circle (so no intersection), or on the other hand the segment endpoints could lie on different sides of the circle and outside it, but there would then be a point on the segment realizing the distance $d$ so in that case the segment does meet the disc. – coffeemath Jun 15 '15 at 10:08
• @coffeemath It is hard to discuss different opinions via word description only. I have uploaded a picture. Through which may be our discussion can continue. – Mick Jun 15 '15 at 12:26
• @coffeemath After our discussion, I have the detection mechanism added. – Mick Jun 16 '15 at 5:46

In a comment, the OP has made clear that the question is whether a given line segment has any points in common with the closed disc of radius $R$ centered at some given point. We may as well translate the coordinates so that the center of the disc is at the origin $(0,0)$ [that is, the coordinated $(X_q,Y_q)$ are initially subtracted from each of $P_1,P_2,Q.$] Let $A,B$ denote the coordinates of the endpoints of the segment, regarding each of them as a complex number. This just makes the computations come out easier.

Firstly, the set of points on the segment with endpoints $A,B$ are those of the form $A+t(B-A)$ where $0 \le t \le 1.$ Also, a vector normal to the vector $B-A$ is given by $i(B-A)$ (here $i$ is the complex unit). So the point where the line through points $A,B$ meets the normal to that line through the origin satisfies $$A+t(B-A)=s \cdot i(B-A).\tag{1}$$ Solving this gives $$-t+is=\frac{A}{B-A}.\tag{2}$$

Now for the problem we may as well assume both of the points $A,B$ are further than $R$ from the origin, else the answer is the segment does meet the disc. Then from there we compute $t$ from $(2)$ and see if it lies in the interval $[0,1].$ If it does not, (recall assuming now each of $A,B$ outside the disc) there is no intersection. If on the other hand $t \in [0,1]$ we may plug $s$ into the right side of $(1)$ so as to find its distance to the origin, and then finally whether that closest point on the line $AB$ (which by our assumption about $t$ actually lies in the segment $AB,$ happens to lie inside the disc. If it does of course, the segment intersects the disc, but if it does not, the segment has no points in common with the disc.

This may be a bit hasty to follow, and I will supply more detail if needed.