y=e y=d
边的连贯性

扫描线算法(7/26)
特别是当存在某一个整数k,0≤k≤n-1,使得 yik>e, d>yik+1 成立时，则由区域的连贯性可知d的交点序列 和e的交点序列之间有以下关系： 1）两序列元素的个数相等，如上图所示。 2）点(xeir,e)与(xdjr,d)位于多边形P的同一边上， 于是 xeir= xdjr + 1/kjr (2) 这样，运用递推关系式(2)可直接由d的交点序 列和e的获得e的交点序列。 以上性质称为边的连贯性，它是区域的连贯性 在相邻两扫描线上的反映。
1.
4.1多边形的定义
定义：一系列首尾相连的线段构成的图形。 线段 -------- 边 端点 -------- 顶点

一般情况：多边形是封闭的
多边形分为凸多边形、凹多边形二种
凸多边形：连多边形内任意两点的 线段,该线段上的点均在多边形内。
计算机生成的物体常常可以用若干多边形 来描述，有些非多边形的物体，也可以用 多边形来逼近。比如上一章二次曲线的绘 制我们了解了可以用多边形去逼近圆。在 多边形生成以后，就可以利用光栅显示系 统对其内部区域进行填充。 那么多边形是如何在系统中如何描述的呢？
A A
P
B
E D
B
E
P
D
C
C
若夹角和为0，则点p 若夹角和为＋360°，则 点p在多边形内 在多边形外
逐点判断法(4/7)
2）射线法
P
E A E A
P
B
B
D C
D C
交点数=偶数（包括0） 交点数=奇数 点在多边形之外 点在多边形之内
逐点判断法(5/7)
2）射线法 步骤： 从待判别点发出射线求交点个数k K的奇偶性决定了点与多边形的内 外关系 注意： 1、若射线恰好交于多边形R的端点，则如 何处理？ 2、如何决定射线方向？
pDC-> SetPixel(x,y,backgroundColor);
} // end of FillPolygonPbyP()
逐点判断的算法的优缺点： 虽然程序简单，但不可取。原因是速
度太慢，主要是由于该算法割断了各 象素之间的联系，孤立地考察各象素 与多边形的内外关系，使得几十万甚 至几百万个像素都要一一判别，每次 判别又要多次求交点，需要做大量的 乘除运算，花费很多时间。 改进思想：除边界外，相邻像素几乎 都有相同的特征。
第4章 多边形
本章我们将讨论图形系统中 新的图元——多边形，研究有 关多边形的概念以及多边形的 表示，学习如何判断一个点是 否在多边形内的方法，以及多 边形的各种填充方法，重点讲 解种子填充算法。
第4章 多边形
多边形的定义 2. 多边形的扫描转换 3. 区域填充(种子填充算法) 4. 反走样

区域的连贯性
扫描线算法(2/26)
设多边形P的顶点Pi=(xi,yi),i=0,1, …,n，又设 yi0,yi1,…yin 是各顶点Pi的坐标yi的递减数列，即yik≥yik+1,0≤k≤n-1 这样，当yik≥yik+1,0≤k≤n-1时，屏幕上位于y=yik和 y=yik+1两条扫描线之间的长方形区域被多边形P的边分割 成若干梯形（三角形可看作其中一底边长为零的梯形）， 它们具有下列性质： y=yik y=yik+1
边的连贯性
扫描线算法(5/26)
设d为一整数，并且d=e-1,并且 yi0≥d≥yin。设位 于扫描线y=d上的交点序列为xdj1,xdj2,xdj3,…,xdjk 现在来讨论扫描线d，e交点序列之间的关系。若多 边形P的边Pr-1Pr与扫描线y=e,y=d都相交，则交点序列 中对应元素xer,xdr满足下列关系： xer= xdr + 1/mr (1) 其中mr为边Pr-1Pr的斜率。
逐点判断法的算法伪码描述
#define MAX 100
Typedef struct
{
int PolygonNum; // 多边形顶点个数
Point vertexces[MAX] //多边形顶点数组
} Polygon // 多边形结构
假设整个屏幕区域只有一个多边形对整个屏幕 区域进行扫描，假设屏幕大小为1024*768 void FillPolygonPbyP(Polygon *P, int fillColor) { int x,y; for(y = 0;y <= 1023;y++) for(x = 0;x <= 767;x++) if(IsInside(P,x,y)) pDC-> SetPixel(x,y, fillColor); else pDC-> SetPixel (x,y,backgroundColor); } // end of FillPolygonPbyP()
扫描线算法

扫描线算法
目标：利用相邻像素之间的连贯性，提高算法
效率 处理对象：非自交多边形 （边与边之间除了 顶点外无其它交点）
扫描线算法(1/26)

