triangulation.cpp

用C++实现最优三角剖分

#include<iostream.h>
//using namespace std;
#include<math.h>
#include<fstream.h>
#include"make2db.h"
double **v,**cc;
int **kay;
double dist(int i,int j)
{
	double dx=v[j][0]-v[i][0];
	double dy=v[j][1]-v[i][1];
	return sqrt(dx*dx+dy*dy);
}
double w(int i,int j,int k)
{
	return(dist(i,j)+dist(j,k)+dist(i,k));
}
double triangulation(int i,int j)
{
	if(cc[i][j]>0) return cc[i][j];
	if(i==j) return 0;
	cc[i][j]=triangulation(i+1,j)+w(i-1,i,j);
	kay[i][j]=i;
	for(int l=i+1;l<j;l++)
	{
		double u=triangulation(i,l)+triangulation(l+1,j)+w(i-1,l,j);
		if(u<cc[i][j])
		{
			cc[i][j]=u;
			kay[i][j]=l;
		}
	}
	return cc[i][j];
}
void Traceback(int i,int j)
{
	if(i==j) return;
	if(kay[i][j]==i) Traceback(i+1,j);
	else
	{
		Traceback(i,kay[i][j]);
		Traceback(kay[i][j]+1,j);
	}
	cout<<"v"<<i-1<<"v"<<kay[i][j]<<"v"<<j<<ends<<","<<ends;
}

void main(void)
{
	int i,j;
	int n;
	ifstream fin("data.txt");
	fin>>n;
	Make2DArray(cc,n,n);
	Make2DArray(kay,n,n);
	Make2DArray(v,n,2);
	for(i=0;i<n;i++)
		fin>>v[i][0]>>v[i][1];
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			cc[i][j]=0;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			kay[i][j]=0;
		triangulation(1,n-1);
		cout<<"最优划分的费用是："<<cc[1][n-1]<<endl;
		Traceback(1,n-1);
		cout<<endl;
		remove2DArray(cc,n);
		remove2DArray(kay,n);
		remove2DArray(v,n);
}