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