Bresenham中点画线算法

先标明这自 blog.csdn.net/######91116/article/details/6295714 直线扫描算法之---bresenham 改进算法(任何斜率，任何方向)by z##图形学神马的全都是数学，看来以后我不能搞这个，伤脑筋，所以先把我现在懂得先记录下来吧。不过呢，我的水平实在有限，对于算法这种东西实在难以说明白，请大家包涵。书上讲的实在是太过简略，所以这里我把一些简单的推导过程都记录下来： 1.重温 bresenham 未改进算法（斜率在 0-1 之间的直线）我想要记录的是 bresenham 改进算法，所以在讲解改进算法之前，我先用一个简单的例子说明一下未改进算法的思想：这是一个斜率 k 在 0-1 之间的一条直线，我就用斜率为 0-1 之间的直线来重温：首先，如图 1 所示，假设 x 列的像素已定，其坐标为（x，y），那么下一个坐标一定是：（x+1，y+1）或者（x+1，y）。而是哪一个取决于 d 的值，假如 d>0.5 那么就是（x+1，y+1），假如 d<0.5,那么就是（x+1，y），而 d 是什么呢？当然是斜率了。（原因如下：y=kx+b当 x 增加 1 时：y=kx+k+b所以当 x 增加 1 是，y 方向的增量是 d。）所以每次我们只需要让 d=d+k（k 是斜率）即可，当 d>=1 时，就让 d 减一，这样就保证了 d 在 0-1 之间。当 d>0.5,下一个点取（x+1，y+1）当 d<0.5,下一个点取（x+1，y） 然后呢，我们为了推断的方便，让 e=d-0.5，这样就变成了：当 e>0，下一个点取（x+1，y+1）当 e<0，下一个点取（x+1，y） 2.过渡，重温之后，我们就想要改进，为什么要改进呢？因为我们这里面有0.5，还有 k，k 里面有 dx/dy，这些除法和小数都不是我们想要的，我们想要的是，只有整数，且只有加法的算法，下面就全面讨论一下改进算法。 3.改进算法篇（不同斜率，不同方向）这里，我们主要分为 4 个角度来说明：A. 斜率在 0-1 只间B. 斜率在 1-无穷之间C. 斜率在 0-（-1）之间D. 斜率在（-1）-负无穷之间E．两种特别情况，两条直线。 A． 斜率在 0-1 只间以往我们会产生除法和小数的地方主要是：e=0.5e=e+k接下来我们一步一步实现我们的目标：1.消除除法e=e+dy/dxe*dx=e*dx+dy2.消除小数2*e*dx= 2e*dx+2dy由于算法中只用到误差项的符号，所以可以使用如下替换：e’=2*e*dx注意：为了让代换后符号不变，必须保证 dx>0使用这个替换以后，我们就可以消除除法和小数了，这里要注意一个问题，我们一定要保持 e 和 e’的符号是相同的，那么就要保证 dx...