1.一种计算机绘图用的多边形填充方法,包括以下步骤:
步骤一:对多边形的顶点依次编号;
步骤二:计算并获取最优栅栏线的坐标;
步骤三:设置像素填充为取补模式;
步骤四:计算水平扫描线与多边形的交点并填充扫描线段;
步骤五:用水平扫描线逐行扫描每条边上的每个像素点,重复步骤四直至扫描完毕;
步骤六:填充完成。
2.根据权利要求1所述的计算机绘图用的多边形填充方法,其特征在于,所述步骤一具体步骤为:对多边形所有顶点进行顺时针或逆时编号P1(x1,y1),P2(x2,y2),…,Pn(xn,yn),Pn+1(xn+1,yn+1),其中P1(x1,y1)表示第1个顶点P1的坐标为x1,y1,P2(x2,y2)表示第2个顶点P2的坐标为x2,y2,Pn(xn,yn)表示第n个顶点Pn的坐标为xn,yn,Pn+1(xn+1,yn+1)是为便于计算引入的辅助顶点,其值等于P1(x1,y1),从而构成封闭多边形图形。
3.根据权利要求1所述的计算机绘图用的多边形填充方法,其特征在于,所述步骤二具体步骤为:(2-1)获取多边形边界范围:扫描多边形的各个顶点坐标,得到max_x、min_x、max_y、min_y,max_x表示x坐标的最大值,min_x表示x坐标的最小值,max_y表示y坐标的最大值,min_y表示y坐标的最小值;
(2-2)初始化栅栏线:随机生成栅栏线的x轴坐标为X,满足X=min_x;
(2-3)计算最优栅栏线位置:
对于多边形的由相邻顶点Pi(xi,yi)和Pi+1(xi+1,yi+1)所在的边Li,i=1,…n,边Li在栅栏线上投影区的面积Si分两种情况讨论:(1)、边Li的两个顶点Pi(xi,yi)、Pi+1(xi+1,yi+1)都在栅栏线一侧,此时投影区正好为一个直角梯形;(2)、Li的两个顶点Pi(xi,yi)、Pi+1(xi+1,yi+1)分别在栅栏线两侧,则先求出两个顶点Pi(xi,yi)、Pi+1(xi+1,yi+1)的交点Ci(xi,yi),再以交点为顶点分成两条边看待;两种情况均按照以下方式处理,最优栅栏线坐标Best_X满足当X=Best_X时,下列公式的值最小:其中xi为第i个顶点的横坐标,yi为第i个顶点的纵坐标,X为栅栏线的横坐标,xi+1为第i+1个顶点的横坐标,yi+1为第i+1个顶点的纵坐标。
4.根据权利要求3所述的计算机绘图用的多边形填充方法,其特征在于,所述步骤二中,最优栅栏线的获得步骤为:(2-2-1):令初始栅栏线X=min_x;i=1;第一个临时量delta1=+∞;第二个临时变量delta2=0;第三个临时量k′=min_x;
(2-2-2):对于第j条可行的栅栏线Xj,1≤j≤n,j∈Z,Z为整数,求若delta2
{delta1→delta2;k′→Xj;};
(2-2-3)令j→j+1;若Xj
5.根据权利要求4所述的计算机绘图用的多边形填充方法,其特征在于,所述步骤三具体步骤为:设置颜色填充为取补模式,在取补模式下,当填充次数为奇数次时,填充颜色为当前颜色,当填充次数为偶数次时,填充颜色显示为背景色。
6.根据权利要求5所述的计算机绘图用的多边形填充方法,其特征在于,所述步骤四具体步骤为:令水平扫描线的y轴坐标为Y,该水平扫描线与多边形的第i条边Li相交于点Cl(xl,Y),与栅栏线相交于点Dl(X,Y),则线段ClDl上所有的像素都设置为当前颜色。
7.根据权利要求3所述的计算机绘图用的多边形填充方法,其特征在于:所述步骤(2-
3)中,边Li在栅栏线上投影区的面积Si的第(1)种情况中,包括一顶点在栅栏线上的情况,此时投影区为直角三角形。