Drawing concentric tiling circles with even diameter

Question

I need to draw circles using pixels with these constraints:

1. the total of pixels across the diameter is an even number,
2. there is no empty pixels between two circles of radius R and R+1 (R is an integer).

The midpoint algorithm can’t be used but I found out that Eric Andres wrote the exact thing I want. The algorithm can be found in this article under the name of “half integer centered circle”. For those who don’t have access to it, I put the interesting part is at the end of the question.

I encounter difficulties to implement the algorithm. I copied the algorithm in Processing using the Python syntax (for the ease of visualisation):

def half_integer_centered_circle(xc, yc, R):
    x = 1
    y = R
    d = R
    while y >= x:    
        point(xc + x, yc + y)
        point(xc + x, yc - y + 1)
        point(xc - x + 1, yc + y)
        point(xc - x + 1, yc - y + 1)
        point(xc + y, yc + x)
        point(xc + y, yc - x + 1)
        point(xc - y + 1, yc + x)
        point(xc - y + 1, yc - x + 1)
        if d > x:
            d = d - x
            x = x + 1
        elif d < R + 1 - y:
            d = d + y - 1
            y = y - 1
        else:
            d = d + y - x - 1
            x = x + 1
            y = y - 1

The point() function just plot a pixel at the given coordinates. Please also note that in the article, x is initialised as S, which is strange because there is no S elsewhere (it’s not explained at all), however it is said that the circle begins at (x, y) = (1, R), so I wrote x = 1.

There is the result I get for a radii between 1 pixel and 20 pixels:

As you can see, there are holes between circles and the circle with R = 3 is different from the given example (see below). Also, the circles are not really round compared to what you get with the midpoint algorithm.

How can I get the correct result?

---

Original Eric Andres’ algorithm:

Answer 1

I don't understand the way in which the algorithm has been presented in that paper. As I read it the else if clause associated with case (b) doesn't have a preceding if. I get the same results as you when transcribing it as written

Looking at the text, rather than the pseudocode, the article seems to be suggesting an algorithm of the following form:

x = 1
y = R
while x is less than or equal to y:
    draw(x, y)
    # ...
    if the pixel to the right has radius between R - 1/2 and R + 1/2:
        move one pixel to the right
    if the pixel below has radius between R - 1/2 and R + 1/2:
        move one pixel down
    else:
        move one pixel diagonally down and right

Which seems plausible. In python:

#!/usr/bin/python3

import numpy as np
import matplotlib.pyplot as pp

fg = pp.figure()
ax = fg.add_subplot(111)

def point(x, y, c):
    xx = [x - 1/2, x + 1/2, x + 1/2, x - 1/2, x - 1/2 ]
    yy = [y - 1/2, y - 1/2, y + 1/2, y + 1/2, y - 1/2 ]
    ax.plot(xx, yy, 'k-')
    ax.fill_between(xx, yy, color=c, linewidth=0)

def half_integer_centered_circle(R, c):
    x = 1
    y = R
    while y >= x:
        point(x, y, c)
        point(x, - y + 1, c)
        point(- x + 1, y, c)
        point(- x + 1, - y + 1, c)
        point(y, x, c)
        point(y, - x + 1, c)
        point(- y + 1, x, c)
        point(- y + 1, - x + 1, c)
        def test(x, y):
            rSqr = x**2 + y**2
            return (R - 1/2)**2 < rSqr and rSqr < (R + 1/2)**2
        if test(x + 1, y):
            x += 1
        elif test(x, y - 1):
            y -= 1
        else:
            x += 1
            y -= 1

for i in range(1, 5):
    half_integer_centered_circle(2*i - 1, 'r')
    half_integer_centered_circle(2*i, 'b')

pp.axis('equal')
pp.show()

This seems to work as intended. Note that I removed the circle centre for simplicity. It should be easy enough to add in again.

---

Edit Realised I could match the radius 3 image if I tweaked the logic a bit.

Answer 2

I have been looking into this matter and observed three issues in the original paper:

1. The arithmetic circle copied here (Figure 10.a in the paper) is not consistent with the formal definition of the "half integer centered circle". In one case the distance to the center must be between R-1/2 and R+1/2 and in the other between integer values. The consequence is that this specific algorithm, if properly implemented, can never generate the circle of Figure 10.a.

2. There is a mistake in one of the inequalities of the algorithm pseudo code: the test for case (b) should be d <= (R + 1 - y) instead of d < (R + 1 - y).

3. All those pixels that satisfy x==y have only 4-fold symmetry (not 8-fold) and are generated twice by the algorithm. Although producing duplicated pixels may not be a problem for a drawing routine, it is not acceptable for the application that I am interested in. However this can be easily fixed by adding a simple check of the x==y condition and skipping the four duplicated pixels.

The python code of the original question includes the inequality error mentioned above and an additional mistake due to missing parenthesis in one of the expressions that should read d = d + (y - x - 1).

The following implementation fixes all this and is compatible with python2 and python3 (no integer division issues in the point() function):

import numpy as np
import matplotlib.pyplot as pp

fg = pp.figure()
ax = fg.add_subplot(111)

def point(x, y, c):
    xx = [x - 0.5, x + 0.5, x + 0.5, x - 0.5, x - 0.5 ]
    yy = [y - 0.5, y - 0.5, y + 0.5, y + 0.5, y - 0.5 ]
    ax.plot(xx, yy, 'k-')
    ax.fill_between(xx, yy, color=c, linewidth=0)


def half_integer_centered_circle(R, c):
    x = 1
    y = R
    d = R
    while y >= x:
        point(x, y, c)
        point(x, - y + 1, c)
        point(- x + 1, y, c)
        point(- x + 1, - y + 1, c)
        if y != x:
            point(y, x, c)
            point(y, - x + 1, c)
            point(- y + 1, x, c)
            point(- y + 1, - x + 1, c)
        if d > x:
            d = d - x
            x = x + 1
        elif d <= R + 1 - y:
            d = d + y - 1
            y = y - 1
        else:
            d = d + (y - x - 1)
            x = x + 1
            y = y - 1

for i in range(1, 5):
    half_integer_centered_circle(2*i - 1, 'r')
    half_integer_centered_circle(2*i, 'b')

pp.axis('equal')
pp.show()