duobianxingdesanjiaoxingpoufendejiefa.txt

用VC++编写的凸多边形最优三角剖分的解法

#include    "windows.h"
#include    <iostream>
using    namespace    std;

/*
  问题描述:
        把多边形0,...,n-1剖分成n-2个三角形,求给定的权值最小
        本程序定义权为:剖分弦的长度和
  程序功能:
        用两种方法求解上述问题(针对任意权的和针对本问题的)
        解法本质都是动态规划
     PS   :    
        动态规划很难,本程序难免会有错误,但是基本思路是正确的
        注释得很详细了
*/

const    V    =    5;//5个顶点

void    LoadData(float dist[][V]);
/*
  解法1:
        重新定义权为:剖分弦的长度和加上多边形的周长(显然等价),重新求解
        本函数还适用于任何定义在剖分后的三角形上的权的情况(修改一下)
        例如权为三角形的面积的面积平方和
*/
void    minWeightTriangulation1(int n, float dist[][V], float t[][V], int s[][V]);
void    ShowSolution1(int s[][V], int i, int j);

/*
  解法2:
        针对此问题的求解方法,不具有普遍适用性
*/
void    minWeightTriangulation2(int n, float dist[][V], float t[][V+1], int s[][V+1]);
void    ShowSolution2(int s[][V+1], int i, int j);

void    end();

int    main()
{
    float    dist[V][V];

    float    t1[V][V];
    int    s1[V][V];

    float    t2[V+1][V+1];
    int    s2[V+1][V+1];

    LoadData(dist);
    
    minWeightTriangulation1(V, dist, t1, s1);
    cout<<"最优剖分权:"<<t1[1][4] - 2 - 1.414 * 3<<"\t剖分弦:\t";//要减去周长
    ShowSolution1(s1, 1, 4);
    cout<<endl;

    minWeightTriangulation2(V, dist, t2, s2);
    cout<<"最优剖分权:"<<t2[0][5]<<"\t剖分弦:\t";
    ShowSolution2(s2, 0, 5);
    cout<<endl;

    
    return    0;
}

void    LoadData(float    dist[][V])
{
    dist[0][1] = dist[1][0] = 1;
    dist[1][2] = dist[2][1] = 1;
    dist[2][3] = dist[3][2] = 1.414;
    dist[3][4] = dist[4][3] = 1.414;
    dist[4][0] = dist[0][4] = 1.414;
    dist[0][2] = dist[2][0] = 1.414;
    dist[0][3] = dist[3][0] = 2;
    dist[1][3] = dist[3][1] = 2.236;
    dist[1][4] = dist[4][1] = 2.828;
    dist[2][4] = dist[4][2] = 2;
}

float    Weight(float dist[][V], int i, int j, int k)
{
    return dist[i][j] + dist[j][k] + dist [k][i];
}

void    minWeightTriangulation1(int n, float dist[][V], float t[][V], int s[][V])
{
/*
    t[i][j]表示顶点为i-1,i,...,j的多边形的最优三角剖分值
    s[i][j]表示顶点为i-1,i,...,j的多边形的最优三角剖分方法,剖分点为s[i][j]
    退化情况1:s[i][j]==i   剖分成 三角形i-1,i,j    和 多边形i,...,j
    退化情况2:s[i][j]==j-1 剖分成 多边形i-1,...,j-1和 三角形i-1,j-1,j
    一般情况:k = s[i][j]   剖分成 多边形i-1,...,k  和 多边形 k,...,j
    权的定义:多边形的周长+剖分的弦长,所以对两种特殊情况进行了处理
*/
    for (int i = 1; i < n; i++)
        t[i][i] = 0;//只有两个顶点认为权是0
    for (int r = 2; r < n; r++)//r+1边形
    {
        for (i = 1; i <= n - r; i++)
        {
            int j = i + r -1;
            /*当i-1,i,j是相邻三个顶点时(r==2),权为
              t[i+1][j] + Weight(dist, i-1, i, j)
              否则,权为
              t[i+1][j] + Weight(dist, i-1, i, j) - dist[i][j]
              因为t[i+1][j]和eight(dist, i-1, i, j)分别计算了
              一次dist[i][j]
            */
            t[i][j] = t[i+1][j] + Weight(dist, i-1, i, j) -
                (r==2?0:dist[i][j]);
            s[i][j] = i;

            for (int k = i + 1; k < j; k++)
            {/*
               当取剖分i-1,j-1时权为
               t[i][k] + t[k+1][j] + dist[i-1][j] + dist[k][j]
               因为t[k+1][j]退化,权为0,故把边dist[k][j]补上
               否则权为t[i][k] + t[k+1][j] + dist[i-1][j]
             */
                float u = t[i][k] + t[k+1][j] + dist[i-1][j] +
                    (k+1==j?dist[k][j]:0);
                if (u<t[i][j])
                {
                    t[i][j] = u;
                    s[i][j] = k;
                }
            }
        }
    }
}

