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

Question

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.

Answer 1

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.

Answer 2

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.