Fillpolygon算法

填充算法很多，比如扫描线填充，种子填充等
http://www.codeproject.com/KB/GDI/QuickFill.aspx
http://blog.sina.com.cn/s/blog_55a8a96d0100084k.html
　扫描线来源于光栅显示器的显示原理：对于屏幕上所有待显示像素的信息，将这些信息按从上 到下、自左至右的方式显示。因此，扫描线多边形区域填充算法的基本原理是，待填充区域按y方向(x方向亦可)扫描线顺序扫描生成。具体实现时，首先按扫描 线顺序，计算扫描线与多边形的相交区间；再用指定的颜色填充这些区间内的像素，即完成这一条扫描线的填充工作。区间的端点可以通过计算扫描线与多边形边界 的交点获得。
　　为了提高效率，在处理每一条扫描线时，仅对与它相交的多边形的边进行求交运算。我们把当前扫描线相交的边称为活性边(active edge)，并把它们按扫描线交点x坐标递增的顺序存放在一个链表中，称此链表为活性边表(AET)。
　　为了提高速度，假定当前扫描线与多边形某一条边的交点的x坐标为xi，则下一条扫描线与该点的交点不需要重新计算，而是通过增加一个增量⊿x来获得。对于直线ax+by+c=0,⊿x=-b/a为常数。
　　另外使用增量法计算时，还需要知道一条边何时不再与下一条扫描线相交，以便及时把它从活性边表中删除出去。因此，活性边表结点的数据结构应保存如下内 容：第1项保存当前扫描线与边的交点坐标x值；第2项保存从当前扫描线到下一条扫描线间x的增量⊿x；第3项保存该边所交的最高扫描线好ymax。
　　为了方便活性边表的建立与更新，可为每一条扫描线建立一个边表(ET)，存放在该扫描线第一次出现的边。也就是说，若某边的较低端点为ymin，则该边就放在扫描线ymin的边表中。
算法过程如下： <div>void FillPolygon(多边形 polygon,int color)
{
     for (各条扫描线,标示为i)
     {
          初始化边表头指针ET[i];
          把ymin=i的边放入ET[i];
     }
     y=最低扫描线号;
     初始化活性边表AET为空;
     for (各条扫描线i)
     {
          把边表ET[i]中的边结点用插入排序法插入AET表,使之按x坐标递增顺序排列;
          遍历AET表,把配对交点区间上的像素(x,y)填色;
          遍历AET表,把ymax=i的结点从AET表中删除,并把ymax>i结点的x值递增⊿x;
          若允许多边形的边自相交，则用冒泡排序法对AET表重新排序;
     }
}</div> <div>　　扫描线与多边形顶点相交时，必须正确的进行交点个数计算，否则，在进行填充时会出现错 误。扫描线与多边形相交的边分处扫描线的两侧，则计一个交点；扫描线与多边形相交的边分处扫描线同侧，且yi<y(i- 1),yi<y(i+1)，则计2个交点，若yi>y(i-1),yi>y(i+1)，则计0个交点；扫描线与多边形边界重合，则计1 个交点。</div>

• 上一篇 发信人 q0p (爱生活，爱拉芳), 信区 age)
• 下一篇 Atl揭秘之“对象创建”篇.