扫描线算法是多边形扫描转换的常用算法。 与逐点判断算法相比，扫描线算法充分利 用了相邻象素之间的连贯性，避免了对象 素的逐点判断和反复求交的运算，达到了 减少了计算量和提高速度的目的。 开发和利用相邻象素之间的连贯性是光栅 图形算法研究的重要内容。扫描线算法综 合利用了区域的连贯性、扫描线连贯性和 边的连贯性等三种形式的连贯性。
区域的连贯性

扫描线算法(3/26)
1）梯形的两底边分别在y=yik和y=yik+1两条扫描线上， 腰在多边形P的边上或在显示屏幕的边界上。 2）这些梯形可分为两类：一类位于多边形P的内部； 另一类在多边形P的外部。 3）两类梯形在长方形区域{yik,yik+1}内相间的排列，即 相邻的两梯形必有一个在多边形P内，另一个在P外。 y=yik y=yik+1
对整个多边形区域进行扫描，比扫描整个屏幕 肯定要节约时间，这是改进后的伪码描述 void FillPolygonPbyP(Polygon *P,int fillColor) { int x,y; for(y = ymin;y <= ymax;y++) for(x = xmin;x <= xmax;x++) if(IsInside(P,x,y)) pDC-> SetPixel(x,y,fillColor); else
逐点判断法(6/7)
3）符号比较法（ 适用于凸多边形） A>基础知识 二点式直线方程的表示及点与直线 的关系多边形各边所在方程的表示 方法
逐点判断法(7/7)
B>步骤 1、找多边形内一点M代入直线方
程，计算M相对于各边的符号情况。 2、对待判定定P作同样的操作 3、对M和P相对于各边的符号情 况作比较
多边形的扫描转换
常用几种方法： 逐点判断法； 扫描线算法； 边填充法； 栅栏填充法； 边界标志法。

逐点判断法(1/7)
算法思想： 逐个象素点判别，确定它们是否在多 边形内，从而来决定是否进行着色。 如何判断点在多边形的内外关系？

1）累计角度法(转角和法)； 2）射线法； 3）符号法；
扫描线的连贯性

扫描线算法(4/26)

求出扫描线与多边形的所有交点后，位于多边形 内的直线段就不难找到了。 设想我们从扫描线的一端出发，这时我们在多边 形外，因为多边形总是在有限范围内的。 当我们 沿直线前进到达第一个交点时，就开始进入多边 形内。 由于直线的另一端是在多边形外，继续沿 直线前进一定会走出多边形内部，因此一定会遇 到第二个交点。 这时我们可以看到，第一和第二 个交点给出的直线段就位于多边形内。 如果没有更多的交点，则该扫描线上只有一段直 线段位于多边形内。 如果继续沿扫描线前进，遇到第三个交点后，重 新进入多边形内。类似前面的分析，一定有第四 个交点。于是第三、第四个交点给出的直线段就 位于多边形内。
扫描线算法(14/26)
扫描线算法(12/26)
扫描线算法(12/26)
●规则： X为小数，即交点落于扫描线上两个相 邻像素之间 (a)交点位于左边之上，向右取整 (b)交点位于右边之上，向左取整

扫描线算法(13/26)Biblioteka 扫描线算法的基本思想
基本思想：

按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的 颜色显示这些区间的象素，即完成填充工作。
扫描线算法(9/26)
奇点的处理
若奇点做二个交点处理，则情况A，交点 个数是偶数。 若奇点做一个交点处理，则情况B，交点 个数是偶数。

扫描线算法(10/26)
奇点的处理
多边形P的顶点可分为两类：极值奇
点和非极值奇点。如果(yi-1 - yi)(yi+1 - yi)≥0，则称顶点Pi为极值点；否则 称Pi为非极值点。(yi-1 和yi+1为相邻 顶点坐标) 规定：奇点是极值点时，该点按两 个交点计算，否则按一个交点计算。
扫描线算法(8/26)
奇点的处理
•当扫描线与多边形P的交点是P的顶点时，则称 该交点为奇点。 •以上所述多边形的三种形式的连贯性都基于这 样的几何事实：每一条扫描线与多边形P的边界 的交点个数都是偶数。但是如果把每一奇点简 单地计为一个交点或者简单地计为两个交点， 都可能出现奇数个交点。那么如果保证交点数 为偶数呢？
逐点判断法(2/7)
1）累计角度法（转角和法） 步骤
1.从某点向多边形顶点发出射线，形成 有向角 2.计算有向角的和，得出结论
0，v位于P之外 i i 0 2 , v位于P之内
n
若等于正负180度表示V在边界上。 该方法适用于：凸多边形、凹多边 形