Drawing concentric circles without gaps

algorithmsgraphics

I want to fill a circle with alternate colors like a lollipop by drawing circumferences of increasing radius on a Cell matrix. I am currently using the Midpoint circle algorithm to get the points. The problem I have is that there are some gaps when filling a circle this way.

In the example below (original is number 1) I used pink and white to highlight the various circumferences. (Notice the black pixels)

The code of my implementation (1) is here: https://gist.github.com/beppe9000/e4a29542a76b8ee3b47f

I am looking for an algorithm that does not produce such gaps.

Update

It is important that the circle is filled using concentric passes because i also update some metadata in the cells as I get them in groups (each one corresponding to a circumference). I tried simplifying the problem, so you didn't get it all, I'm sorry if I'm not a great communicator… 😉

Basically I need the circumferences produced to be perfectly contiguous. That means no gaps between circles of radius n and n+1

Update 2

I tried the brute-force algorithm with some results, still lacking the ability to get individual circumferences. In particular I had great hopes for number 3…
enter image description here

Best Answer

The midpoint algorithm gives you the set of points lying "exactely" a given distance from the center.

What you would want to do is to use another algorithm where you test if the distance is lower than (and not equal to) the radius.

The brute force algorithm would be to check every cell in the grid, but if you really want to be efficient, you could perform neighbourhood testing (similar to the midpoint algorithm) and perform some sort of line scan starting from the top (x_start = x_radius; y_start = y_radius + radius).

An example in pseudo-code: 

foreach i in i_range:
    foreach j in j_range:
        y = i - ry
        x = j - rx
        if (x^2 + y^2)^0.5 - 0:
           paint_cell(i,j)
Related Topic