《工程计算机图形学第四部分图形处理基本算法.ppt》由会员分享，可在线阅读，更多相关《工程计算机图形学第四部分图形处理基本算法.ppt（17页珍藏版）》请在三一办公上搜索。
1、工程计算机图形学第四章 图形处理基本算法,浙江大学工程及计算机图学所,1,SHU Graphics&Image Group,浙江大学工程及计算机图学所,主要内容,多边形的方向及顶点的凸凹性判断点在多边形内外判断曲线数据压缩算法,2,浙江大学工程及计算机图学所,4.1多边形的方向及顶点的凸凹性判断,1.基本概念凸凹性的定义 如图所示。如果与Pi(i=1,2,，n)相关联的两条边Pi-1 Pi与Pi Pi+1所夹的角小于或等于，则称顶点Pi是凸的，否则称顶点Pi 是凹的。,3,图4-1-1,图4-1-2,浙江大学工程及计算机图学所,拓扑变化的概念 作为点集的几何图形，如果在变换时正逆两方面的两图形
2、都是单值而且连续对应，则这种对应称为拓扑映射，相应的几何变换称为拓扑变换,4,浙江大学工程及计算机图学所,4.1多边形的方向及顶点的凸凹性判断,2.经典算法介绍（1）凸凹性判断经典算法,5,图4-1-5,浙江大学工程及计算机图学所,4.1多边形的方向及顶点的凸凹性判断,（2）方向性判断经典算法-有向面积法,如果sp0，则多边形顶点以逆时针方向连接；如果sp0，则多边形顶点以顺时针方向连接；如果sp=0，则多边形所有顶点共线，这与简单多边形的定义相矛盾，因此可以不予考虑。,6,图4-1-6,浙江大学工程及计算机图学所,4.1多边形的方向及顶点的凸凹性判断,（3）方向性判断快速算法规则1：多边形方
3、向与同构凸多边形方向相同规则2：多边形方向与凸点的方向相同？,7,图4-1-7,图4-1-8,浙江大学工程及计算机图学所,4.1多边形的方向及顶点的凸凹性判断,（4）方向性判断新思路,8,图4-1-9,浙江大学工程及计算机图学所,4.1多边形的方向及顶点的凸凹性判断,9,图4-1-10,浙江大学工程及计算机图学所,4.1多边形的方向及顶点的凸凹性判断,（3）方向性判断新思路,XXXi-1 XXXi+1，顶点为凸顶点,XXXi-1 XXXi+1，顶点为凸顶点,10,图4-1-11,浙江大学工程及计算机图学所,4.1多边形的方向及顶点的凸凹性判断,实质上与叉乘法等效,11,图4-1-12,浙江大学
4、工程及计算机图学所,4.2点在多边形内外判断,1.叉积判断法点在凸多边形内的充要条件是叉积Vi Vi+1（i=1,2,n）的符号相同。叉积判断法仅适用于凸多边形 2.夹角之和检验法若 则点在多边形内；若 则点在多边形外,12,图4-1-13,浙江大学工程及计算机图学所,4.2点在多边形内外判断,3.交点计数检验法 当多边形是凹多边形，甚至还带孔时，可采用交点计数检验法判断点是否在多边形内。具体做法是从判断点P0作一射线至无穷远，然后求射线与多边形的交点，若交点个数为奇数，则点在多边形内，否则点在多边形外 特殊情况：若共享顶点的两边在射线的同一侧，则交点计数加2，否则加1。具体计数时，当一条边的
5、两端点y值都大于y0，即边处于射线上方时，计数加1，否则不加,13,图4-1-14,图4-1-15,浙江大学工程及计算机图学所,4.3曲线数据压缩算法,命题：点数多、局部分布密集、整体分布情况复杂等特征的曲线压缩、简化；要求尽可能保持特征,14,图4-1-16,浙江大学工程及计算机图学所,顶点减少法步骤一：确定阀值。当前点与前一个点的距离小于阀值时，舍弃当前点；当前点大于等于阀值时，记录当前点，并将当前点设为新的起始点。步骤二：选取作为起始点，并记录。计算与的距离，如果距离大于，记录，并将作为新的起始点；如果距离小于，舍弃，并继续判断与的距离，直到找到一个与的距离大于的点，记录新的点，并将新的
6、点作为新的起始点。步骤三：反复进行步骤二，直到最后一个点。,15,4.3曲线数据压缩算法,图4-1-17,浙江大学工程及计算机图学所,Douglas-Peucker算法步骤一：确定阀值。步骤二：先连接第一个和最后一个边界网格顶点，计算这对基准顶点对之间的点到基准线的距离。如果有一个及一个以上的点到基准线的距离大于，将距离基准线最远的点记为第n个点，删除基准线，并将第一个点和第n个点记为基准顶点对，将第n个点和最后一个点记为基准顶点对；如果所有点到基准线的距离都小于等于，删除基准顶点之间的所有点，只保留基准顶点对作为基准顶点对之间曲线的控制顶点。步骤三：重复将步骤二中得到的基准顶点对进行步骤二的计算，直到所有点到他们的基准线的距离都小于等于。,16,4.3曲线数据压缩算法,图4-1-18,浙江大学工程及计算机图学所,Douglas-Peucker算法的问题,公共边分裂,自相交的出现,17,4.3曲线数据压缩算法,图4-1-19,
