凸多边形的最优三角剖分程序清单：
#include
#include
using namespace std;
void MinWeightTriangulation(int n,float t[][50],int s[][50],float v[][2]); float w(int i,int j,int k,float v[][2]);
void traceback(int i,int j,int s[][50]); //输出三角形的剖分结果
bool judge(int i,int j,int n,float v[][2]); //用于判断是否能构成凸多边形 void main()
{
}
void MinWeightTriangulation(int n,float t[][50],int s[][50],float v[][2]) {
for(int i=1;i
} } } float u=t[i][k]+t[k+1][j]+w(i-1,k,j,v); if(u
float w(int i,int j,int k,float v[][2])
{
{
}
bool judge(int a,int b,int n,float v[][2]) //返回1表示能构成凸多边形 {
边形
else { k=(v[a][1]-v[b][1])/(v[b][0]-v[a][0]); //直线的斜率 y=((v[a][1]-v[b][1])/(v[a][0]-v[b][0]))*v[a][0]-v[a][1]; for(int i=0;iv[a][0])boola=1; else if(v[i][1]
边形
}} if(i!=a&&i!=b) {if(v[i][1]+k*v[i][0]+y>0)boola=1; } if(boola==boolb)return 0; //boola和boolb的值相等，说明直线两侧都与点，不能构成凸多else return 1; else if(v[i][1]+k*v[i][0]+y