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

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

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

<*) (b)图2表达式语法树与三角剖分的对应语法树中每一个叶子表示表达式中一个原子在语法树中，若一结点有一个表示表达式左子树，以及 一个表示表达式Er的右子树，则以该结点为根的子树表示表达式仁店』因此，有n个原子的完全加括号 表达式对应于惟一的一棵有n个叶结点的语法树，反之亦然凸多边形｛v0 ,v1，…，vn-1｝的三角剖分也可以用语法树来表示例如，图1(a)中凸多边形的三角剖分可用图 2(b)所示的语法树来表示该语法树的根结点为边v0v6，三角剖分中的弦组成其余的内部结点多边形中 除v0v6边外的每一条边是语法树的一个叶结点树根v0v6是三角形v0v3v6的一条边，该三角形将原多边形 分为3个部分：三角形v0v3v6，凸多边形｛v0,v1，…，V3｝和凸多边形｛v3,v4，…，v6｝三角形v0v3v6的另外两条 边，即弦v3v6和v0v3为根的两个儿子以它们为根的子树分别表示凸多边形｛v0 ,v1，…，V3｝和凸多边形 ｛v3,v4，…，V6｝的三角剖分在一般情况下，一个凸n边形的三角剖分对应于一棵有n-1个叶子的语法树反之，也可根据一棵有n-1 个叶子的语法树产生相应的一个凸n边形的三角剖分。

也就是说，凸n边形的三角剖分与n-1个叶子的语 法树之间存在一一对应关系由于n个矩阵的完全加括号乘积与n个叶子的语法树之间存在一一对应关系， 因此n个矩阵的完全加括号乘积也与凸(n+1)边形的三角剖分之间存在一一对应关系图2的(a)和(b)表示 出了这种对应关系，这时n=6矩阵连乘积A1A2..A6中的每个矩阵入对应于凸(n+1)边形中的一条边％‘ 三角剖分中的一条弦《马，i#include #include #include "Triangle.h"CTriangle::CTriangle(){M = 0;t = new int *[N];s = new int *[N];for(int i=0 ; i 0){P = P+1；}else if(total[k] < 0){q = q+1;}}if((p>0 && q>0) || (p==0 && q==0)){cout<<"无法构成凸多边形！ "<