v逐点判断法 FANG UNINES #define maX 100 Typedef struct{ int PolygonUm;∥多边形顶点个数 Point vertexes MAX]∥多边形顶点数组 } Polygon∥多边形结构 void FillPolygon P(Polygon*Pint polygon Color for(y=ymin; y <=ymax; y++) forex=xmin; x <=xmax; x++) if(iNside (p x, y)) PutPixel(x, v, polygoncolor); else PutPixel(x, y, backgroundcolor); B/*end of fillPolygonPbyP0*/ 2021/1/21 浙江大学计算机图形学 7
2021/1/21 浙江大学计算机图形学 7 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() */ #define MAX 100 Typedef struct { int PolygonNum; // 多边形顶点个数 Point vertexces[MAX] //多边形顶点数组 } Polygon // 多边形结构 逐点判断法
逐点判断法 逐个判断绘图窗口内的像素: n如何判断点在多边形的内外关系? 1)射线法: 2)累计角度法 3)编码法; 2021/1/21 浙江大学计算机图形学
2021/1/21 浙江大学计算机图形学 8 逐点判断法 ◼ 逐个判断绘图窗口内的像素： ◼ 如何判断点在多边形的内外关系？ 1）射线法： 2）累计角度法 3）编码法；
逐点判断法 1)射线法 步骤: 从待判别点v发出射线 2.求交点个数k K的奇偶性决定了点与多边形的内外关系 2021/1/21 冽让人子昇饥囹形字
2021/1/21 浙江大学计算机图形学 9 逐点判断法 1）射线法 ◼ 步骤： 1. 从待判别点v发出射线 2. 求交点个数k 3. K的奇偶性决定了点与多边形的内外关系
逐点判断法 2)累计角度法 步骤 从v点向多边形P顶点发出射线,形成有向角O 2.计算有相交的和,得出结论 0,w位于P之外 0 ±2x,n位于P之内 B 2021/1/21 浙江大学计算机图形学
2021/1/21 浙江大学计算机图形学 10 逐点判断法 2）累计角度法 ◼ 步骤 1. 从v点向多边形P顶点发出射线，形成有向角 2. 计算有相交的和，得出结论 = = 位于 之内 ， 位于 之外 v P n v P i i 2 , 0 0 i
逐点判断法 ■逐点判断的算法虽然程序简单,但不可取。原 因是速度太慢,主要是由于该算法割断了各象 素之间的联系,孤立地考察各象素与多边形的 内外关系,使得几十万甚至几百万个象素都要 判别,每次判别又要多次求交点,需要做 大量的乘除运算,花费很多时间。 2021/1/21 浙江大学计算机图形学
2021/1/21 浙江大学计算机图形学 11 逐点判断法 ◼ 逐点判断的算法虽然程序简单，但不可取。原 因是速度太慢，主要是由于该算法割断了各象 素之间的联系，孤立地考察各象素与多边形的 内外关系，使得几十万甚至几百万个象素都要 一一判别，每次判别又要多次求交点，需要做 大量的乘除运算，花费很多时间