Check if segment crosses circle

Question

I have 2 points $p_1$ and $p_2$ in a $2D$ plane. There are $N$ balls of radius $r$ scattered in the plane. I want to know which balls will be crossed by the segment $p_1 \rightarrow p_2$.

I did it using line-point distance, but obviously, when checking the balls, some of them who are not crossed by the segment are giving me false-positives, since they are crossed by the line formed from the points $p_1$ and $p_2$.

Given $p_1$, $p_2$, $r$ and the position $(x,y)$ of a ball, how can I know if this ball is crossed by the segment?

In the image below, the green balls are crossed while the reds are not.

Answer 1

Checking the distance center-of-circle to line being less than radious is a good method.

To get only intersections with the segment, not the line, for those circles who intersect the line check also the distances from the center to both points $p1,p2$ to be less than radious.

Answer 2

Using coordinates, write $p_1=(x_{p_1},y_{p_2})$ and similarly for $p_2$. Now, you can parametrize the points of the segment between the two poins in this way: \begin{equation} p=\lambda(p_2-p_1)+p_1 \end{equation}

whith $\lambda\in[0,1]$ a parameter. This means that each point $p$ of the segment is written as \begin{equation} p=(\lambda(x_{p_2}-x_{p_1})+x_{p_1}, \lambda(y_{p_2}-y_{p_1})+y_{p_1}). \end{equation}

Now, take a ball of center $(x,y)$ and radius $r$, compute its equation $(X-x)^2+(Y-y)^2=r^2$ and simply substitute the coordinates of the generic parametrized point $p$ inside the equation. The only variable now is the parameter $\lambda$, and the equation is quadratic. If this equation has some solution for $\lambda\in[0,1]$, the segment intersects the ball, otherwise not.

Answer 3

I was able to solve it by drawing a rectangle of height $2r$ and width $||p_2 - p_1||.$ If the center of a ball is inside the rectangle, it means the segment crosses it.