在图形学中，经常用到多边形三角剖分。

最优三角剖分

      最优三角剖分，就是把一个多边形分割成若干个三角形，求三角形某种最优解。一般都用动态规划来实现。这里我们以最小权重三角剖分（weight-minimizing triangulations）为例，根据参考资料1整理得来。

问题描述

      已知凸多边形任意两点形成边的权重Wij，将凸多边形分割成若干个互不相交的三角形，使得该三角剖分中的所有三角形边的权重之和最小。 凸多边形三角剖分如下图所示：

问题解决

       若凸边形P={V0,V1……Vn-1}的最优三角剖分T包含三角形V0VkVn,0<k<n，则T的权为三个部分权之和：三角形V0VkVn的权，多边形{V0,V1……Vk}的权和多边形{Vk,Vk+1……Vn}的权之和。如下图所示：

      可以断言，由T确定的这两个子多边形的三角剖分也是最优的。因为若有{V0,V1……Vk}和{V0,V1……Vk}更小权的三角剖分，将导致T不是最优三角剖分的矛盾。因此，凸多边形的三角剖分问题具有最优子结构性质。
      现在我们找状态转移公式。 设t[i][j],0<=i<j<n为凸多边形{Vi,Vi+1……Vj}的最优三角剖分所对应的权值函数值，即其最优值。最优剖分包含三角形ViVkVj的权，子多边形{Vi,Vi+1……Vk}的权，子多边形{Vk，Vk+1……Vj}的权之和。

      因此，可得状态转移公式：

最终凸边形P的最优权值为t[0][n-1]。

示例演示

//凸多边形最优三角剖分
#include <iostream> 
using namespace std;

//我们假设的凸多边形顶点的个数
const int kPointsNum = 6;
//凸多边形每两个顶点形成边的权重，Wii = 0
int weight[][kPointsNum] = { { 0,2,2,3,1,4 },
    			{ 2,0,1,5,2,3 },
    			{ 2,1,0,2,1,4 },
    			{ 3,5,2,0,6,2 },
    			{ 1,2,1,6,0,1 },
    			{ 4,3,4,2,1,0 } }; 

int MinWeightTriangulation(int n, int **t, int **s);
void Traceback(int i, int j, int **s);//构造最优解
int Weight(int a, int b, int c); ////权重函数 

int main()
{
	int **s = new int *[kPointsNum]; //s[i][j]记录Vi到Vj最优三角剖分的中间点K   
	int **t = new int *[kPointsNum];//t[i][j]表示多边形{ViVkVj}的最优权值
	for (int i = 0; i < kPointsNum; i++){
		s[i] = new int[kPointsNum];
		t[i] = new int[kPointsNum];
	}
	cout << "此多边形的最优三角剖分值为：" << MinWeightTriangulation(kPointsNum, t, s) << endl;
	cout << "最优三角剖分结构为：" << endl;
	Traceback(0, kPointsNum - 1, s); //s[i][j]记录了Vi和Vj构成三角形的第3个顶点的位置

	//release resource
	for (int i = 0; i < kPointsNum; i++) {
		delete []s[i];
		delete []t[i];
	}
	system("pause");
	return 0;
}

int MinWeightTriangulation(int n, int **t, int **s)
{
	for(int i = 0; i < n; i++) {
		t[i][i] = 0;
		t[i][(i + 1) % n] = 0;  //t[i][i+1] =0
	}	
	for(int j = 2; j < n; j++) {
		for(int i = 0; i < n - j; i++){
			int k = i + j;
			int m = i + 1;
			t[i][k] = t[i][m] + t[m][k] + Weight(i, m, k);
			s[i][k] = m;
			for(m = m + 1; m < k; m++){
				int u = t[i][m] + t[m][k] + Weight(i, m, j);
				if (u < t[i][k]) {
					t[i][k] = u;
					s[i][k] = m;
				}
			}
		}
	}
	return t[0][kPointsNum - 1];
}

void Traceback(int i, int j, int **s)
{
	cout << i << "  " << j << endl;
	if(i == j){
		cout << "i == j" << endl;
		return;
	} 
	if(i + 1 == j) {
		cout << "i + 1 == j" << endl;
		return;
	}	
	Traceback(i, s[i][j], s);
	Traceback(s[i][j], j, s);
	cout << "三角剖分顶点：V" << i << ",V" << j << ",V" << s[i][j] << endl;
}

int Weight(int a, int b, int c)
{
	return weight[a][b] + weight[b][c] + weight[a][c];
}

运行结果

参考资料

1. 0014算法笔记——【动态规划】凸多边形最优三角剖分（https://blog.csdn.net/liufeng_king/article/details/8639376）