Given a point P and a circle, how to check if segment (0,0) to P intersects the circle?

Question

Suppose I am at $(0,0)$.

Given a point $P$, I want to know if it is in the blue region or in the red.

In other words, I want to know if a segment from $(0,0)$ to $P$ will intersect a given circle.

I don't need to know where it intersects. I want to answer if this segment intersects the circle in the quickest way possible (less operations), for a computer program execution.

I'm wondering if there is a quicker way of checking this other than taking the distance from point to line and comparing with the radius.

Answer 1

Given the center of the circle $C =(C_x, C_y) $ and its radius $r$, its Cartesian equation is

$ (x - C_x)^2 + (y - C_y)^2 = r^2 $

Now by connecting $P = (P_x, P_y)$ to the origin, the parametric equation of the line segment $OP$ is

$p(t) = t P = (t P_x, t P_y) $, where $ 0 \le t \le 1 $

Find the intersection of this line segment with the circle by substituting the $x$ and $y$ coordinates of $p(t)$ into the equation of the circle, this gives

$( t P_x - C_x)^2 + (t P_y - C_y)^2 = r^2 $

And this simplifies to

$ a_2 t^2 + a_1 t + a_0 = 0 $

with

$ a_2 = P_x^2 + P_y^2 , \ a_1 = - 2 ( P_x C_x + P_y C_y ) , \ a_0 = C_x^2 + C_y^2 - r^2 $

The discriminant of this quadratic equation is

$ \Delta = a_1^2 - 4 \ a_2 \ a_0 $

If $\Delta \lt 0 $ then there is no intersection between the segment and the circle, so $P$ must be in the blue region.

If $\Delta = 0 $ , then there is only one solution for $t$, and that solution is

$ t_0 = - \dfrac{a_1}{2 a_2} $

In this case, if $t_0 \gt 1$ then $P$ is in the blue region, otherwise, $P$ is on the straight boundary between the red region and the blue region

If $\Delta \gt 0 $, then there are two solutions

$ t_1 = \dfrac{ - a_1 - \sqrt{\Delta} }{2 a_2} $

$ t_2 = \dfrac{ - a_1 + \sqrt{\Delta} }{2 a_2 } $

These two values correspond to the intersections of the line segment (or its extension) with the circle. Since $a_2 \gt 0 $ , then $t_1 \lt t_2 $.

Now, if $t_1 \lt 1$ then $P$ lies in the red region. If $t_1 \gt 1$ then $P$ lies in the blue region.

Answer 2

say point $P$ is $(a, b)$.

What is the equation of the line passing through $(a, b)$ and $(0, 0)$. Must be $y = mx$, where $m$ is the slope.

You know the equation of the circle: $(x - c)^2 + (y - d)^2 = r^2$

If they intersect there must be a point (u, v) that satisfies both equations.

Answer 3

I ended up solving this problem splitting it in two steps. The first step to cover the inner part of the circle and the second step to cover the outer part.

Step 1: Checking $distance(P,O) \le r$. This would cover this region:

Step 2: To cover the remaining region, I needed to take the distance from the line formed by $(0,0)$ and $P$ and the circle's origin $O$. For this, I used the vector notation of a line:

$$P_t = P_0 + dt$$

Where $P_0$ is a point in the line, $d$ is the normalized directional vector of the line and $P_t$ is the target point in time $t$.

Given this notation, the distance between the line and $O$ can be evaluated by the formula

$$distance(P_0 + dt, O) = ||(O-P_0) - ((O-P_0)\cdot D)D||$$

As we know $(0,0)$ is in the line, we could reduce it to

$$distance(P_0 + dt, O) = ||O - (O\cdot D)D||$$

We know that the direction $d$ is $P - (0,0)$ normalized, which is just $\hat{P}$ (seeing $P$ as a vector and normalizing it).

$$distance(P_0 + dt, O) = ||O - (O\cdot \hat{P})\hat{P}||$$

So, in the end, we ask $||O - (O\cdot \hat{P})\hat{P}|| \le r$ and if $||P|| >= ||O||$. This would cover this region:

---

In a nutshell, $P$ is in the red region if

• $distance(P,O) \le r$ or

• $||O - (O\cdot \hat{P})\hat{P}|| \le r$ and if $||P|| >= ||O||$