预测使用中点圆算法返回的点数

Question

众所周知的中点圆算法(wikipedia)给出了给定半径的圆的像素坐标的x,y坐标。

它使用迭代计算，并在每次迭代中使用条件退出循环：while (y > x) etc... 我有一个问题，就是如何预测，在给定半径的情况下，算法返回的点的总数是多少？ 我的数学背景有限，无法推导出来。我搜索了一下，唯一找到的是以下内容: http://www.gdunge.com/2011/03/23/a-different-kind-of-pi。页面的作者Doug提到他通过实验发现round(sqrt(2) * radius)适用于四分之一圆。我尝试用它来得到整个圆，但会错过一些点。

这个数字背后的实质规律是什么？

- Jean-Yves

---

我也不是数学家，但在我看来，它似乎只是周长的长度，向上取整。 - Kae Verens

@Kae：我找到的最接近的公式是 4 * ( round(sqrt(2)/2 * (radius-1)) + 2 )。但它大约每16个点就会失败... - Jean-Yves

@Kae：此外，周长的长度为2 * pi * r，并且它甚至没有相同的斜率。 - Jean-Yves

Answer 1

我以你的公式为基础，得到了这个结果：

floor((sqrt(2)*(radius-1)+4)/2)*8

现在它运行得非常好。

- Danguafer

---

非常接近 - 只考虑八分之一，返回实际计数或一个更大的半径为16557，然后在32767（图形最大值）的半径上增长1523个以上。 - carmin

Answer 2

中点圆算法绘制半径为r的圆时，绘制的像素点数量为
    4 round(sqrt(2) r)
或等效地
    4 floor(sqrt(2) r + 1/2)。
*许多中点圆算法的实现会重复绘制多个像素点。
    实际的重复次数取决于半径和具体实现的细节。
特别地，C#实现算法（原帖中引用）绘制的像素点数量，包括重复的，为
        8 floor((sqrt(2)/2) r + 3/4) + 4。

- user3405743

---

我的像素数量公式甚至在那些被接受的答案无法解决的情况下也能正常工作。 - user3405743

好的，就是这样！在答案中解释一下就可以了！ - Nathan Tuggy

我的回答还指出了绘制像素的不同数量和包括重复像素的总绘制像素数量之间的区别。从发帖者的问题中并不清楚他正在寻找哪一个，甚至是否意识到它们是不同的数字。 - user3405743

Answer 3

如果您查看您所参考的维基百科页面上的图表，您会发现在第一象限中，每个像素都比前一个像素高一个单位，并且比前一个像素低一个像素，快速浏览算法表明，在此位置的八分之一圆弧中，这总是如此。

因此，绘制圆的第一个八分之一所需的像素数是您在第一个八分之一中向上移动的像素数。如果半径为r，则您在第一个八分之一中向上移动的距离为r sin 45度，即r / sqrt（2）- 在45度处，我们有一个直角三角形，两条边长为1，斜边长为sqrt（2）。

如果一个八分之一需要r / sqrt（2），那么四分之一圆 - 两个八分之一 - 需要r * sqrt（2）

- mcdowella

---

谢谢！我发现4 *（round(sqrt(2)/2 * (radius-1)) + 2）可以工作，但舍入问题会偶尔导致失败...我会继续研究。 - Jean-Yves