文档介绍：第四章填充图元的生成
扫描转换矩形
扫描转换多边形
扫描转换扇形区域
区域填充
以图像填充区域
字符的表示与输出
1
一般步骤
确定那些像素位于填充图元的内部
确定以什么颜色填充这些像素
2
扫描转换矩形(1/2)
方法:
void FillRectangle(Rectangle *rect,int color)
{ int x,y;
for(y = rect->ymin;y <= rect->ymax;y++)
for(x = rect->xmin;x <= rect->xmax;x++)
PutPixel(x,y,color);
}/*end of FillRectangle() */
3
扫描转换矩形(2/ 2)
问题:
矩形是简单的多边形,那么为什么要单独处理矩形?
共享边界如何处理?
原则:左闭右开,下闭上开
属于谁?
4
扫描转换多边形(1/ 19)
多边形的表示方法
顶点表示
点阵表示
扫描转换多边形:将顶点表示形式转换成点阵表示形式
5
扫描转换多边形(2/ 19)
逐点判断算法
方法
void FillPolygonPbyP(Polygon *P,int polygonColor)
{ int x,y;
for(y = ymin;y <= ymax;y++)
for(x = xmin;x <= xmax;x++)
if(IsInside(P,x,y))
PutPixel(x,y,polygonColor);
else
PutPixel(x,y,backgroundColor);
}/*end of FillPolygonPbyP() */
6
扫描转换多边形(3/ 19)
问题:如何判别点(x,y)关于多边形区域P的内外关系?
射线法
步骤:
从待判别点v发出射线
求交点个数k
K的奇偶性决定了点与多边形的内外关系
奇异情况处理
7
扫描转换多边形(4/ 19)
累计角度法
步骤
从v点向多边形P顶点发出射线,形成有向角
计算有相交的和,得出结论
奇异情况处理
例子:五角星
离散计算方法:编码方法
8
扫描转换多边形(5/ 19)
算法优点:简单
算法缺点:计算量太大,速度慢
扫描线算法
目标:利用像素之间的连贯性,提高算法效率
处理对象:非自交多边形
9
扫描转换多边形(6/ 19)
基本原理
一条扫描线与多边形的边有偶数个交点
步骤:
求交
排序
填充
演示:MorphInk
10