Hello :) let's say i have a circle with a center x,y and radius r. i can manually "draw" it into an array, for later display etc. what i am having trouble with is filling the circle with a certain color. there is the "cheap" way, of simply drawing lines from the center, to the calculated circle borders in a certain color, but it's less than perfect. i clearly remember there was a recursive way to do it, but cannot remember it. it is also important i do not use any api to draw the circle and fill it, but do it on my own. if you can help in any way, it would be great :) thank you :)

If you already have an algorithm for drawing the border of the circle, just find each pair of pixels on each row on the border, and you know that every pixel between them is inside the circle and thus should be colored in.

So, if (X1, Y) and (X2, Y) are on the circle, everything between (X1, Y) and (X2, Y) are in the circle.

Thinking about how you could to do this recursively, the first thing that comes to my mind is this:

Since you already have the border, you can start at the center pixel and fill it with your color. Check the color of every of the four direct neighbors of that pixel and if the neighboring pixel isn't colored yet, fill it with your color and check every of the four neighbors of that pixel and so on...

This algorithm is easily implemented recursively and will fill your entire circle until it hits the border.

[Edited by - DraganO on January 21, 2009 2:51:47 AM]

Thanks a lot :)

I would use a rasterization technique to fill the circle, since you already have an equation describing the border and it's a convex region. A recursive approach requires a ton of stack state, is slower, and more suited for arbitrary enclosed regions where you can't easily use other techniques and brute force is the best option.

Like andur mentioned, start at the top of your circle, which is y' = y + r (or y - r is your vertical axis is inverted), and calculate both values of x' using the circle equation. They should be the same at the top and bottom of the circle, but not in the middle. Continue on to the next row, y'-1, and calculate two more values for x'. Fill in the row between those values. Keep going until you reach y' = y - r, which is the bottom of the circle, and you'll be done!

What I'd do is start with a square around the circle, then recursively check whether the square intersected the circle (In which case I'd quarter the square and recurse over each quarter), or if the square was inside the circle (In which case I'd fill the square), or if the square was outside of the circle (In which case I'd stop recursing on it).

It's a simple way to quickly fill a circle, or any other shape you can check against a square. Of course you want to stop at a certain point; probably once the square has a width of 1.