凸多边形最优三角剖分.docx

凸多边形最优三角剖分2007-07-13 00:03一、 问题描述多边形是平面上一条分段线性的闭曲线也就是说，多边形是由一系列首尾相接的直线段组成的组成多边形的各直线段称为该多边形的边多边形相接两条边的连接点称为多边形的顶点若多边形的边之间除了连接顶点外没有别的公共点，则称该多边形为简单多边形一个简单多边形将平面分为 3 个部分：被包围在多边形内的所有点构成了多边形的内部；多边形本身构成多边形的边界；而平面上其余的点构成了多边形的外部当一个简单多边形及其内部构成一个闭凸集时，称该简单多边形为凸多边形也就是说凸多边形边界上或内部的任意两点所连成的直线段上所有的点均在该凸多边形的内部或边界上通常，用多边形顶点的逆时针序列来表示一个凸多边形，即 P={v0 ,v1 ,… ,vn-1}表示具有 n 条边 v0v1，v 1v2，… ,v n-1vn的一个凸多边形，其中，约定 v0=vn若 vi与 vj是多边形上不相邻的两个顶点，则线段 vivj称为多边形的一条弦弦将多边形分割成凸的两个子多边形{v i ,vi+1 ,… ,vj}和{v j ,vj+1 ,… ,vi}多边形的三角剖分是一个将多边形分割成互不相交的三角形的弦的集合 T。

图 1 是一个凸多边形的两个不同的三角剖分图 1 一个凸多边形的 2 个不同的三角剖分在凸多边形 P 的一个三角剖分 T 中，各弦互不相交，且弦数已达到最大，即 P的任一不在 T 中的弦必与 T 中某一弦相交在一个有 n 个顶点的凸多边形的三角剖分中，恰好有 n-3 条弦和 n-2 个三角形凸多边形最优三角剖分的问题是：给定一个凸多边形 P={v0 ,v1 ,… ,vn-1}以及定义在由多边形的边和弦组成的三角形上的权函数 ω要求确定该凸多边形的一个三角剖分，使得该三角剖分对应的权即剖分中诸三角形上的权之和为最小可以定义三角形上各种各样的权函数 ω 例如：定义 ω (vivjvk)=|vivj|+|vivk|+|vkvj|，其中，|v ivj|是点 vi到 vj的欧氏距离相应于此权函数的最优三角剖分即为最小弦长三角剖分二、 算法思路凸多边形的三角剖分与表达式的完全加括号方式之间具有十分紧密的联系正如所看到过的，矩阵连乘积的最优计算次序问题等价于矩阵链的完全加括号方式这些问题之间的相关性可从它们所对应的完全二叉树的同构性看出一个表达式的完全加括号方式对应于一棵完全二叉树，人们称这棵二叉树为表达式的语法树。

例如，与完全加括号的矩阵连乘积((A 1(A2A3))(A4(A5A6)))相对应的语法树如图 2(a)所示图 2 表达式语法树与三角剖分的对应语法树中每一个叶子表示表达式中一个原子在语法树中，若一结点有一个表示表达式 E1的左子树，以及一个表示表达式 Er的右子树，则以该结点为根的子树表示表达式(E 1Er)因此，有 n 个原子的完全加括号表达式对应于惟一的一棵有 n 个叶结点的语法树，反之亦然凸多边形{v 0 ,v1 ,… ,vn-1}的三角剖分也可以用语法树来表示例如，图 1(a)中凸多边形的三角剖分可用图 2(b)所示的语法树来表示该语法树的根结点为边 v0v6，三角剖分中的弦组成其余的内部结点多边形中除 v0v6边外的每一条边是语法树的一个叶结点树根 v0v6是三角形 v0v3v6的一条边，该三角形将原多边形分为 3 个部分：三角形 v0v3v6，凸多边形{v 0 ,v1 ,… ,v3}和凸多边形{v 3 ,v4 ,… ,v6}三角形 v0v3v6的另外两条边，即弦 v3v6和 v0v3为根的两个儿子以它们为根的子树分别表示凸多边形{v 0 ,v1 ,… ,v3}和凸多边形{v 3 ,v4 ,… ,v6}的三角剖分。

在一般情况下，一个凸 n 边形的三角剖分对应于一棵有 n-1 个叶子的语法树反之，也可根据一棵有 n-1 个叶子的语法树产生相应的一个凸 n 边形的三角剖分也就是说，凸 n 边形的三角剖分与 n-1 个叶子的语法树之间存在一一对应关系由于 n 个矩阵的完全加括号乘积与 n 个叶子的语法树之间存在一一对应关系，因此 n 个矩阵的完全加括号乘积也与凸(n+1)边形的三角剖分之间存在一一对应关系图 2 的(a)和(b)表示出了这种对应关系，这时 n=6矩阵连乘积A1A2..A6中的每个矩阵 Ai对应于凸(n+1)边形中的一条边 vi-1vi三角剖分中的一条弦 vivj，i0,则该点在直线右侧；若 ax+by+c0 所以点(5,0)在直线右侧程序中用指针 v 来记录各点坐标，按逆时针依次输入用*total 来记录坐标在直线方程中的值用 p 和 q 分别记录点代入方程所得值的正或负的点的个数若是凸多边形，则应全为正或全为负，即 p>0 和 q>0 不同时成立；若是凹多边形，则 p>0 和 q>0 同时成立而其中若 p=0 和 q=0 同时成立，则不能构成多边形 图形学:名词解释 （1）2007-07-13 00:103D三维（three dimension）。

