I have a list of circles (x, y, radius) and a line origin (x, y), I want to be able to determine a line segment that intersects as many circles as possible with one of it's points being the line origin, the line is completely straight. This is all in 2D.

Circles have a fixed radius and can overlap. There is no minimum distance that the line has to intersect with the circle.

An image of what I want: https://i.imgur.com/RNgQlh5.png

Psuedocode is fine.

CodePudding user response：

As suggested by @Stef, compute the angles (on fourquedrants) of all tangents to the circle from the line origin. Tag the angles with 1 and -1 in the trigonometric rotation order, and sort them increasingly. Ignore the circles that surround that origin.

Now form the prefix sum of the ±1 tags and consider the angular interval that yields the largest value.

To get the angles for a circle, compute the polar argument of the center and add plus or minus the half aperture, the sine of which is the ratio of the circle radius over the distance center-origin.