I need to draw an approximate circle on a grid of squares and find its area. Each square must either be completely part of the circle or not at all occupied. Obviously, this means that it cannot be a perfect circle. Instead, it will look something like the circles in this picture: enter image description here

The circle is generated by selecting a center point (x,y coordinates in the grid) and a radius and counting any square in the grid as part of the circle if the Euclidean distance between it and the center point is less than that radius. Up until now I've just been checking every cell in the vicinity to see if it meets these criteria, but it seems like there must be a better way if I just need to know how many cells are included (i.e. the area).

Is it possible to come up with a formula for calculating the area of this sort of circle based on the radius, or does the discretization make it too unpredictable?

  • $\begingroup$ This sounds like an integration problem where the partition has a fixed size... Have you already optimized based on counting only $1/4$ of each circle? Another approach might be to start with the proper area, then subtract where you have squares which are not entirely inside your circle. $\endgroup$ – abiessu Apr 20 '15 at 4:57
  • $\begingroup$ I have not, but that's a great idea, and I will now! $\endgroup$ – seaotternerd Apr 20 '15 at 4:59
  • 1
    $\begingroup$ There may be useful information if you look at the Gauss Circle Problem (Wikipedia). $\endgroup$ – André Nicolas Apr 20 '15 at 5:05
  • 2
    $\begingroup$ you may find answers of this similar question useful. $\endgroup$ – achille hui Apr 20 '15 at 5:17
  • $\begingroup$ Perfect! That's exactly what I was looking for. Thanks! $\endgroup$ – seaotternerd Apr 20 '15 at 5:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.