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

本节介绍计算机图形学中实用的圆与椭圆生成算法。直角坐标法与极坐标法因计算量大，仅作理论存在。

本节介绍计算机图形学中实用的圆与椭圆生成算法。直角坐标法与极坐标法因计算量大，仅作理论存在。中点画圆法利用判别函数F(x,y)=x²+y²-R²，通过中点M的符号在两个候选点中取舍，并推导出判别式d的递推公式与初始值，避免重复计算。Bresenham算法对d的初值与计算方式做整数化改进，消除浮点运算。正负法依据F值的正负决定向右或向下步进，同样免去浮点运算，但可能重复画点，生成质量也稍逊。

椭圆部分先说明其对称性，只需画出第一象限的四分之一弧。中点画椭圆法以F(x,y)=bx²+ay²-ab为判别函数，根据法向量分界点把弧分为上下两区：上部沿x方向步进，下部沿y方向反向步进，分别给出判别式的增量递推式，以减少每次的计算量。