algorithm - Bresenham 的圆算法

Question

https://www.geeksforgeeks.org/bresenhams-circle-drawing-algorithm/

我正在查看 Bresenham 的算法，我试图用它来制作 MS 绘画风格应用程序。我已经将它实现到 python 中并且可以正常工作。但是，我不确定这是如何工作的。除了决策参数，我了解所有算法。具体为什么它必须是 d = 3 – (2 * r) , d = d + (4*x) + 6 或 d = d + 4 * (x – y) + 10。是否有人熟悉该算法或了解这些推导背后的数学原理？我了解直线算法背后的理论，但我很难理解圆形绘图。

Answer 1

如果您刚刚绘制了像素 (x,y)，那么下一个要绘制的像素是 (x+1,y) 或 (x +1,y-1)

使用的实际条件决定选择哪个是近似哪个最接近理想圆。如果(x+1)² + y² - r² > r² - (x+1)² - (y-1)²

收集相似项，简化为 2(x+1)² + y² + (y-1)² - 2r² > 0

展开得到 2x² + 2y² - 2r² + 4x - 2y + 3 > 0

左边那个表达式是d .最初，x=0 和 y=r，所以这些项中的大部分为零或抵消，我们有 d = 3 - 2y = 3 - 2r

您询问的其他表达式表示如何 d选择下一个像素后会发生变化。

http://www.wolframalpha.com/input/?i=simplify+(2(x%2B2)%C2%B2+%2B+(y-1)%C2%B2+%2B+(y-2)%C2%B2+-+2r%C2%B2)+-+(2(x%2B1)%C2%B2+%2B+y%C2%B2+%2B+(y-1)%C2%B2+-+2r%C2%B2)

http://www.wolframalpha.com/input/?i=simplify+(2(x%2B2)%C2%B2+%2B+y%C2%B2+%2B+(y-1)%C2%B2+-+2r%C2%B2)+-+(2(x%2B1)%C2%B2+%2B+y%C2%B2+%2B+(y-1)%C2%B2+-+2r%C2%B2)