Calculate line intersecting most points, based on random points in a grid

Question

I have been struggling with a math issue for a game I've been developing. I am in need to find the best starting and ending point for a straight line so that it intersects most of the circles (the blue one always needs to be intersected).

As you can see in the image below I want to be able to calculate that green line based on the given points, where the blue one is required to be intersected. The rule is that the line has to intersect as many circles as possible and should always intersect the blue circle.

I've tried to apply the best fit algorithm but that doesn't really takes intersection into consideration. Would appreciate if someone could help me out solving the math for this.

There will only ba a maximum of 5 circles while calculating the line.

Note: I am not deeply involved into math, only know the basic symbols for it.

Answer 1

If there are at most 5 circles to be considered the problem can be solved easily.

Given a subset of circles, you just have to check if you can find a line that intersects all of them. we can safely assume, if such a long exists, it's going to be the one best fitting the center of circles (in case circles all have same radius which seems to be the case in your picture).

Iterating over the subsets of all the circles is an easy task too, you just have to count from 0->2^n - 1 (like 0 to 31 in case of just 5 circles). Each bit of the number determines if a certain circle is present in subset or not.

So here is an algorithm in a whole:

counting from 0 to 31
    determine a subset of circles that you are going to check
    find the best fitting line for those set of circles
    check if the best fitting line intersects with all of the circles
    if all of the circles are on the line, update the chosen line.

Answer 2

It's not very pretty, but assuming there is only one blue circle, you could:

Create a line that goes through the blue's center, incrementally rotate it around the center, at each angle check how many circles coincide with the line, and finally pick the best one.

If you have to do this once, or at least not very often, this will work out fine.