《算法的乐趣》第四十一节

本节讲解光栅图形扫描转换的概念：由于点阵设备的像素有大小且位置固定，只能用像素近似显示数学意义上的直线，这一构造最逼近图形的像素直线的过程即扫描转换。

本节讲解光栅图形扫描转换的概念：由于点阵设备的像素有大小且位置固定，只能用像素近似显示数学意义上的直线，这一构造最逼近图形的像素直线的过程即扫描转换。随后介绍了几种直线生成算法：数值微分法（DDA）按斜率沿主方向步进并取整，简单精确但需浮点运算；Bresenham算法通过判断交点与相邻像素中心的距离差，推导出只用整数加减和移位的递推判据，效率高、应用最广；对称算法利用直线段的中点对称性，每次判断生成两端各一个点；两步算法则沿一个方向每次生成两个点，按决策量判断后两个点的四种组合。作者比较指出，DDA简单但效率低，Bresenham因整数运算效率高，两步、四步算法虽理论效率更高，但准备与运算开销大，画短线时反而不如Bresenham。