# How can I calculate "All squares within R" in a natural looking manner?

I'm working with a square grid, and I have a couple of effects that target all squares within R; in other words, a circular (or spherical) effect.

But, circles being, well, circular, and squares being... less so, things obviously have to be approximated. For instance:

But! I feel that some of these approximations don't quite give the approximation I want. For instance, consider this square:

It's obvious that the majority of the square falls within the circle, but using a pure "square counting" method (i.e., all squares within R of the origin), it gets left out.

Is there a better algorithm to grab all squares for which the majority of their area lies within the circle?

• If I understand this right, your current algorithm colours any fully-encapsulated squares red; you want to cover any square where 50% or more of the area is encapsulated, is that right? Mar 31 '14 at 2:21
• @ashes999 Correct. The picture actually centers the origin on an intersection between 4 squares, but I'd also be interested with an origin from the middle of one of the cells. Mar 31 '14 at 2:22
• try including a square if the line from the center to the center of the square in question has length <= to the radius. Mar 31 '14 at 3:17
• Or quite simply enlarge the radius by (about) half the tile size. Might be a "close enough" solution. Mar 31 '14 at 7:22
• @Raxvan Sure. It's the same as the one used in the example pictures: for a given radius "r", include all squares that can be reached in "r" square steps. (Diagonals are 1.5; always round totals down) Mar 31 '14 at 12:12

Without details of your existing algorithm, it's hard to say, but in pretty much any case involving a line over a grid, I've found the answer to be Bresenham's, or a variant thereof. In this case, I'd recommend looking at the Midpoint Circle Algorithm. That can give you a set of outer-bounds tiles, and then just fill it from there.

• Rerunning the Midpoint Circle Algorithim subtracting 1 from the radius each time until the radius is 1 results in a filled circle. Apr 9 '14 at 20:35
• @ClassicThunder I strongly recommend against building a filled circle that way - it's surprisingly difficult to guarantee that you won't get 'holes' in the fill and some pixels will definitely be hit more than once. Instead, use the midpoint algorithm (or similar) to determine (for instance) the X-bounds for each scanline of the circle, and just loop over all the pixels from one end of the scanline to the other. Apr 9 '14 at 21:17

As was approximately pointed out in comments, the simplest way to do what you're after is to test the center of the square, rather than all of the corners. This isn't exactly equivalent to a majority of the square's area being within your circle, but the latter is a Hard Problem, and it should be close enough for your needs.

But note that this doesn't take any floating-point arithmetic, either — testing whether (x+1/2, y+1/2) is within some distance r of your center (which I'll take as the origin) is just checking whether (x+1/2)2+(y+1/2)2 < r2, and by multiplying by 4, this is exactly the same as testing whether (2x+1)2+(2y+1)2 < 4r2. This is useful for testing individual grid cells for inclusion.

For anything beyond this, though — and in particular, for generating all the points at once — I heartily second David Kiger's recommendation of "Bresenham-style" algorithms like the midpoint algorithm. They're also all-integer algorithms and can find you the endpoints for each row of your circle with only a small amount of arithmetic.

A traditional Midpoint Circle Algorithm implementation look like the below and only outlines the circle.

draw_circle(int x0, int y0, int radius)
{
int x = radius, y = 0;

while(x >= y)
{
set_pixel(x + x0, y + y0);
set_pixel(y + x0, x + y0);
set_pixel(-x + x0, y + y0);
set_pixel(-y + x0, x + y0);
set_pixel(-x + x0, -y + y0);
set_pixel(-y + x0, -x + y0);
set_pixel(x + x0, -y + y0);
set_pixel(y + x0, -x + y0);
y++;
{
radiusError += 2 * y + 1;
} else {
x--;
radiusError+= 2 * (y - x + 1);
}
}
}


Here is a brute force method that bumps things up from O(N) to O(N2) but benefits from not utilizing with Cosine or Squaring functions. It also actually fills in the circle instead of outlining it.

void draw_circle (int radius)
{
int x, y;

if ((x * x) + (y * y) <= (radius * radius))
set_pixel(x, y);
}


As you titled "in a natural looking manner" I think it is a dither or "photoshop feather" problem, not a geometric problem.
You can fill any square that is touching circumference line with color compensated by brightness according to area inside circle. In your example, all squares inside circumference are filled with red (inside color), and all outside squares are white (outside color). If a given square have 25% of area inside circumference, then it can be filled with an color equivalent with 25% inside color and 75% outside color. The tricky part is color calculation and you should research about it. This how I solved it:

for(col=0, col<grid_size, col++{
for (row=0, row<grid_size, row++{
d = sqr(x^2 + y^2); // Distance from center
d_i = floor(d); // Integer part of distance
// Paint with inside color i.e red (0xFF0000).
} else if (d_i > radius){
// Paint with outside color i.e. white (0x000000).
} else{
// Pixel is touching circumference line.
// Lets calculate how much area is inside circle.
// Get angle from center.
if (x == 0) {
if (y > 0) {
angle = pi();
} else {
angle = -pi();
}
} else {
angle = atan(y / x);
}
p_w = (d - d_i) * sin(angle);
p_h = (d - d_i) * cos(angle);
a = p_w * p_h; // (rough) Pixel area under circumference, which falls inside circle.
// Trivial solution. Color averaging is a non-trivial issue.
if (\$a >= 0.50) {
// Bigger area, more like inside color
// Paint with 0xAA0000
} else {
// Less area, more like outside color
// Paint with 0x660000
}
}
}
}