2

I am trying to draw a filled circle with the midpoint algorithm. I already managed to draw an unfilled circle with y0 = 320; x0 = 240; radius = 180 -with the following code (reference: https://en.wikipedia.org/wiki/Midpoint_circle_algorithm):

int x0, int y0, int radius;

x0 = 320;     //assign values
y0 = 240;
radius = 180;

int x = radius-1;
int y = 0;
int dx = 1;
int dy = 1;
int err = dx - (radius << 1);

while (x >= y)
{
    putpixel(x0 + x, y0 + y);
    putpixel(x0 + y, y0 + x);
    putpixel(x0 - y, y0 + x);
    putpixel(x0 - x, y0 + y);
    putpixel(x0 - x, y0 - y);
    putpixel(x0 - y, y0 - x);
    putpixel(x0 + y, y0 - x);
    putpixel(x0 + x, y0 - y);

    if (err <= 0)
    {
        y++;
        err += dy;
        dy += 2;
    }
    if (err > 0)
    {
        x--;
        dx += 2;
        err += dx - (radius << 1);
    }
}

This delivers the following output (saved in a bitmap): enter image description here

Now I want, that this unfilled yellow circle will be filled, so it looks like this:

enter image description here

I thought I can accommplish this with setting the radius everytime to radius-- so it draws the same circle with a -1 radius - and that until radius=0. So basically it draws everytime a new circle filled up with the old circle until there is now circle to draw anymore (radius=0). My code for this is:

int x0, int y0, int radius;

x0 = 320;     //assign values
y0 = 240;
radius = 180;

int x = radius-1;
int y = 0;
int dx = 1;
int dy = 1;
int err = dx - (radius << 1);

while(radius!=0) {
    while (x >= y)
    {
        putpixel(x0 + x, y0 + y);
        putpixel(x0 + y, y0 + x);
        putpixel(x0 - y, y0 + x);
        putpixel(x0 - x, y0 + y);
        putpixel(x0 - x, y0 - y);
        putpixel(x0 - y, y0 - x);
        putpixel(x0 + y, y0 - x);
        putpixel(x0 + x, y0 - y);

        if (err <= 0)
        {
            y++;
            err += dy;
            dy += 2;
        }
        if (err > 0)
        {
            x--;
            dx += 2;
            err += dx - (radius << 1);
        }
    }

    x0 = x0 - 1;     //getting the next circle until radius = 0
    y0 = y0 -1;
    radius = radius - 1;

    x = radius-1;
    y = 0;
    dx = 1;
    dy = 1;
    err = dx - (radius << 1);

}

This should be the code to my idea how I could fill up, but all i get is an infinite-loop.. Has anyone an idea why? Or has anyone another way to fill up the circle using the midpoint algorithm?

Greetings

payloc91
  • 3,724
  • 1
  • 17
  • 45
s.r.
  • 146
  • 8
  • 2
    first thing in that case: put a lot of printfs to print values of varying indices like x, y, err in all the loops and observe where you're stuck. Also use a small circle to avoid a lot of output. – Jean-François Fabre Dec 06 '17 at 09:57
  • @Jean-FrançoisFabre thanks for that advice - i will try that and lower the radius to 5. But is my idea, how I can fill up the rest, right? – s.r. Dec 06 '17 at 10:01
  • 1
    oh you could also use a flood fill algorithm. I'm describing one (implemented in python) here: https://stackoverflow.com/questions/40963288/fatal-python-error-cannot-recover-from-stack-overflow-during-flood-fill/40963737?s=2|26.2027#40963737 – Jean-François Fabre Dec 06 '17 at 10:11
  • this would work? where can I find your algorithm? this would be awesome. edit: just saw you edited it - thanks :) edit2: @Jean-FrançoisFabre could you maybe give me an exaple, how I implement your fill-up-algorithm in my c-programm? – s.r. Dec 06 '17 at 10:13
  • 1
    if you can convert my python code to C, you'll get a generic flood fill code, that can fill any closed form, not only a circle. – Jean-François Fabre Dec 06 '17 at 10:17
  • You should try debugging! – MrSmith42 Dec 06 '17 at 10:37
  • This question is a duplicate of [fast algorithm for drawing filled circles?](https://stackoverflow.com/q/1201200/563940). – Pedro Dec 06 '17 at 12:46

2 Answers2

6

I'm pretty sure doing it your way won't generate a very nice circle; rounding errors and such might very well end up giving you "holes" in the circle, i.e. un-filled pixels.

A much better approach is to realize that the circle can be viewed as a bunch of horizontal lines of varying lengths. Thus, all you need to do is to iterate the y component from -r to r, and for each such y compute the corresponding x using your existing code. Then draw a horizontal line from (-x, y) to (x, y).

unwind
  • 391,730
  • 64
  • 469
  • 606
  • +1 for that idea: I already thought that - so you mean i should fill the circle up line by line? This means I should get first the starting coordinate and then the ending coordinate from a line am I right? – s.r. Dec 06 '17 at 10:10
  • 1
    Yes, I mean you should draw the circle as a bunch of horizontal lines. No need to draw the actual circle (outline, un-filled) first, just draw the lines and that will be enough. You only need to compute *one* horizontal coordinate per vertical coordinate, since the circle is symmetrical as I said. – unwind Dec 06 '17 at 10:28
0

This question is a duplicate of fast algorithm for drawing filled circles?.

Pedro
  • 842
  • 6
  • 16