计算机图形学——多边形区域填充算法
本⽂主要分析并实现了2种常见的多边形填充算法：逐点法、有序边表法
1.逐点法
在逐点法实现中，⽤到了两个函数。
其中的实现原理⼗分简单，不过PointInPolygon(int pointNumOfPolygon, CPoint tarPolygon[], CPoint testPoint)函数的实现⽐较复杂，但这个函数也⼗分实⽤，在后⾯的三⾓剖分中也有使⽤。
算法描述：
（1）将给定多边形输⼊；
（2）求出多边形的最⼩包含矩形；
incursion（3）逐点扫描最⼩矩形的每⼀点，并判断是否位于多边形内部，从最⼩点到最⼤点⼀次判断，如果在该多边形内部，则将该点上⾊；
（4）判断位于多边形内部的⽅法是，过每⼀点⽔平向右作射线，与多边形边界求交点，如果交点个数为
奇数，则说明该点在多边形内部，偶数则说明在多边形外部。
效果如下：
实现代码：
//逐点法填充
void PointFillpoly(int pNumbers, CPoint *points, CDC *pDC)
{
BoxRect_t polyRect;
polyRect =getPolygonRect(pNumbers, points);
m_pDC->MoveTo(polyRect.minX, polyRect.minY);
m_pDC->LineTo(polyRect.minX, polyRect.maxY);
m_pDC->LineTo(polyRect.maxX, polyRect.maxY);
m_pDC->LineTo(polyRect.maxX, polyRect.minY);
m_pDC->LineTo(polyRect.minX, polyRect.minY);
CPoint testPoint;
//从最⼩点到最⼤点⼀次判断，如果在该多边形内部，则进⾏填充
for(testPoint.x = polyRect.minX; testPoint.x < polyRect.maxX; testPoint.x++) for(testPoint.y = polyRect.minY; testPoint.y < polyRect.maxY; testPoint.y++){ if(PointInPolygon(m_pNumbers, m_pAccord, testPoint))
pDC->SetPixel(testPoint.x, testPoint.y,RGB(255,255,255));
}
}
//得到该多边形的最⼤、最⼩的y、x值
BoxRect_t getPolygonRect(int pointNumOfPolygon, CPoint tarPolygon[])
{
BoxRect_t boxRect;外表英语
boxRect.minX =50000;
boxRect.minY =50000;
boxRect.maxX =-50000;
boxRect.maxY =-50000;
for(int i =0; i < pointNumOfPolygon; i++){
if(tarPolygon[i].x < boxRect.minX) boxRect.minX = tarPolygon[i].x;
if(tarPolygon[i].y < boxRect.minY) boxRect.minY = tarPolygon[i].y;
if(tarPolygon[i].x > boxRect.maxX) boxRect.maxX = tarPolygon[i].x;
if(tarPolygon[i].y > boxRect.maxY) boxRect.maxY = tarPolygon[i].y;
}
return boxRect;
河北衡水中学网站
}london olympic games
//判断点是否位于区域内
BOOL PointInPolygon(int pointNumOfPolygon, CPoint tarPolygon[], CPoint testPoint)
{
if(pointNumOfPolygon <3)
return fal;
bool inSide = FALSE;
float lineSlope, interSectX;
int i =0, j = pointNumOfPolygon -1;
for(i =0; i < pointNumOfPolygon; i++){
if((tarPolygon[i].y < testPoint.y && tarPolygon[j].y >= testPoint.y ||
tarPolygon[j].y < testPoint.y && tarPolygon[i].y >= testPoint.y)&&
(tarPolygon[i].x <= testPoint.x || tarPolygon[j].x <= testPoint.x)){
if(tarPolygon[j].x != tarPolygon[i].x){
lineSlope =(float)(tarPolygon[j].y - tarPolygon[i].y)/(tarPolygon[j].x - tarPolygon[i].x);
interSectX =(int)(tarPolygon[i].x +(testPoint.y - tarPolygon[i].y)/ lineSlope);
}在线中文翻译成韩文
el
interSectX = tarPolygon[i].x;
if(interSectX < testPoint.x)
inSide =!inSide;
}
j = i;
}
return inSide;
}
2.有序边表法
⾸先给出有序边表法中定义使⽤的变量。
int m_Begin, m_End, m_edgeNumbers, m_Scan;//求交边集指针，有效边数，当前扫描位置
float m_yMax[N], m_yMin[N], m_Xa[N], m_Dx[N];//每条边y最⼤值，y最⼩值，每条边与扫描线x的交点，每条边斜率倒数
基本思想：⽤⽔平扫描线从上到下（或从下到上）扫描由多条⾸尾相连的线段构成的多边形，每根扫描线与多边形的某些边产⽣⼀系列交点。将这些交点按照x坐标排序，将排序后的点两两成对，作为线段的两个端点，以所填的颜⾊画⽔平直线。
在实现中⾸先需要对多边形的每⼀条边进⾏处理操作，因为是采⽤⽔平线扫描填充，所以对于⽔平线不做处理。对其余边根据端点的y 值⼤⼩进⾏排序，保存yMax，yMin，Xa(相对应的x坐标)以及Dx(斜率的倒数)。
在进⾏扫描的过程中，很重要的⼀部分操作便是求交边集指针的移动。初始状态位0，在扫描线开始向下移动后，调⽤Include()函数，检查是否有边进⼊扫描线交集(即判断所有y最⼤值⼤于扫描线当前y值的边线)，此时将m_End++，即尾指针向后移动。在Include()函数中，也会调整起始点位置，将Dx调整为位移量。
之后调⽤UpdateXvalue()函数，判断是否有边退出求交边集。
如果没有边退出，则移动x，并根据x值⼤⼩进⾏排序。
有边退出，更新数组，删除该边，m_Begin++，即头指针向后移动。
调⽤pFillScan(pDC)函数，进⾏填充。
m_Scan–，回到第⼆步进⾏循环，直到m_Begin==m_End。
算法描述：
建⽴边表的⽅法：
易听（1）与x轴平⾏的边不计⼊；
（2）多边形的顶点分为两⼤类：⼀类是局部极值点，另外⼀类是⾮极值点。当扫⾯线与第⼀类顶点相交时，应看作两个点；⽽当扫描线与第⼆类顶点相交时，应视为⼀个点，对于极值点则要记录两条边；
（3）扫描线按照y轴从低到⾼顺次记录；
（4）⼀条边按照y轴的⾼低记录；
（5）多条边以x轴递增顺序记录；
morita算法流程：
1、根据给出的多边形顶点坐标，建⽴NET表，求出顶点坐标中最⼤y值ymax和最⼩y值ymin。
2、初始化AET表指针，使它为空。
3、执⾏下列步骤直⾄NET和AET都为空．
（1）如NET中的第y类⾮空，则将其中的所有边取出并插⼊AET中；
（2）如果有新边插⼊AET，则对AET中各边排序；
（3）对AET中的边两两配对，（1和2为⼀对，3和4为⼀对，…），
将每对边中x坐标按规则取整，获得有效的填充区段，再填充．
（4）将当前扫描线纵坐标y值递值1；
（5）如果AET表中某记录的ymax=yj，则删除该记录 （因为每条边被看作下闭上开的）；（6）对AET中剩下的每⼀条边的x递增dx，即x’ = x+ dx ．
效果如下：
实现代码如下：
//有序边表法填充
void Fillpolygon(int pNumbers, CPoint* points, CDC* pDC)
{
m_edgeNumbers =0;
pLoadPolygon(pNumbers, points);// Polygon Loading, calculates every edge's m_yMax[],m_yMin[],m_Xa[],m_Dx[]
//求交边集范围，因为数组已经根据y值⼤⼩进⾏边的排序，所以end向后移动即代表有边进⼊，start向后移动，代表有边退出 m_Begin = m_End =0;
tyra banksm_Scan =(int)m_yMax[0];//从顶向下扫描
Include();//检查是否有边进⼊扫描线
UpdateXvalue();//检查是否有边退出扫描线
while(m_Begin != m_End){
pFillScan(pDC);
m_Scan--;
Include();
UpdateXvalue();
}
}
void pLoadPolygon(int pNumbers, CPoint* points)
{
float x1, y1, x2, y2;
x1 = points[0].x; y1 = points[0].y +0.5;
for(int i =1; i < pNumbers; i++){
x2 = points[i].x; y2 = points[i].y +0.5;
if(abs(int(y2 - y1))>=0)//⽔平线不做处理
{
pInrtLine(x1, y1, x2, y2);
x1 = x2; y1 = y2;
}
el
elephant
x2 = x1;
}
}
void pInrtLine(float x1,float y1,float x2,float y2)
{
dhdint i;
float Ymax, Ymin;
Ymax =(y2 > y1)? y2 : y1;
Ymin =(y2 < y1)? y2 : y1;
i = m_edgeNumbers;
//根据y值的⼤⼩，进⾏排序插⼊，⼤的在前⾯
while(i !=0&& m_yMax[i -1]< Ymax){
m_yMax[i]= m_yMax[i -1];
m_yMin[i]= m_yMin[i -1];
m_Xa[i]= m_Xa[i -1];
m_Dx[i]= m_Dx[i -1];
i--;
}
m_yMax[i]= Ymax;
m_yMin[i]= Ymin;
if(y2 > y1) m_Xa[i]= x2;//根据y⼤⼩确定Xa的值，y⼤的会先于扫描线相交
el m_Xa[i]= x1;
m_Dx[i]=(x2 - x1)/(y2 - y1);//斜率的倒数
m_edgeNumbers++;
}
