Sign in to follow this  
pavachan

Circle - A question about filling it.

Recommended Posts

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 :)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
One easy way is just to frame the circle with an imaginary square and only colour in the region of the square that is within the bounds of the circle:

def drawFilledCircle((x, y), radius, colour):
radiusSquared = radius * radius

for u in range(-radius, radius + 1):
for v in range(-radius, radius + 1):
distanceSquared = u * u + v * v

if distanceSquared < radiusSquared:
plot(x + u, y + v, colour)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this