凸多边形最优三角剖分C语言编写 算法

凸多边形最优三角剖分（C语言编写） 算法

#include 
#include 
int graph[8][8]=
{
0 14 25 27 10 11 24 16
14 0 18 15 27 28 16 14
25 18 0 19 14 19 16 10
27 15 19 0 22 23 15 14
10 27 14 22 0 14 13 20
11 28 19 23 14 0 15 18
24 16 16 15 13 15 0 27
16 14 10 14 20 18 27 0
};

int t[8][8];
int s[8][8];
int w（int m int n int p）
{
return graph[m][n] + graph[m][p] + graph[n][p];
}
void sp（int m int n）//输出最优剖分需要添加的线段
{
if （n-m<=2）
   return;
if（s[m][n]-m>=2）
{
   printf（“V%d-V%d\n“ m s[m][n]）;
   sp（m s[m][n]）;
}
if （n-s[m][n]>=2）
{
   printf（“V%d-V%d\n“ s[m][n] n）;
   sp（s[m][n] n）;
}
}
int main（）
{
int i j k r u;
memset（t 0 sizeof（t））;
memset（s 0 sizeof（s））;
for （r=2; r<=7; r++）
   for （i=0; i<7-r+1; i++）
   {
    j = i + r;
    t[i][j] =t[i][i+1] + t[i+1][j] +w（i i+1 j）;
    s[i][j] = i+1;
    for （k=i+2; k    {
     u = t[i][k] + t[k][j] + w（i k j）;
     if （u     {
      t[i][j] = u;
      s[i][j] = k;
     }
    }
   }
   printf（“输出最优剖分总权值为\n“）;
   printf（“%d\n“ t[0][7]）;
   printf（“输出最优剖分需要添加的线段为\n“）;
   sp（07）;
return 0;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件     172144  2011-10-16 22:20  凸多边形最优三角剖分\Debug\tuduojiaoxing.exe

     文件     185240  2011-10-16 22:20  凸多边形最优三角剖分\Debug\tuduojiaoxing.ilk

     文件       5634  2011-10-16 22:20  凸多边形最优三角剖分\Debug\tuduojiaoxing.obj

     文件     157244  2011-10-15 23:01  凸多边形最优三角剖分\Debug\tuduojiaoxing.pch

     文件     476160  2011-10-16 22:20  凸多边形最优三角剖分\Debug\tuduojiaoxing.pdb

     文件      33792  2011-10-16 22:28  凸多边形最优三角剖分\Debug\vc60.idb

     文件      45056  2011-10-16 22:20  凸多边形最优三角剖分\Debug\vc60.pdb

     文件       1219  2011-10-16 22:20  凸多边形最优三角剖分\tuduojiaoxing.c

     文件       3483  2011-10-16 22:05  凸多边形最优三角剖分\tuduojiaoxing.dsp

     文件        551  2011-10-16 22:36  凸多边形最优三角剖分\tuduojiaoxing.dsw

     文件      41984  2011-10-16 22:36  凸多边形最优三角剖分\tuduojiaoxing.ncb

     文件      48640  2011-10-16 22:36  凸多边形最优三角剖分\tuduojiaoxing.opt

     文件        789  2011-10-16 22:20  凸多边形最优三角剖分\tuduojiaoxing.plg

     目录          0  2011-10-16 17:35  凸多边形最优三角剖分\Debug

     目录          0  2011-10-16 22:36  凸多边形最优三角剖分

----------- ---------  ---------- -----  ----

              1171936                    15