用偶数直径画同心瓷砖圆形

Question

我需要使用像素绘制圆，具有以下限制条件：

1. 直径上的总像素数是偶数
2. 半径为R和R+1 (R是整数)的两个圆之间没有空像素。

中点算法无法使用，但我发现Eric Andres编写了我想要的精确算法。该算法可以在本文“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算法:

- Zoxume

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的图像。

- Bill

---

谢谢，它有效。在小半径处，圆的表面宽度看起来相当不规则（有点大），但在我打算使用的半径处，它是完美的。然而，这并不能解释为什么给出的伪代码无法运行。 - Zoxume

很高兴能够帮忙。我同意我们仍然不清楚为什么纸上的伪代码无法工作。可能有一个错别字或者关于d的定义有问题，但是我认为理解算法会更容易，而不是弄清楚纸上的错误或者我们误解了什么。 - Bill

Answer 2

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

1. 此处复制的算术圆（论文中的图10.a）与“半整数居中圆”的正式定义不一致。在某种情况下，距离中心的距离必须在R-1/2和R+1/2之间，在另一种情况下必须在整数值之间。因此，如果正确实现了这个特定算法，则无法生成图10.a的圆。
2. 在算法伪代码的一个不等式中存在错误：对于情况（b）的测试应该是d <= (R + 1 - y)而不是d < (R + 1 - y)。
3. 所有满足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()

- pablof