void    ShowSolution1(int s[][V], int i, int j)
{
    if (i + 1 >= j)    return;
    int k = s[i][j];

    if (k == i)
    {//退化情况1:s[i][j]==i   剖分成 三角形i-1,i,j    和 多边形i,...,j
        cout<<'('<<i<<','<<j<<") ";
        ShowSolution1(s, i+1, j);
    }
    else
        if (k==j-1)
        {//退化情况2:s[i][j]==j-1 剖分成 多边形i-1,...,j-1和 三角形i-1,j-1,j
            ShowSolution1(s, i, j-1);
            cout<<'('<<i-1<<','<<j-1<<") ";
        }
        else
        {//一般情况:k = s[i][j]   剖分成 多边形i-1,...,k  和 多边形 k,...,j
            ShowSolution1(s, i, k);
            cout<<'('<<i-1<<','<<k<<") ";
            cout<<'('<<k<<','<<j<<") ";
            ShowSolution1(s, k+1, j);
        }
}

float    Distance(float dist[][V], int i, int j)
{
    if (i == (j + 1)%V || j == (i +1)%V)
        return 0;
    return dist[i][j];
}

void    minWeightTriangulation2(int n, float dist[][V], float t[][V+1], int s[][V+1])
{
/*
   t[i][j]表示从顶点i开始的j个顶点围成的多边形(j边形)的最优剖分的权
   s[i][j]表示从顶点i开始的j个顶点围成的多边形(j边形)的最优剖分的方法,
   剖分点为 i + s[i][j]
   退化情况1:s[i][j]==1  剖分成 三角形i,i+1,i+j-1 和 多边形 i+1,...,i+j-1
   退化情况2:s[i][j]==j-2剖分成 多边形i,...,i+j-2 和 三角形 i,i+j-2,i+j-1
   一般情况 :k = s[i][j] 剖分成 多边形i,...,i+k   和 多边形 i+k,...,i+j-1
 */
    const    MAX    =    10000;
    float    temp, q;
    int    kk;
    
    for (int k = 0; k < n; k++)
    {
        t[k][2] = 0;
        t[k][3] = 0;
    }

    for (int r = 4; r <= n; r++)
        for (int i = 0; i < n; i++)
        {
            for (q = MAX, kk = 1; kk <= r - 2; kk++)
            {/*
               划分成子问题 
               多边形i,...,i+kk 和 多边形 i+kk,...,i+r-1
               划分弦为 (i, ((i+kk)%n) 和 ((i+kk)%n, (i+r-1)%n)
               由于Distance函数中相邻弦长度为0,故退化情况自动包含
                 */
                temp = t[i][(kk+1)%n] + t[(i+kk)%n][(n+r-kk)%n] + 
                    Distance(dist, i, ((i+kk)%n) ) +  
                    Distance(dist, (i+kk)%n, (i+r-1)%n);
                if (temp < q)
                {
                    k = kk;
                    q = temp;
                }
            }
            t[i][r] = q;
            s[i][r] = k;
            if (r==n) break;//一旦r==n可以马上跳出本层循环
        }
}

void    ShowSolution2(int s[][V+1], int i, int j)
{
    if (j<=3)    return;

    int k = s[i][j];
    if  (k==1)
    {//退化情况1:s[i][j]==1  剖分成 三角形i,i+1,i+j-1 和 多边形 i+1,...,i+j-1
        cout<<'('<<i+1<<','<<i+j-1<<") ";
        ShowSolution2(s, i+1, j-1);
    }
    else
        if (s[i][j]==j-1)
        {//退化情况2:s[i][j]==j-2剖分成 多边形i,...,i+j-2 和 三角形 i,i+j-2,i+j-1
            cout<<'('<<i<<','<<i+j-1<<") ";
            ShowSolution2(s, i, j-1);
        }
        else
        {//一般情况 :k = s[i][j] 剖分成 多边形i,...,i+k   和 多边形 i+k,...,i+j-1
            ShowSolution2(s, i, k+1);
            cout<<'('<<i<<','<<i+k<<") ";
            ShowSolution2(s, i+k, j-k);
            cout<<'('<<i+k<<','<<i+j-1<<") ";
        }
}