文档介绍：滁州学院国土信息工程系
主讲孙勇
Email:sunyong_cug@
计算机图形学
第四章多边形的扫描转换与区域填充
多边形有两种重要的表示方法:顶点表示和点阵表示。
多边形的扫描转换:把多边形的顶点表示转换为点阵表示。
区域可采用内点表示和边界表示两种表示形式。
区域填充:指先将区域的一点赋予指定的颜色,然后将该颜色扩展到整个区域的过程。
多边形分为凸多边形、凹多边形、含内环的多边形。
扫描线算法
基本思想:
按扫描线顺序,计算扫描线与多边形的相交区间,再用要求的颜色显示这些区间的象素,即完成填充工作。
对于一条扫描线填充过程可以分为四个步骤:
(1)求交(2)排序
(3)配对(4)填色
判断任意点是否在多边形内
算法思想
从该点(x, y)向( —∞, y)引直线,并计算该线与多边形的交点数n(自左向右算起)
if(n%2 == 0)
{ 则(x, y)在多边形外}
else
{ 则(x, y)在多边形内}
扫描线与多边形的顶点或边界相交时,必须正确的交点的取舍。只需检查顶点的两条边的另外两个端点的y值。按这两个y值中大于交点y值的个数是0,1,2来决定。
实际上将多边形的每条边与所有扫描线都求交点没有必要的。因为可能大多数扫描线与多边形根本不相交。为了提高算法效率,应只处理与多边形相交的那些扫描线,同时,交点的计算可以通过增量法来实现
扫描线填色法
一个多边形与若干扫描线
数据结构
活性边表(AET):把与当前扫描线相交的边称为活性边,并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中
结点内容
x:当前扫描线与边的交点坐标
△x:从当前扫描线到下一条扫描线间x的增量
ymax:该边所交的最高扫描线号ymax