8
\$\begingroup\$

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:

https://i.stack.imgur.com/AoXda.gif

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

enter image description here

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?

\$\endgroup\$
13
  • 1
    \$\begingroup\$ 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? \$\endgroup\$
    – ashes999
    Mar 31, 2014 at 2:21
  • \$\begingroup\$ @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. \$\endgroup\$ Mar 31, 2014 at 2:22
  • 7
    \$\begingroup\$ try including a square if the line from the center to the center of the square in question has length <= to the radius. \$\endgroup\$
    – Ray Tayek
    Mar 31, 2014 at 3:17
  • 1
    \$\begingroup\$ Or quite simply enlarge the radius by (about) half the tile size. Might be a "close enough" solution. \$\endgroup\$
    – CodeSmile
    Mar 31, 2014 at 7:22
  • 1
    \$\begingroup\$ @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) \$\endgroup\$ Mar 31, 2014 at 12:12

5 Answers 5

6
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Rerunning the Midpoint Circle Algorithim subtracting 1 from the radius each time until the radius is 1 results in a filled circle. \$\endgroup\$ Apr 9, 2014 at 20:35
  • 4
    \$\begingroup\$ @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. \$\endgroup\$ Apr 9, 2014 at 21:17
4
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
      }
    }
  }
}    
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ This does not provide an answer to the question. Once you have sufficient reputation you will be able to comment on any post; instead, provide answers that don't require clarification from the asker. - From Review \$\endgroup\$
    – liggiorgio
    Feb 7, 2022 at 10:19
  • \$\begingroup\$ In your opinion, is it fixed now? \$\endgroup\$ Feb 12, 2022 at 15:29
  • \$\begingroup\$ Not really. OP is trying to improve their search algorithm because the expected results are not optimal (i.e. not all squares for a given radius are found). They're looking for a better logic that considers the correct grid squares within a circle. OTOH, your answer addresses performance and optimisation, which are beyond the scope of the question. \$\endgroup\$
    – liggiorgio
    Feb 13, 2022 at 10:01
  • \$\begingroup\$ I would contest that the OP was doing their best to communicate their desired results, and that Inferring that this was for a game, given this is the game design community, I gave a more contextualized answer that is now a complete methodology to achieve said required results. OP can make it look exactly as they wish using my approach. The assumption of an algorithm could be seen as potentially erroneous. Not trying to be combative, just trying to fully respond to your input. \$\endgroup\$ Feb 15, 2022 at 16:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .