4

著名的中点圆算法（维基百科）为我们提供了给定半径圆的像素坐标的 x,y 坐标。

它使用的计算是迭代的，并且在每次迭代时使用一个条件来退出循环：while (y > x) etc...

我的问题是如何提前预测，给定半径，算法返回的点总数是多少？

我的数学背景有限，无法推导出来。我搜索了它，我发现的唯一内容如下：http ://www.gdunge.com/2011/03/23/a-different-kind-of-pi 。该页面的作者 Doug 提到，他通过实验发现该round(sqrt(2) * radius)方法适用于四分之一圈。我尝试了它试图获得整个圈子，但它错过了一些点。

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

4

3 回答 3

7

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

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

它工作得很好。

于 2013-02-21T05:49:18.693 回答
1

如果您查看您参考的维基百科页面上的图表，您会看到，在第一个八分圆中，每个像素都比前一个像素高一个单位，比前一个像素低一个像素，快速浏览一下算法建议在这个位置上的八分圆总是如此。

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

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

于 2011-11-20T12:36:45.040 回答
1

绘制半径为r 的圆时，中点圆算法绘制的不同* 像素数  为     4 圆 (sqrt(2) r ) 或等效地为     4 层 (sqrt(2) r + 1/2)。


*中点圆算法的许多实现会多次绘制多个像素。
    重复的实际数量取决于半径和特定
    实现的细节。特别是，     原始帖子中引用的算法的 C#实现所绘制的像素数（包括重复项）为         8 floor((sqrt(2)/2) r + 3/4) + 4。

于 2015-02-09T02:45:01.080 回答