Finding intersection points of circle and grid efficiently

Question

What's a good method to find the intersection points of a circle defined by it's center point and radius and an arbitrary grid?

An illustration of the points I am trying to find:

Possible solutions I have thought of so far:

1. Find all the lines that lie between center +- radius. For each line calculate the intersection points.

2. Make the circle an n sided polygon and use a geometry library to find the intersection points between the polygon and grid lines. This would allow using other shapes other than circles as well.

Answer 1

It seems reasonable to iterate through sets of coordinates of lines, finding the intersection of each grid line with the circle. However, to avoid ill-conditioned calculations, one should sometimes use y-line, and sometimes x-line, coordinates as the independent variable. Specifically, divide the circle into four arcs with division points at °45, 135°, 225°, and 315°.

Suppose the circle center is at xₒ,yₒ and radius is r. With δ = (r·√2)/2, the range of x coordinates for the top and bottom arcs is from xₒ-δ to xₒ+δ. The range of y coordinates for the right and left arcs is from yₒ-δ to yₒ+δ.

Let y₁, y₂ be top and bottom y coordinates corresponding to x. For the top and bottom arcs use the formula d=√(r²-(x-xₒ)²); y₁=yₒ+d; y₂=yₒ-d.

Let x₁, x₂ be right and left x coordinates corresponding to y. For the right and left arcs, use the formula d=√(r²-(y-yₒ)²); x₁=xₒ+d; x₂=xₒ-d.

As noted in a comment, the equations derive from the circle equation. In this case, that's (x-xₒ)² + (y-yₒ)² = r², from which we get either (x-xₒ)² = r² - (y-yₒ)² so that x-xₒ = ±√(r² - (y-yₒ)²), etc., or (y-yₒ)² = r² - (x-xₒ)² so that y-yₒ = ±√(r² - (x-xₒ)²), etc.