How many squares does a circle cover?

I've looked a lot of places for this answer, but can't seem to find the exact solution for my specific question.

I have a circle with a diameter of 30um. I want to overlay this circle on a grid of 5um x 5um. I want to know both the minimum and maximum squares that the circle can cover if it is randomly placed on this grid. The caveat: A square counts as in the circle if it is more than 95% covered by the circle.

Is there a way that I can calculate the coverage of every square and have it counted if it exceeds a certain percentage? In a way, this is more like a tiling problem than a shape packing problem.

Any help would be great, thanks!

Answer 1

[Image Analyst]

I don't think the math is so easy. For the square inside the circle, fine - they're completely 100% covered, but for the squares intersecting the perimeter, well . . . the overlap area can have strange, crazy shapes. It would depend a lot on where (what side) the circle perimeter enters a side. Just try to visualize it. The shape could be simply a chord if it entered and left on one side, but it could look almost like a square with some corner clipped off in a weird way if the perimeter entered and left on two adjacent sides. I wouldn't even try the math. Perhaps Roger Stafford (the resident mathematician over in the newsgroup) might, but to me it looks tedious. Now, if you want to try it numerically, rather than theoretically/analytically, by using digital images, then that's do-able (at least for me). Not easy, for the most general case where the square size, quantized size, circle radius, and circle center location are all variables that you can adjust, but at least possible with some programming time and thought. For example, let's say that your tiniest unit - your digitzation size - is 1 unit (say it represents 1/1000 of a micron). Now let's say that you want "big squares" that are 5,000 units wide (for 5 microns, or whatever), and your "canvass size" 50,000 by 50,000 units, so you could potentially fit as many as 10 complete big squares across it or two partial squares and 8 full squares, depending on where they were centered. Now let's say you have a radius of 15000 units (diameter of 30,000), and the center of the circle is at 17,000 units (not the perfect center of your canvass). So then you have to plan out how to build a program around those numbers.... I'd start by building the image, then masking with the circle, then scanning with blockproc() to check which squares are more than 50% covered.

Answer 2

[Courtney]

I'm not looking to change the size of the circles or the squares. The circle has a diameter of 30 microns and the size of the grid squares are 5 microns per side. The squares have to stay in a grid and can't be rotated or shifted in any way.