客观世界中静止的物体都是三维的，在计算机图形学中常在一定的坐标系中用（x，y，z）坐标系列表示物体3D modeling3D 建模用三维坐标来描述物体的形状在各种计算机图形应用领域中有不同的三维建模方法，用不同的算法来描述这些领域中的物体和对象3D transformation3D 变换在三维空间中把物体的三维坐标从一个位置变换至另一位置，或者从一个坐标系变换至另一坐标系这是一种对物体的三维坐标（x，y，z）进行数据操作的一种形式3D transformation sequence3D 变换序列把客观世界中的物体在计算机屏幕上显示，通常需要进行一系列坐标变换，如从物体的相对坐标系变换至计算机屏幕需要经过平移、旋转、视点投影变换等一系列坐标变换4D四维（four dimension）在计算机图形学中描述客观世界除了用三维坐标来描述物体的形状外，还用时间 t 作为第四维来描述过程，通常用（x，y，z，t）表示6D六维（six dimension）在计算机图形学三维应用过程中（例如：模拟仿真、虚拟现实应用等）用六个自由度（x，y，z 坐标、偏角、倾角、仰角）来描述物体的运动a stream一段流AABB沿坐标轴的包围盒（axis-aligned bounding boxes）ABI二进制接口Absorption吸收Accumulation Buffer累积缓存。

累积缓存同颜色缓存一样也保存颜色数据，但它只保存 RGBA 颜色数据，而不能保存颜色索引数据（因为在颜色表方式下使用累积缓存其结果不确定）这个缓存一般用于累积一系列图像，从而形成最后的合成图像利用这种方法，可以进行场景反走样操作action mapping动作映射algorithm算法一般指在用电脑软件解决问题时所用的数学方法或程序实现过程通常用数学公式或程序框图来描述aliasing走样在进行渲染着色的时候，所绘制的图元直接按照所赋给的颜色绘制象素，就会产生锯齿状的边，这就是走样alpha blending阿尔法混合一种让图像产生透明感的技术alpha channelalpha 通道alpha color componentalpha 颜色组件alpha constantalpha 常量alpha value阿尔法值颜色成分中的第四个成分Alpha 值不用于直接显示，一般用于颜色的混合Ambient Light环境光analog模拟animated deformation动态自由变形AntiAliasing反走样（anti-aliasing）根据图形单元的象素覆盖区域来确定象素的颜色值，这种渲染绘制技术就是反走样。

APIs应用程序编程接口application specific clipping特定裁剪应用图形单元在视点坐标系的平面上进行ARB体系结构评审委员会（Architecture Review Board）Architecture Review Board体系结构评审委员会（ARB）area fill区域填充即用指定的颜色和模式填充多边形或三角形区域围绕区域的线条即为边界这在计算机图形学中是基本的绘图方式articulated motion关节运动一个与其它三维图形相连接的部件的运动这种运动在动画或模拟中经常用到AxDF轴变形（axial Deformation）axial Deformation轴变形（AxDF）axis aligned bounding boxes沿坐标轴的包围盒（AABB）B splineB-样条back face背面多边形的一侧多边形有正面和背面这二个面，在视窗中只有一个面是可见的，这个可见的面是正面还是背面在多边形投影到视窗后而定，若多边形的边为顺时针方向，其中的一个面可见，若多边形的边为逆时针方向，则另一个面可见，时针方向对应于正面还是反面由编程者而定background color背景颜色。

整个图形的底色behavior行为binary file二进制文件以二进制格式存储的文件，它的格式与 ASCII 格式（文本）相对立，其存储空间相对较小bit位二进制数，位作为状态变量只有 0 或 1 二个可能的值二进制数可由一个或多个二进制位组成bitmap位图一种在显示内存或常规内存中字节的矩阵存储方式OpenGL 中对位图的显示用 glBitmap()函数绘制bitplane位平面计算机屏幕上所有象素的字节的某一位组成的矩阵称为一个位平面位平面用于驱动视频输出，也称为颜色平面帧缓冲区就是由一组位平面组成的Blend过渡运算blending混合把二种颜色减少成为一种颜色，通常混合后的颜色由这二种颜色线性内插得到Body体它是面的并集Boundary Representation边界表示（BRep）它是几何造型中最成熟、无二义的表示法bounding box包围盒bounding volume包围盒bounding volume hierarchy包围盒层次BRDFbi-directional reflectance distribution function 的缩写它的概念是，不论你观看的角度如何，让物体表面显现的不同材质看起来真切。

BRep边界表示（Boundary Representation）它是几何造型中最成熟、无二义的表示法buffer缓冲区用于临时存储数据和图象的一块内存区域在计算机图形学中通常指存储色彩的单个成分（如红色、绿色)或单个索引（如颜色索引或模板索引）的一组位面存储 R、G、B、A 四个值的缓冲区称为颜色缓冲区bump mapping凹凸贴图BYPASSED旁路，忽略CAD计算机辅助设计用计算机软件命令代替绘图工具并用计算机屏幕代替绘图板，而且能够用计算机三维图形显示所设计的工程部件这种方式大大提高了工程设计者的效率CALLBACK回调callback function回调函数在应用程序中处理系统功能的函数通常在不同系统（如与外部设备交互）间交流时用到回调函数CAPP计算机辅助工艺过程设计change with time逐时变化client客户发出 OpenGL 命令的计算机这个计算机可以通过网络与其它执行这些命令的计算机相连，或者在同一个计算机上发布和执行命令clip coordinates裁剪坐标这是指在投影变换后在透视变换前的坐标系统视窗体的裁剪在裁剪坐标系下进行，但应用特定裁剪不是在此坐标系下进行。

clipping剪 裁将超出裁剪面所定义的视窗边界的图形部分删除如果点在外面，就简单地拒绝；如果线或多边形在外面，在外面的部分被删除，并且按照需要补充的新的顶。