Circle-Line Intersection

Question

Problem Statement
Given radius $r$ of a circle centered at the origin and a line on which two points $(x1,y1)$ and $(x2,y2)$ lie, determine whether the line intersects the circle at any point.

I'm having trouble understanding the intuition behind MathWorld's formula for this problem. For example, how is the determinant of the column matrix $D$ relevant in finding the answer?

Answer 1

For convenience, let's name the two points on the line and the origin: $A = (x_1,y_1),$ $B = (x_2,y_2),$ and $C=(0,0).$ Then the magnitude of the determinant $D = \begin{vmatrix}x_1&x_2\\y_1&y_2\end{vmatrix}$ is twice the area of the triangle $\triangle ABC.$

But the area of $\triangle ABC$ is $\frac12 d_r h,$ where $d_r$ is the length of the segment $AB$ and $h$ is the distance of $C$ from the infinite line through $A$ and $B.$ So $\lvert D\rvert = d_r h,$ and we can eliminate the need for the absolute value by squaring both sides of the equation: $D^2 = d_r^2 h^2,$ and therefore $h^2 = {D^2}/{d_r^2}.$

Note that we have the following cases:

Case $r^2 d_r^2 - D^2 = 0.$ Then $r^2 = {D^2}/{d_r^2} = h^2,$ and the infinite line $AB$ is tangent to the circle of radius $r.$

Case $r^2 d_r^2 - D^2 > 0.$ Then $r^2 > {D^2}/{d_r^2} = h^2,$ that is, the radius of the circle is greater than the distance to the line, and the infinite line $AB$ intersects the circle of radius $r$ twice.

Case $r^2 d_r^2 - D^2 < 0.$ Then $r^2 < {D^2}/{d_r^2} = h^2,$ and the infinite line $AB$ does not intersect the circle of radius $r$ even once.

That does not explain all the details of the formulas, but it seems like a good reason why the determinant might show up there.

Answer 2

The problem you describe is well studied and often applied with ray-tracing. However, I find the solution they describe on MathWorld not the most intuitive one, see also another post at math.stackexchange. Below I describe how I would do this.

Let $\bf{p}=\begin{bmatrix}x_1 & y_1\end{bmatrix}^T$ and $\bf{q}=\begin{bmatrix}x_2 & y_2\end{bmatrix}^T$ your endpoints. Then we are interested whether the line $\bf{t}(\lambda)=\bf{p}+\lambda\bf{d}$ with $\bf{d}=\bf{q}-\bf{p}$ hits the circle with radius $r$. Furthermore, because $\bf{p}$ and $\bf{q}$ are endpoints, we need $0 \leq \lambda \leq 1$. The line $\bf{t}(\lambda)$ hits the circle when the dot product $\bf{t}(\lambda)\cdot\bf{t}(\lambda)$ equals $r^2$. Thus, we can write: \begin{align} (\bf{p}+\lambda\bf{d})\cdot(\bf{p}+\lambda\bf{d}) &= r^2, \\ \lambda^2\bf{d}\cdot\bf{d}+\lambda\cdot 2 \bf{p} \cdot\bf{d}+\bf{p}\cdot\bf{p}-r^2 &=0,\\ a\lambda^2+b\lambda+c&=0, \end{align} With $a=\bf{d}\cdot\bf{d}$, $b=2 \bf{p}\cdot\bf{d}$ and $c=\bf{p}\cdot\bf{p}-r^2$. Now we end up with our standard quadratic formula, which you can solve as follows: \begin{align} D=b^2-4ac, \\ \lambda = \frac{-b \pm \sqrt{b^2-4ac}}{2a}. \end{align} If case $D<0$, then the line through $\bf{p}$ and $\bf{q}$ never hits the circle. If $0<\lambda<1$, then the line hits the circle between $\bf{p}$ and $\bf{q}$.

Answer 3

Here’s one way that a determinant can sneak into the formulas you cite: Working in homogeneous coordinates, the line through the two points is given by the cross product $$\mathscr l = [x_1,y_1,1]\times[x_2,y_2,1]=[y_1-y_2,x_2-x_1,x_1y_2-x_2y_1]$$ and the distance of this line from the origin can be found by the usual distance formula $${|x_1y_2-x_2y_1|\over\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}} = {|D| \over d_r}.$$ Squaring and comparing to $r^2$ yields the table in the article you cite.

I must point out, however, that those formulas are for the intersection of a line with a circle centered on the origin, not for a line segment as in your question. You must also determine whether or not the intersection points lie within the segment. If all you want to do is to detect an intersection rather than finding the actual intersection point(s), then you simply need to compare the distances of the two points from the origin. If one distance is less than or equal to $r$ and the other is greater than or equal to $r$, then you have an intersection. (For efficiency, you can of course compare the squares of the distances instead.)

On the other hand, if, contrary to what you’ve stated in your question, you want to know the actual intersection points, then you can certainly use the cited formulas (or find the solution in a slightly different way, such as described in EdG’s answer or here), but you’ll also need to check that the computed points lie on the segment.