填充算法说明文档

1、填充算法说明文档（简单形填充（圆，椭圆）；逐点判断法；扫描线算法，边缘填充法，边界标志法）题目：简单图形填充（包括圆和椭圆）（选做） 逐点判断（选做） 自定义多边形填充 边缘填充（选做） 扫描线算法（必做） 边界标志算法（必做）功能：1，对简单图形（圆，椭圆）的填充； 2，自定义多边形的填充：可通过菜单选择不同的算法使用指南：一， 对简单图形：直接点击菜单中“简单图形-圆/椭圆”即可；二， 对于自定义多边形：1，先通过菜单选择所要使用的填充算法；2，在客户区用鼠标左键点出要填充多边形的顶点，按鼠标右键结束；程序即会调用相应的算法对该多边形填充。三， 可通过菜单中的“清屏”选项清除屏幕。模块功能

2、说明： 函数void CircleFill(POINT radius, int r, COLORREF col)生成一个以radius为原点，以r为半径的圆，并以col为颜色填充该圆； 函数void EllipseFill(POINT radius, int a, int b, COLORREF col)生成一个以radius为中心以a为长半轴，以b为短半轴的椭圆，并以col为颜色填充该椭圆； 对于自定义多边形，其顶点系列存在polygon中，顶点个数为len; 函数void PointFill(POINT point, int len, COLORREF col)用逐点判断法填充自定义多边形

3、。 函数void ScanlineFill(POINT point, int len, COLORREF col) 用扫描线算法填充自定义多边形。 函数void EdgeFill(POINT point, int len) 用边缘填充算法填充自定义多边形。 函数void FlagFill(POINT point, int len, COLORREF fillcol) 用边界标志算法填充自定义多边形。 核心算法说明：一， 对于简单圆和椭圆，由于其对称性，只需在圆的生算法中加入几个语句，即每确定了一个点时，将与该点关于Y轴对称的点连起来。二， 逐点判断法：先找出包含待填充多边形的最小矩形，然后对矩

4、形内的每一个点判断其是在多边形内还是在多边形外，如果在多边形内则对该点着填充色，如果在多边形外则不着色（或者说着背景色）；在确定一个点在多边形内还是多边形外时，运用奇偶规则：以当前点引一条射线，射线与多边形的交点个数为奇数时，点在多边形内；交点个数为偶数时，点在多边形外。三， 扫描线算法：核心思想是利用区域的连贯性，扫描线的连贯性，边的连贯性。先将与当前扫描线的交点按X由大到小连接起来，然后顺序两两配对，把配对的两点之间的点也着上填充色。具体做法是1， 建立ET表；2， （Y初始化）取扫描线纵坐标的初始值为ET中非空元素的最小序号。3， （AEL初始化）将边的活性链表AEL设置为空；4， 按从

5、下到上的顺序对纵坐标为Y的扫描线（当前扫描线）执行下列步骤，直到分类表ET和边的活化链表AEL都为空为止。如边分类表ET中的第Y类元素非空，则将属于该类的所有边从ET中取出来并插入活性链表AEL中，AEL中的各边按照X值（当X值相等时，按dx值）递增方向排序。若相对于当前扫描线，边的活性链表AEL为非空，则将AEL中的边两两肉依次配对，即第1，2边为一对，第3，4边为一对依此类推。每一对边与当前扫描线的交点所构成的区段位于多边形内，依次对这些区段上的点（象素）按多边形属性着色。将边的活性链表AEL中满足Y=Ymax的边删去。将边的活性链AEL剩下的每一条边的X域累加dx，即：X=X+dx.将当

6、前的扫描线的纵坐标值Y累加1；说明：ET中的元素是边项，每个边项有四个域组成：1，Ymax，边的上端点的Y坐标；2，X，在ET中表示边的下端点的X坐标，在AEL中则表示边与扫描线的交点的X坐标；3，dx，边的斜率的倒数；4，next 指向下一条边的指针。对于边项，程序中用一个结构Edge来表示。对ET，AEL表用一个CET类来实现。建立ET表前，要对奇点做些预处理。若Pi,是非极值点，则将Pi-1Pi,PiPi+1两边中位于扫描线Y=Yi上方的那条边在Pi处截去一个单位长。在ET建立时，先按下端点的纵坐标值对所有边作桶分类，再用排序方法按下端点X坐标递增的顺序将同一组中的边排列成行。四边缘填充

7、算法 根据余数的性质，即对M 作偶数次求余运算，其结果是M；而对M作奇数次求余运算的结果是/M。在光栅图形中，如某区域已着上值为M的某种颜色，对M作偶数次求余运算后，该区域颜色不变；而作奇数次求余运算后，该区域颜色则变为值为/M的颜色。具体算法为：先求出包含该多边形的最小矩形；对每边的右边的点做求余填充。程序中取（，），由于背景色是白色，所以（，）；根据奇偶规则易知：在多边形内的点被填充了奇数次，所得颜色为：（，）即黑色，而对多边形外的点被填充的偶数次，颜色为，即白色，还是背景色。具体代码见：函数void EdgeFill(POINT point, int len)；五边界标志算法：核心思想：

8、同样是利用奇偶规则。先对多边形的边置上特殊的标志颜色，然后对每一条扫描线，从左到右读取点，第一次读到标志颜色时，说明开始进入多边形内部，开始对点填充填充色，第二次读到标志颜色时，说明已走到多边形外面，不用对点着色（或者说着上背景色）；这样的思想与扫描线算法想同，只是省去了建立复杂的数据结构。注意事项：在理想情况下，该方法是能很好工作的。但由于计算机显示出的点是离散化的，会出现一些异常。比如说：如果直线斜率不为，理论上不会有两个不同点的纵坐标相同，但屏幕显示时确有可能出现这样的情况，在这种情况下，如果直接使用上述算法，会出现问题。我是这样处理的：为了保证不会出现上面的情况，强制一条直线与扫描线有

9、最多只有一个交点，当出现多个时，不同点的纵坐标相同时，只对较左的一点着上边界标志色；这样可以保证一条直线与扫描线最多只有一个交点。另一种异常是：当多边形的角很尖时，有可能使相邻两边的部分点重合在一起，这样读点时只能读到一次边界标志色，如再使用奇偶规则，会导致多边形外面的点被着色。我是这样处理的：对边着边界标志色时，先对其判断，如果该点已是边界色了，就对该点着上填充色。这样便可解决上述问题。但对于某些图形，还有会有个别异常，有待进一步调试。小结：上述几种填充算法，对于简单图形利用其对称性，这种方法有比较大的局限性；逐点判断法计算量比较大，比较慢，但方法比较简单，填充的图形类型比较多，；扫描线算法比较快，适合用软件实现，但算法比较复杂，对于有边相交的情况，有可能出现异常。边缘填充，比较慢，对同一点有很多重复操作，方法简单；边界标志法，比较快，特别适合用硬件实现，方法思想很简单，但细节比较多，要用到一些技巧； 函数void EllipsePN(POINT point, int a, int