填充算法说明文档.docVIP

填充算法说明文档 （简单形填充（圆，椭圆）；逐点判断法；扫描线算法，边缘填充法，边界标志法） 题目：简单图形填充（包括圆和椭圆）（选做） 逐点判断（选做） 自定义多边形填充 边缘填充（选做） 扫描线算法（必做） 边界标志算法（必做） 功能：1，对简单图形（圆，椭圆）的填充； 2，自定义多边形的填充：可通过菜单选择不同的算法 使用指南： 对简单图形：直接点击菜单中“简单图形-?圆/椭圆”即可； 对于自定义多边形：1，先通过菜单选择所要使用的填充算法；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)用逐点判断法填充自定义多边形。 函数void ScanlineFill(POINT point[], int len, COLORREF col) 用扫描线算法填充自定义多边形。 函数void EdgeFill(POINT point[], int len) 用边缘填充算法填充自定义多边形。 函数void FlagFill(POINT point[], int len, COLORREF fillcol) 用边界标志算法填充自定义多边形。 核心算法说明： 对于简单圆和椭圆，由于其对称性，只需在圆的生算法中加入几个语句，即每确定了一个点时，将与该点关于Y轴对称的点连起来。 逐点判断法：先找出包含待填充多边形的最小矩形，然后对矩形内的每一个点判断其是在多边形内还是在多边形外，如果在多边形内则对该点着填充色，如果在多边形外则不着色（或者说着背景色）；在确定一个点在多边形内还是多边形外时，运用奇偶规则：以当前点引一条射线，射线与多边形的交点个数为奇数时，点在多边形内；交点个数为偶数时，点在多边形外。 扫描线算法：核心思想是利用区域的连贯性，扫描线的连贯性，边的连贯性。先将与当前扫描线的交点按X由大到小连接起来，然后顺序两两配对，把配对的两点之间的点也着上填充色。具体做法是 建立ET表； （Y初始化）取扫描线纵坐标的初始值为ET中非空元素的最小序号。 （AEL初始化）将边的活性链表AEL设置为空； 按从下到上的顺序对纵坐标为Y的扫描线（当前扫描线）执行下列步骤，直到分类表ET和边的活化链表AEL都为空为止。  = 1 \* GB3 ①．如边分类表ET中的第Y类元素非空，则将属于该类的所有边从ET中取出来并插入活性链表AEL中，AEL中的各边按照X值（当X值相等时，按dx值）递增方向排序。  = 2 \* GB3 ②若相对于当前扫描线，边的活性链表AEL为非空，则将AEL中的边两两肉依次配对，即第1，2边为一对，第3，4边为一对依此类推。每一对边与当前扫描线的交点所构成的区段位于多边形内，依次对这些区段上的点（象素）按多边形属性着色。  = 3 \* GB3 ③将边的活性链表AEL中满足Y=Ymax的边删去。  = 4 \* GB3 ④将边的活性链AEL剩下的每一条边的X域累加dx，即：X=X+dx.  = 5 \* GB3 ⑤将当前的扫描线的纵坐标值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建立时，先按下