工程计算机图形学第四章 图形处置根本算法浙江大学工程及计算机图学所浙江大学工程及计算机图学所 1SHU Graphics & Image Group工程及计算机图形学工程及计算机图形学浙江大学工程及计算机图学所浙江大学工程及计算机图学所主要内容n多边形的方向及顶点的凸凹性判别多边形的方向及顶点的凸凹性判别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方向性判别经典算法方向性判别经典算法-有向面积法有向面积法假设sp0，那么多边形顶点以逆时针方向衔接；假设sp0，那么多边形顶点以顺时针方向衔接；假设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.叉叉积积判判别别法法n点在凸多点在凸多边边形内的充要条件是形内的充要条件是叉叉积积Vi Vi+1 i=1,2, n 的符的符号一号一样样。叉。叉积积判判别别法法仅仅适用于适用于凸多凸多边边形形 n2.夹夹角之和角之和检验检验法法n假假设设 那么点在多那么点在多边边形形内；内；n假假设设 那么点在多那么点在多边边形形外外 12图4-1-13工程及计算机图形学工程及计算机图形学浙江大学工程及计算机图学所浙江大学工程及计算机图学所4.2点在多边形内外判别n3.交点计数检验法交点计数检验法n 当多边形是凹多边形，甚至还带当多边形是凹多边形，甚至还带孔时，可采用交点计数检验法判孔时，可采用交点计数检验法判别点能否在多边形内。详细做法别点能否在多边形内。详细做法是从判别点是从判别点P0作一射线至无穷远，作一射线至无穷远，然后求射线与多边形的交点，假然后求射线与多边形的交点，假设交点个数为奇数，那么点在多设交点个数为奇数，那么点在多边形内，否那么点在多边形外边形内，否那么点在多边形外 n特殊情况：假设共享顶点的两边特殊情况：假设共享顶点的两边在射线的同一侧，那么交点计数在射线的同一侧，那么交点计数加加2，否那么加，否那么加1。详细计数时，。详细计数时，当一条边的两端点当一条边的两端点y值都大于值都大于y0，即边处于射线上方时，计数加，即边处于射线上方时，计数加1，否那么不加，否那么不加13图4-1-14图4-1-15工程及计算机图形学工程及计算机图形学浙江大学工程及计算机图学所浙江大学工程及计算机图学所4.3曲线数据紧缩算法n命题：n 点数多、局部分布密集、整体分布情况复杂等特征的曲线紧缩、简化；要求尽能够坚持特征14图4-1-16工程及计算机图形学工程及计算机图形学浙江大学工程及计算机图学所浙江大学工程及计算机图学所n顶点减少法n步骤一：确定阀值。当前点与前一个点的间隔小于阀值时，舍弃当前点；当前点大于等于阀值时，记录当前点，并将当前点设为新的起始点。n步骤二：选取作为起始点，并记录。计算与的间隔，假设间隔大于，记录，并将作为新的起始点；假设间隔小于，舍弃，并继续判别与的间隔，直到找到一个与的间隔大于的点，记录新的点，并将新的点作为新的起始点。n步骤三：反复进展步骤二，直到最后一个点。154.3曲线数据紧缩算法图4-1-17工程及计算机图形学工程及计算机图形学浙江大学工程及计算机图学所浙江大学工程及计算机图学所nDouglas-Peucker算法n步骤一：确定阀值。n步骤二：先衔接第一个和最后一个边境网格顶点，计算这对基准顶点对之间的点到基准线的间隔。假设有一个及一个以上的点到基准线的间隔大于，将间隔基准线最远的点记为第n个点，删除基准线，并将第一个点和第n个点记为基准顶点对，将第n个点和最后一个点记为基准顶点对；假设一切点到基准线的间隔都小于等于，删除基准顶点之间的一切点，只保管基准顶点对作为基准顶点对之间曲线的控制顶点。n步骤三：反复将步骤二中得到的基准顶点对进展步骤二的计算，直到一切点到他们的基准线的间隔都小于等于。 164.3曲线数据紧缩算法图4-1-18工程及计算机图形学工程及计算机图形学浙江大学工程及计算机图学所浙江大学工程及计算机图学所nDouglas-Peucker算法的问题公共边分裂自相交的出现174.3曲线数据紧缩算法图4-1-19