
工程计算机图形学第四部分图形处理基本算法.ppt
17页工程计算机图形学第四章 图形处理基本算法浙江大学工程及计算机图学所浙江大学工程及计算机图学所 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工程及计算机图形学工程及计算机图形学浙江大学工程及计算机图学所浙江大学工程及计算机图学所 拓扑变化的概念 作为点集的几何图形,如果在变换时正逆两方面的两图形都是单值而且连续对应,则这种对应称为拓扑映射,相应的几何变换称为拓扑变换圆的拓扑映射图4-1-3半圆的拓扑映射图4-1-44工程及计算机图形学工程及计算机图形学浙江大学工程及计算机图学所浙江大学工程及计算机图学所4.1多边形的方向及顶点的凸凹性判断2.经典算法介绍经典算法介绍((1)凸凹性判断经典算法)凸凹性判断经典算法 5图4-1-5工程及计算机图形学工程及计算机图形学浙江大学工程及计算机图学所浙江大学工程及计算机图学所4.1多边形的方向及顶点的凸凹性判断((2)方向性判断经典算法)方向性判断经典算法--有向面积法有向面积法如果sp>0,则多边形顶点以逆时针方向连接;如果sp<0,则多边形顶点以顺时针方向连接;如果sp=0,则多边形所有顶点共线,这与简单多边形的定义相矛盾,因此可以不予考虑。
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多边形的方向及顶点的凸凹性判断((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工程及计算机图形学工程及计算机图形学浙江大学工程及计算机图学所浙江大学工程及计算机图学所4.2点在多边形内外判断n3.交点计数检验法交点计数检验法 当多边形是凹多边形,甚至还带孔时,可采用交点计数检验法判断点是否在多边形内具体做法是从判断点P0作一射线至无穷远,然后求射线与多边形的交点,若交点个数为奇数,则点在多边形内,否则点在多边形外 特殊情况:特殊情况:若共享顶点的两边在射线的同一侧,则交点计数加2,否则加1具体计数时,当一条边的两端点y值都大于y0,即边处于射线上方时,计数加1,否则不加13图4-1-14图4-1-15工程及计算机图形学工程及计算机图形学浙江大学工程及计算机图学所浙江大学工程及计算机图学所4.3曲线数据压缩算法n命题: 点数多、局部分布密集、整体分布情况复杂等特征的曲线压缩、简化;要求尽可能保持特征14图4-1-16工程及计算机图形学工程及计算机图形学浙江大学工程及计算机图学所浙江大学工程及计算机图学所n顶点减少法步骤一:确定阀值步骤一:确定阀值ε。
当前点与前一个点的距离小于阀值时,舍弃当前点;当前点与前一个点的距离小于阀值时,舍弃当前点;当前点大于等于阀值时,记录当前点,并将当前点设为新的起始点当前点大于等于阀值时,记录当前点,并将当前点设为新的起始点步骤二:选取作为起始点,并记录计算与的距离,如果距离大于步骤二:选取作为起始点,并记录计算与的距离,如果距离大于ε,记,记录,并将作为新的起始点;如果距离小于录,并将作为新的起始点;如果距离小于ε,舍弃,并继续判断与的距离,,舍弃,并继续判断与的距离,直到找到一个与的距离大于直到找到一个与的距离大于ε的点,记录新的点,并将新的点作为新的起的点,记录新的点,并将新的点作为新的起始点步骤三:反复进行步骤二,直到最后一个点步骤三:反复进行步骤二,直到最后一个点154.3曲线数据压缩算法图4-1-17工程及计算机图形学工程及计算机图形学浙江大学工程及计算机图学所浙江大学工程及计算机图学所nDouglas-Peucker算法步骤一:确定阀值ε步骤二:先连接第一个和最后一个边界网格顶点,计算这对基准顶点对之间的点到基准线的距离如果有一个及一个以上的点到基准线的距离大于ε,将距离基准线最远的点记为第n个点,删除基准线,并将第一个点和第n个点记为基准顶点对,将第n个点和最后一个点记为基准顶点对;如果所有点到基准线的距离都小于等于ε,删除基准顶点之间的所有点,只保留基准顶点对作为基准顶点对之间曲线的控制顶点。
步骤三:重复将步骤二中得到的基准顶点对进行步骤二的计算,直到所有点到他们的基准线的距离都小于等于ε 164.3曲线数据压缩算法图4-1-18工程及计算机图形学工程及计算机图形学浙江大学工程及计算机图学所浙江大学工程及计算机图学所nDouglas-Peucker算法的问题公共边分裂自相交的出现174.3曲线数据压缩算法图4-1-19。












