参考博⽂：
⼀、概述
电台导播⼀般来讲，计算机的填充轮廓线的⽅法有两⼤类：扫描转换和种⼦填充。
扫描转换：按扫描线的顺序确定某⼀点是否位于多边形或轮廓形范围之内。这些算法⼀般从多边形或轮廓线的“顶部”开始进⾏到“底部”。扫描转换技术适⽤于光栅扫描设备和画线显⽰器。在画线显⽰器中⽤于画剖⾯线或轮廓的阴影线。如下 种⼦填充：⾸先假定封闭轮廓线内某点是已知的。然后算法开始搜索与种⼦相邻且位于轮廓线内的点。如果相邻点不位于轮廓线内，那么就已经到达轮廓线的边界。如果相邻点位于轮廓线内，那么这个点就
成为新的种⼦点，然后继续递归地搜索下去，种⼦填充算法只适⽤于光栅扫描设备。
⼆、多边形填充
多边形
顶点表⽰就是⽤多边形的顶点序列来表⽰多边形。点阵表⽰是⽤位于多边形内的象素集合来表⽰多边形。顶点表⽰占内存少，⼏何意义强，易于进⾏⼏何变换；⽽点阵表⽰丢失了许多⼏何信息（如边界、顶点）。但光栅显⽰图形需要点阵表⽰形式。
多边形的扫描转换就是把多边形的顶点表⽰转换为点阵表⽰。
多边形扫描转换
填充多边形最简单的⽅法就是：
检查光栅的每⼀像素是否位于多边形内。但是这种效率实在太低了。有⼈曾经想到要⽤包围盒来减少计算量，所谓包围盒就是包含该多边形的最⼩矩形。只有在包围盒的那些点需要检查。但是这个算法如果遇到下右图也不见得是种好⽅法。
于是有⼈提出了多边形的扫描转换，在给定的扫描线上，像素这种特性只在多边形的边和该扫描线交点处才会发⽣变化。于是我们就可以拿这些交点来操作，通过⼀系列算法进⾏填充，⽐如下图：
我们可以看到，扫描线2和多边形交于x=1和x=8，这两个交点把扫描线分成了三段：
x<1 多边形外
1<=x<=8 多边形内
x>8 多边形外
我们只需要把1<=x<=8，y=2，这段像素置成填充的值，⽽x<1,y=2;x>8,y=2这段像素置成背景⾊就可以了。以此类推，只要是能求出交点，让计算机把交点认识清楚，就能够准确⽆误的完成填充。那么怎么“认识”交点呢？
关于这个⽅法，有⼈提出了简单的奇偶扫描转换算法，它的主要思路就是：在扫描线开始时，奇偶位设置为0，表⽰扫描线在多边形的外部；扫描线与多边形第⼀次相交时，奇偶位设置为1，表⽰扫描线现在在多边形的内部；到下⼀个交点时，奇偶位设置为0，表⽰扫描线已通过多边形，⼜在多边形的外部。当奇偶位为0时，像素设置成多边形背景⾊，否则，设置为多边形⾊。
后来有⼈提出了更为有效的有序边表算法，它的基本思想是将多边形边与扫描线的交点进⾏排序。这个算法是本⽂的重点，最后会⽤代码实现。
1，⾸先来说下这个算法⽤到的数据结构：边表NET+活性边表AET。原理上讲，填充的时候是根据活性边表AET进⾏填充的，但是活性边表AET的更新⼜是依据边表NET。那么NET到底存储的是什么呢，⽤“边”的思路理解有点别扭，在我看来这个NET存储的就是多边形顶点与扫描线相交的信息：
数据结构：
x 当前扫描线与边的交点坐标；dx从当前扫描线到下⼀条扫描线间x的增量（(x2-x1)/(y2-y1)）；ymax 该边所交的最⾼扫描线
数据结构代码表⽰：
/*定义结构体⽤于活性边表AET和新边表NET*/
typedef struct XET
劳动价值论{
double x;
double dx, ymax;
大余篮球论坛
XET* next;
}AET,NET;
举例：
对于下图多边形：
它的边表NET就是：
我们看到扫描线1，它与P2(5,1)相交对吧~， 那么x的值就是5，由于经过P2的边有两条，⽽这两条边y的最⼤值分别是2,3；斜率的倒数分别是-3,2.5。于是边表NET头结点1后⾯跟的两个节点就这样写了
为什么扫描线4的边表为空呢，因为扫描线4与多边形相交的边p1p6,p3p4已经被记录了，不再是新边了，所以不记录了。如果还是看不懂的话，看这个blog，讲的⼀看就懂：
边表根据多边形进⾏初始化的代码如下：
/*初始化头结点*/
NET *pNET[1024];
for (i = 0; i <= MaxY; i++){
pNET[i] = new NET;
pNET[i]->dx = 0;
pNET[i]->x = 0;
pNET[i]->ymax = 0;
pNET[i]->next = NULL;
}
/*扫描并建⽴NET表*/
for (i = MinY; i <= MaxY; i++){
/*i表⽰扫描线，扫描线从多边形的最底端开始，向上扫描*/
for (int j = 0; j < vertNum;j++)
/
*如果多边形的该顶点与扫描线相交，判断该点为顶点的两条直线是否在扫描线上⽅
*如果在上⽅，就记录在边表中，并且是头插法记录，结点并没有按照x值进⾏排序，毕竟在更新AET的时候还要重新排⼀次
*所以NET表可以暂时不排序
*/
if (ThePolygon.m_Vertex[j].y == i){
/*笔画前⾯的那个点*/
if (ThePolygon.m_Vertex[(j - 1 + vertNum) % vertNum].y > ThePolygon.m_Vertex[j].y){
NET *p = new NET;
p->x = ThePolygon.m_Vertex[j].x;
p->ymax = ThePolygon.m_Vertex[(j - 1 + vertNum) % vertNum].y;范文同
p->dx = double((ThePolygon.m_Vertex[(j - 1 + vertNum) % vertNum].x - ThePolygon.m_Vertex[j].x)) / double((ThePolygon.m_Vertex[(j - 1 + vertNum) % vertN p->next = pNET[i]->next;
pNET[i]->next = p;
}
/*笔画后⾯的那个点*/
if (ThePolygon.m_Vertex[(j + 1 + vertNum) % vertNum].y > ThePolygon.m_Vertex[j].y){
NET *p = new NET;
p->x = ThePolygon.m_Vertex[j].x;奇圣胶囊
p->ymax = ThePolygon.m_Vertex[(j + 1 + vertNum) % vertNum].y;
p->dx = double((ThePolygon.m_Vertex[(j + 1 + vertNum) % vertNum].x - ThePolygon.m_Vertex[j].x)) / double((ThePolygon.m_Vertex[(j + 1 + vertNum) % vert p->next = pNET[i]->next;
pNET[i]->next = p;
}
}
}
然后就是动态的更新活性边表AET了， 更新的原则就是：
1、根据给出的多边形顶点坐标，建⽴NET表；
求出顶点坐标中最⼤y值ymax和最⼩y值ymin。
2、初始化AET表指针，使它为空。
3、执⾏下列步骤直⾄NET和AET都为空．
3.1、如NET中的第y类⾮空，则将其中的所有边取出并插⼊AET中；
3.2、如果有新边插⼊AET，则对AET中各边排序；
3.3、对AET中的边两两配对，（1和2为⼀对，3和4为⼀对，…），
将每对边中x坐标按规则取整，获得有效的填充区段，再填充．
3.4、将当前扫描线纵坐标y值递值1；
3.5、如果AET表中某记录的ymax=yj，则删除该记录（因为每条边被看作下闭上开的）；
3.6、对AET中剩下的每⼀条边的x递增dx，即x' = x+ dx ．
想要看到具体动态的步骤还是参考这篇博⽂，给的太详细了，看完肯定能知道是怎么个流程：
更新AET的代码如下：
/*建⽴并更新活性边表AET*/
for (i = MinY; i <= MaxY; i++){
/*更新活性边表AET，计算扫描线与边的新的交点x，此时y值没有达到临界值的话*/
NET *p = pAET->next;
while (p){
p->x = p->x + p->dx;
p = p->next;
}
/*更新完以后，对活性边表AET按照x值从⼩到⼤排序*/
AET *tq = pAET;
p = pAET->next;
tq->next = NULL;
while (p){
while (tq->next&&p->x >= tq->next->x)
tq = tq->next;
NET *s = p->next;
p->next = tq->next;
tq->next = p;
p = s;
tq = pAET;
}
/*从AET表中删除ymax==i的结点*/
AET *q = pAET;
p = q->next;
while (p){
if (p->ymax == i){
q->next = p->next;
delete p;
p = q->next;马家老鸡铺
}
else{
q = q->next;
p = q->next;
}
}
/*将NET中的新点加⼊AET，并⽤插⼊法按X值递增排序*/
p = pNET[i]->next;
q = pAET;
while (p){
while (q->next&&p->x >= q->next->x)
q = q->next;
NET *s = p->next;
p->next = q->next;
q->next = p;
p = s;
q = pAET;
}
/*配对填充颜⾊*/
p = pAET->next;
while (p&&p->next){
for (float j = p->x; j <= p->next->x; j++){
pDC->SetPixel(static_cast<int>(j), i,fillCol);
}
p = p->next->next;
}
}
所以整个函数的实现是这样的：
void CCGPainterView::ScanlineConvertion(CDC *pDC, MyPolygon ThePolygon, COLORREF fillCol) {
//Write your own scan-line convertion algorithm here.
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议