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-1)(x+1)2+y 2-r 2>r 2-(x+1)2-(y-1)2，则选择(，y-1)。

收集相似的术语，简化为2(x+1)2+y 2+(y-1)2-2R 2> 0。

膨胀使为2x 2+ 2y 2-2R 2+ 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)