绘制直径均匀的同心圆

Question

我需要使用具有以下约束的像素绘制圆圈：

直径上的像素总数为偶数，
两个半径为R和R+1（R为整数）的圆之间没有空像素。

不能使用中点算法，但我发现 Eric Andres 写的正是我想要的。该算法可以在 this article 中找到，名称为“half integer centered circle”。对于那些无法访问它的人，我把有趣的部分放在问题的末尾。

我在实现算法时遇到困难。我使用 Python 语法复制了 Processing 中的算法（为了便于可视化）：

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

point() 函数只是在给定坐标处绘制一个像素。另请注意，文章中x被初始化为S，这很奇怪，因为其他地方没有S（根本没有解释），但是据说圆从 (x, y) = (1, R) 开始，所以我写了 x = 1.

这是我得到的半径在 1 像素到 20 像素之间的结果：

如您所见，圆之间有孔，R = 3 的圆与给定的示例不同（见下文）。此外，与使用中点算法得到的圆相比，这些圆并不是真正的圆。

怎样才能得到正确的结果？

Eric Andres 的原始算法：

Answer 1

我不明白该论文中介绍算法的方式。在我阅读它时，与案例 (b) 关联的 else if 子句没有前面的 if。我在抄写时得到了和你一样的结果

看文章而不是伪代码，文章似乎在建议以下形式的算法：

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

这似乎有道理。在 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()

这似乎符合预期。请注意，为简单起见，我删除了圆心。再次添加应该很容易。

编辑意识到如果我稍微调整一下逻辑，我可以匹配半径为 3 的图像。

Answer 2

我一直在研究这个问题，在原论文中观察到三个问题：

这里复制的算术圆（论文中的图10.a）与"half integer centered circle"的正式定义不一致。在一种情况下，到中心的距离必须介于 R-1/2 和 R+1/2 之间，而在另一种情况下，则介于整数值之间。结果是这个特定的算法，如果正确实施，永远不会生成图 10.a.
算法伪代码的不等式之一有错误：案例(b)的测试应该是d <= (R + 1 - y)而不是d < (R + 1 - y).
所有那些满足x==y的像素只有4重对称（不是8重），算法生成了两次。虽然产生重复的像素对于绘图例程来说可能不是问题，但对于我感兴趣的应用程序来说这是不可接受的。然而，这可以通过添加对 x==y 条件的简单检查并跳过四个重复的来轻松解决像素.

原始问题的 python 代码包括上述不等式错误和由于表达式之一缺少括号而导致的额外错误，该表达式应为 d = d + (y - x - 1).

以下实现修复了所有这些问题并与 python2 和 python3 兼容（point() 函数中没有整数除法问题）：

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

绘制直径均匀的同心圆

Drawing concentric tiling circles with even diameter

algorithm

drawing

draw

pixel

pixels