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

Question

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?

Answer 1

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.

Answer 2

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)²+(y+1/2)² < r², and by multiplying by 4, this is exactly the same as testing whether (2x+1)²+(2y+1)² < 4r². 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.

Answer 3

Since all the other answers leave parts of the answer as an assignment to the reader.

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;
  int radiusError = 1-x;

  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++;
    if (radiusError<0)
    {
      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;

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

More about Circles.

Answer 4

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++{
    x = radius - col;
    y = radius - row;
    d = sqr(x^2 + y^2); // Distance from center
    d_i = floor(d); // Integer part of distance
    if (d_i < radius){
      // 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
      }
    }
  }
}    

Answer 5

The final answer is usually: hardcode it. That is, if you are going to be using this in any performance restricted way, such as interwoven with frame rendering, and assuming that you can bound the problem to some reasonable set of radii, iterating over references to each predetermined output skips the calculation phase entirely.

I recommend getting some graph paper out and then translating the squares you want for the circle radii you want to select for and reuse a method like this (c#)

void relativeAddress(sbyte x = 0, sbyte z = 0) { var _address = data.rootAddress; _address.X += x; _address.Z += z; addresses.Add(_address); }

and then for each case of radii as they grew in size, you can add additional rings. I recommend if (radii < nextThreshold){return;}, as it is easy to read and makes the perfect branch prediction.