How can I draw a filled circle on a grid with the less rectangle as possible?

Question

I have a grid with a variable width/height spacing. Let's say 100 horizontal lines separated by 80 pixels and 100 hundred vertical lines separated by 50 pixels.

Each cell of the grid in my logic have the same function as a pixel. So each of my pixels will be 50 px width and 100 px height.

I need to draw a circle filled with a color (let's say black) and without stroke.

I also need my circle to (as it is made out of filled cells) be with the less rectangles as possible, so certain rectangles are bigger than other ones.

for example the center of the circle is made out of one big rectangle then as we go closer to the edge the rectangles becomes smaller.

for example here I have circle with a grid of same width/height spacing made out of 9 rectangles (sorry for the quality of the image)

Any algorithm to do that?

Answer 1

To get a proper circle, you can use a transformation matrix to transform your cell coordinates into equally spaced cartesian coordinates. In the case of your 50 x 100 pixel cells, your transformation matrix would probably either double the width or halve the height. So something like this:

| 0.5 0.0 |
| 0.0 1.0 |

If you want to draw a circle of radius r at a center point (cx, cy), you could iterate over the cells from (cx - r, cy - r) to (cx + r, cy + r) and test if each one is in the circle, and if so, fill it in, otherwise, don't. Something like this pseudocode:

double rSquared = r * r;
for (int row = cy - r; row < cy + r; row++)
{
    for (int col = cx - r; col < cx + r; col++)
    {
        double x = col * transform[0][0] + row * transform[0][1];
        double y = col * transform[1][0] + row * transform[1][1];
        double distSquared = x * x + y * y;
        if (distSquared <= rSquared)
        {
            // inside the circle, fill in this cell (col, row)
        }
        else
        {
            // outside the circle, don't fill in this cell (col, row)
        }
    }
}

As for drawing rectangles, it's not clear what you're trying to accomplish there. There's no need to use rectangles when drawing a circle.