Counting how many circles will line segment cross

Question

so I have x circles, given by X,Y coordinates + radius.

I'm unsuccessfully trying to figure out, how to make an algorithm for counting how many circles will line segment cross. For illustration: 1 (Green line crossed 2 circles, red line crossed 1)

I know the starting and ending points of line segments + circles as stated before. Tried to solve it with vector distance equation. The code i wrote was like this (Already googled answers):

for(int i = 0; i<d;i++)
{
        for (int j = 0; j<s; j++)
        {
            int x1 = lines[i][0];
            int x2 = lines[i][2];
            int y1 = lines[i][1];
            int y2 = lines[i][3];
            double x21 = x2-x1;
            double y12 = y1-y2;
            double x12 = x1-x2;
            double y21 = y2-y1;
            double x0 = rooms[j][0];
            double y0 = rooms[j][1];
            double numerator = abs((x21*x0)+(y12*y0)+(x12*y1)+(y21*x1));
            double enumerator = sqrt(pow(x21,2)+pow(y12,2));
            double s = numerator /enumerator ;
            double r = rooms[j][2];
            if (s<=r) {
                count++;
            }
        }
}

, but the code didn't work.

Answer 1

If we have a circle with centre at $C(x,y)$, radius $r$ and line determined by two points $A(x_1, y_1)$ and $B(x_2, y_2)$ we can determine if the line cross the circle using the following algorithm:

1. Calculate the lengths of $AB$, $AC$ and $BC$
2. Calculate the area $P$ of the triangle $ABC$ (for example using Heron's formula)
3. $h=\frac{2 P}{|AB|}$
4. The line intersects with the circle iff $h\leq r$

Python script:

import math

circles = {}
circles[0]=[1.0,1.0,2] 
circles[1]=[0.0,0.0,1]

def circlesCount(x1,x2,y1,y2):
  counter=0
  for cir in circles:
    ci=circles[cir]
    # first we take sides length of the triangle
    a= math.sqrt((x1-y1)**2+(x2-y2)**2)
    b= math.sqrt((x1-ci[0])**2+(x2-ci[1])**2)
    c= math.sqrt((ci[0]-y1)**2+(ci[1]-y2)**2)
    # using heron formula calculate the area of triangle
    p= (a+b+c)/2
    P1=math.sqrt(p*(p-a)*(p-b)*(p-c))
    h=2*P1/a
    if h<=ci[2]:
      counter+=1
  return counter

print circlesCount(0,1,2,2)
print circlesCount(10,1,5,5)

Answer 2

WLOG, the line segment goes from $(0,0)$ to $(0,L)$ (otherwise, translate/rotate to make is such).

Then for every circle, solve

$$\begin{cases}(x-x_c)^2+(y-y_c)^2\le r^2,\\y=0.\end{cases}$$

There is a solution provided

$$(x-x_c)+y_c^2\le r^2,$$ i.e. $$|y_c|\le |r|.$$

Then check if $$\left[x_c-\sqrt{r^2-y_c^2},x_c+\sqrt{r^2-y_c^2}\right]\cap[0,L]\ne\emptyset,$$ or

$$-\sqrt{r^2-y_c^2}\le x_c\le L+\sqrt{r^2-y_c^2}.$$