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

算法分析部分

#include<iostream>
using namespace std;

/*
多边形是平面上一条分段线性闭曲线。也就是说多边形是由一系列首尾相连的
直线段所组成的。组成多边形的各直线段称为多边形的边。连接多边形相继两
条边的点称为多边形的顶点。若多边形的边除了连接顶点外没有别的交点，则
称多边形为简单多边形。一个简单多边形将平面分为三个部分：被包围在多边
形内的所有点构成了多边形的内部，多边形本身构成了多边形的边界；而平面上
其余包围着多边形的点构成了多边形的外部。当一个简单多边形及其内部构成一
个闭凸集时，称简单多边形为一个凸多边形。即凸多边形边界上或内部的任意两
点所连成的直线段上所有点均在凸多边形的内部或边界上。

通常，用多边形顶点的逆时针序列来表示一个凸多边形，即P={v0,v1,...,vn}表示
有n条边vov1,v1v2,..,vn-1vn的一个凸多边形。其中，约定v0 = vn.
若vi与vj是多边形上不相邻的两个顶点，则线段vivj称为多边形的一条弦。弦vivj
将多边形分割成两个多边形{vi,vi+1,...,vj}和{vj,vj+1,...,vi}。

多边形的三角剖分是一个将多边形分割成互不相交的三角形的弦的结合T。

在凸多边形P的一个三角剖分T中，各弦互不相交，且集合T已达到最大，即P的任一不
在T中的弦必与T中某一弦相交。在一个有n个顶点的凸多边形的三角剖分中，恰有
n-3条弦和n-2个三角形。
凸多边形最优三角剖分问题：给定一个凸多边形P={v0,v1,...,vn-1}，以及定义在由
凸多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的一个三角剖分，
使得该三角剖分中诸三角形上权之和为最小。
*/

/*
三角剖分的结构及相关问题：
凸多边形的三角剖分与表达式的完全加括号之间具有十分紧密的联系。正如所看到的
，矩阵连乘积的最优计算次序问题等价于矩阵链的最优完全加括号方式。这些问题之间的
相关性，可从它们所对应的完全二叉树的同构性看出。
一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全
加括号的矩阵连乘积((A1(A2A3))(A4(A5A6)))所相应的语法树如图所示：

一般情况下，一个凸n边形的三角剖分对应于一棵有n-1个叶结点的语法树。反之，也可根据
一棵有n-1个叶结点的语法树产生一个相应的凸n边形的三角剖分。也就是说，凸n边形的三角
剖分与有n-1个叶结点的语法树之间存在一一对应关系。由于n个矩阵的完全加括号乘积与n个
叶结点的语法树之间存在一一对应关系。因此，n个矩阵的完全加括号乘积也与凸(n+1)边形中
的三角剖分之间存在一一对应关系。矩阵连乘积A1A2...An中的每个矩阵Ai对应于凸(n+1)边形
中的一条边vi-1vi三角剖分中的一条弦vivj,i>j,对应于矩阵连乘积A[i+1:j]。

  事实上，矩阵连乘积的最优计算次序问题是凸多边形最优三角剖分问题的一个特殊情形，
对于给定的矩阵链A1A2...An，定义一个与之相应的凸(n+1)边形P={vo,v1,...,vn},使得
矩阵Ai与凸多边形的边vi-1vi一一对应。若矩阵Ai的维数为pi-1*pi,i=1,2,..n，则定义三角形
vivjvk上的权函数值为：w(vivjvk) = pipjpk。依此权函数的定义，凸多边形P的最优
三剖分所对应的语法树给出矩阵链A1A2。。。AN的最优完全加括号方式。
*/

/*
最优子结构性质：
事实上，若凸(n+1)边形P={vo,v1,...,vn}的一个最优三角剖分T包含三角形vovkvn
,1<=k<=n-1，则T的权为三个部分权之和：三角形vovkvn的权，子多边形{vo,v1,...,vk}
和{vk,vk+1,...,vn}的权之和。可以断言，由T所确定的这两个子多边形的三角剖分也是
最优的。因为若有{v0,v1,..,vk}或{vk,vk+1,...,vn}的更小权的三角剖分将导致T
不是最优三角剖分的矛盾。
*/

/*
最优三角剖分的递归结构
首先定义t[i][j],1<=i<j<=n为凸子多边形{vi-1,vi,...,vj}的最优三角剖分所
对应的权函数值，即最优值。为方便起见，设退化的多边形{vi-1vi}具有权值0。
因此，要计算的凸（N+1）边形P的最优权值为t[1][n].

t[i][j]   =  0 i == j
          =  min{i <= k < j}{t[i][k] + t[k+1][j] + w(vi-1vkvj)} i < j
*/

/*
计算最优值
与矩阵连乘积问题中计算m[i][j]的递归式进行比较容易看出
除了权函数的定义外，t[i][j]与m[i][j]的递归式是完全一样的。
因此只要对计算m[i][j]的算法MatrixChain作很小的修改就完全使用于计算t[i][j]

下面描述计算凸(n+1)边形P={v0,v1,...,vn}的最优三角剖分的动态规划算法
该算法以凸多边形P={vo,v1,...,vn}和定义在三角形上的权函数w作为输入。
*/

template< class Type >
void MinWeightTriangulation( int n, Type **t, int **s )
{
	for( int i = 1; i <= n; ++i )
	{
		t[i][i] = 0;
	}
	for( int r = 2; r <= n; ++r )
	{
		for( int i = 1; i <= n - r + 1; ++i )
		{
			int j = i + r -1;
			t[i][j] = t[i+1][j] + w(i-1,i,j);
			s[i][j] = i;
			for( int k = i + 1; k < i + r - 1; ++k )
			{
				int u = t[i][k] + t[k+1][j] + w(i-1,k,j);
			}
			if ( u < t[i][j] )
			{
				t[i][j] = u;
				s[i][j] = k;
			}
		}
	}
}
//算法占用O(n^2)空间，耗时间O(n^3)

/*
构造最优三角剖分
算法在计算每一个凸子多边形{vi-1,vi,...,vj}的最优值时，用数组s记录了最优三角剖分
中所有三角形信息。s[i][j]记录了与vi-1,vj一起构成三角形的第三个顶点的位置
。裾此，用O(n)时间就可构造出最优三角剖分中的所有三角形
*/
int main()
{
	return 0;
}