1、5.3 试用中点 Bresenham 算法画直线段的原理推导斜率在-1,0之间的直线段绘制过程（要求写清原理、误差函数、递推公式及最终画图过程） 。解法一：构造直线方程 F(x,y)=y-kx-b=0由于 ，即 ，此时 x 为最大位移方向 ，算法每次在 x01k1xy方向上加 1，y 方向上减 1 或减 0。即对于当前选定的点 Pi（xi，yi ） ，下一个点应该为 或 ，选取哪一个点依赖于判,iidyxPiiuyxP,1别式。即有 11iiiiyx取 Pu 和 Pd 的中点 M（ xi+1，yi-0.5） ，将 M 的坐标代入直线方程构造判别式： bxkyyfxfii iiM)1(5.0)5
2、.0,当（注意这里的判断方法）d0 时， M 点在 Q 点上方，取 1,iidyxPd0 时, 增量为 -1-kkdbxyfiiii1)2(5.,2当 时, 增量为-k0dkdbxyyxfiiii12 )2(5.0.,kkbkxybyf 5.05.0)(.,00000由于 x 方向递增， ，故此在等式两边同乘以 ，则有：x x2当 d0 时, 增量为yDkd212 yx2当 时, 增量为0y12 yyxDkd25.0注意：此时优化要注意此时 0 时， M 点在 Q 点上方，取 iidP,当 d0 时, 增量为 kkdbxyfii12)2(5.0.,当 时, 增量为 1+k0dkxyfii )(
3、.1,12kbkxyf 5.0.)(5.,000由于 x 方向递减， ，故此在等式两边同乘以- ，则有：0x x2当 d0 时, 增量为yDkd212 y2当 时, 增量为0yx21 yx2yxDkd25.05.7 利用中点 Bresenham 画圆算法的原理推导第一象限 xy 到y0 圆弧段的扫描转换算法（要求写清原理、误差函数、递推公式及最终画图过程） 。yPPl PrM解：在 x=y 到 y=0 的圆弧中， （R,0）点比在圆弧上，算法从该点开始。最大位移方向为 y，由（R,0）点开始，y 渐增，x 渐减，每次 y 方向加 1，x 方向减 1 或减 0。 （注意算法的起始点）设 P 点坐
4、标（ xi,yi）,下一个候选点为 Pr（xi,yi+1）和 Pl（xi-1,yi+1 ） ，取 Pl 和 Pr 的中点 M（ xi-0.5,yi+1） ，设理想圆与 y=yi+1 的交点 Q，构造判别式： 222)1()5.0(),( RyxyxFd iM 当 d0 时， M 在 Q 点右方，取 Pl（xi-1,yi+1）d0 时，M 与 Q 点重合，约定取 Pl（xi-1,yi+1 ）所以有： )0(11dxxyiii i推导判别式：时，取 Pl（xi-1,yi+1） ，下一点为（xi-1,yi+2）和（xi-0d2,yi+2）52 1)(2)1().0().0(1)2,5.(1 222
5、ii iiii ii iiyxd yyxRyxF时，取 Pr（xi,yi+1） ，下一点为（xi,yi+2 ）和（xi-1,yi+2） 321)(2)1()5.0(),.(122 i iii ii iiydyxRyFdRRRRF 25.5.0),.(20优化：令 D=d-0.25则上述公式只有初值发生变化，即 D=1-R，其余用 D 替换 d 即可。5.11 如图 559 所示多边形，若采用扫描转换算法（ET 边表算法）进行填充，试写出该多边形的 ET 表和当扫描线 Y4 时的有效边表（AET 表，活性边表） 。xy21345678123456解： ET 表 123456131/2 75033
6、-166-1 361/4651y4 时的 AET 表3.5 6 1/4Y=46 6 -1 6 5 1 7 5 0注意：（1）构造边表时，水平边不需要构造；（2）边表中纵向链表的长度等于多边形覆盖的扫描线数；（3）边表与有效边表中每个结点的第三项为 1/k；（4）构造有效边表时，每个结点的第一项，即当前扫描线与多边形边交点处的 x 坐标不需要四舍五入，否则在计算下一条扫描线时可能会造成误差。5.22 构造两个例子，一个是 4连通图，其边界是 8连通的，另一个是 8连通图，其边界是 4连通的。解：注意：由于八邻接点中包含四邻接点，所以四连通区域也可以看作八连通区域，但是四连通区域与八连通区域的边界
7、条件是不同的，通常在边界表示的区域中，四连通区域边界（内环和外环边界）的连通性是八连通，而八连通区域边界（内环和外环边界）的连通性是四连通。在一些特殊的情况下一个区域的连通性可能既是四连通也是八连通，例如内点表示的四连通区域（内点表示没有显示的边界） ，或者将边界表示的四连通区域的所有边界（内环和外环边界）都改为四连通性质。6.4 已知点 P（x p，y p）及直线 L 的方程 Ax+By+C=0，试推导一个相对 L 作对称变换的变换矩阵 T，使点 P 的对称点为 。TP解法一：（1）当 B=0 时，直线方程变为 Ax+C=0，即 x=-C/A，该直线与 y 轴平行。变换可以先将直线平移，使之与 y 轴重合，此时的对称变换是相对于 y 轴的对称变换，最后在反平移，使直线回到原来的位置。 102101010 ACACACT（2）当 时，直线方程变为 ，直线与 y 轴有一个BBxy交点（0，-C/B） ，直线的斜率 k=-A/B。此时先将直线平移，使点（0，-C/B）与原点重合，在顺时针旋转 角（tg=-A/B）使直线与 x 轴重合，此时的对称变换是相对于 x 轴的对称变换，最后反变换，使直线回到原来的位置。 1)2cos(2sin0ico 1010cosin1010cosini10 BC BCT
