直线插补.docVIP

直线的插补算法 F0203305 5020309063 马超 【算法描述】 该程序使用了Bresenham算法的思想，将四个象限（考虑到斜率1，1一共八种情况）的问题通过交换端点的方法合并成一，四象限的问题。再利用sign变量，统一成一个问题。又考虑到斜率1，1最终问题分成了两种情况。在直线插补程序的一开始，把斜率为正无穷的情况单独进行讨论。最终完成了整个程序。 具体算法是： 将左端点进行端点规整，在斜率小于1的情况下，在X轴方向进行单位步长增长。若斜率大于1，就对Y轴进行单位步长增长，原理与斜率小于1的情况差不多，此处只说明斜率小于1的情况。 先看左端点的规整： 此处使用的方法是一律对直线进行延长，在斜率小于1的情况下认为交在x=low(rx)处，求出此交点的y坐标。其中low(rx)为小于rx的最大整数。在（x,Round(y)）处画点。其中Round(y)表示对y进行四舍五入。然后x以单位步长进行增长，每增长一步，计算出相应的Y值。在（x,Round(y)）处画点，一直进行到x的值〉=右端点的x值时，结束。 如下图所示： 下面证明此插补方法得到的直线是最接近原直线的： 我们知道，如果要想接近直线，则每一点倒直线的距离应该尽可能的近。 我们考虑P, Q1,Q2三点。 P点是我们找到的比较点，现在可能选中的点是Q1,Q2，我们选择的是离P点近的点Q1。下面证明离P点近的点也就是离直线近的点。 可以很容易的推出，Q1到直线的距离L1为： Q2到直线的距离L2为： 其中PQ1,PQ2分别为Q1,Q2点到P点的距离，k为直线的斜率。 从上式可以看出，离P点近的点也就是离直线近的点。由此可以证明，新直线是原直线的最好逼近。 【源程序】 可参见源代码。此处只给出主要代码（其中有端点规整的代码）： void CHomeWork1View::Compute(CDC* pDC) { double lx,ly,rx,ry,linx,liny,k; int sign; //此变量的作用是将一，四象限的问题进行统一。 //lx,ly为左边点的坐标（x小）；rx，ry为右边点的坐标（x大） if(first.xsecond.x) { lx = second.x; ly = second.y; rx = first.x; ry = first.y; } else { lx = first.x; ly = first.y; rx = second.x; ry = second.y; } if(first.x==second.x) //斜率不存在 { sign = ryly?1:-1; linx = Round(lx); liny = floor((ly+20)/20)*20*sign; while(liny(ry)*sign) { paint(pDC,linx,fabs(liny)); liny+=20; } } else //斜率存在 { k = -fabs((ly-ry)/(rx-lx)); sign = ryly?1:-1; if(fabs(ry-ly)fabs(rx-lx)) //斜率绝对值小于1的情况，按x步增 { linx = floor(lx/20)*20; liny = (lx-linx)*k*sign+ly; while(linxrx) { paint(pDC,linx,Round(liny)); linx+=20; liny-=20*k*sign; } } else //斜率绝对值大于1的情况，按y步增 { liny = (sign==1)?(floor(ly/20)*20*sign):(ceil(ly/20)*20*sign); linx = lx+(ly-fabs(liny))/k*sign; while(linyry*sign) { paint(pDC,Round(linx),fabs(liny)); liny+=20; linx-=20/k; } } } } 解决闪烁的双缓冲方法如下： void CHomeWork1View::OnDraw(CDC* pDC) { CHomeWork1Doc* pDoc = GetDocument(); ASSERT_VALID(pDoc); int n