看来看去还是这个论文解释的非常清楚。
http://www.cnblogs.com/dogstar/archive/2011/04/07/2008726.html

本项目的部分代码参考自下面博客

https://www.cnblogs.com/lan-yt/p/9200621.html

 

最近项目中涉及到使用Unity3D来进行地图上国家的渲染，比如把中国圈起来染成红色的这样的需求。

Unity3D把区域渲染是用的MeshRender，关于MeshRender的用法我就不详细讲解了。

最终问题卡在一个点上，对于中国边界这样的凹多边形，如何将其剖分为一系列三角形。

本来以为这是个最常见的问题，应该会有很多求解方法的，结果我找了半天，就找到了上面给出网址的那个博客，而没找到成形的源码。

还好那个博客上有代码，就按照那个博客上的代码，运行了一下，反正在我电脑上有点小的BUG。

不过这个BUG很容易修改，虽然我忘记我是怎么修改的了，后来运行成功了。

于是，我就找到中国边界数据，把它读进去，然后运行。

等了一会儿，系统爆栈了，因为那个博客中算法用到了递归，而中国边界有八千多个点，一个点递归一次，需要递归八千次。

不得已，只好自己写代码了。

后来看到了一个翻译来自日本的凹多边形剖分算法，耳切法。

博客地址：

https://blog.csdn.net/u010019717/article/details/52753855

根据第二个博客中的思想，来设计如下算法：

步骤一：将多边形的所有点读入数组V中。

步骤二：判断该多边形是否为凸多边形，如果为凸多边形，按照凸多边形剖分算法进行处理，算法结束，否则转到步骤三。

步骤三：将所有顶点的序号读入一个数组A中保存起来，然后遍历多边形的顶点，判断每个顶点是否为“耳朵节点”，然后将所有“耳朵节点”保存到数组B。

步骤四：如果耳朵节点数组B为空或者顶点数组V的顶点数组小于三，则算法结束。否则，取出耳朵节点中的第一个顶点P来。

步骤五：找到该节点的前序节点M和后序节点N，这三个点MPN组成一个三角形，保存到结果数组R中，然后，把当前顶点P从耳朵节点中去掉，从数组V中去掉，从序号数组B中去掉。

步骤六：前序节点M和后序节点N，成为了“耳朵节点”的候选。则分别判断M与N是不是耳朵节点，如果是耳朵节点，且没有在当前的耳朵节点数组B中，则将判断为耳朵节点的点放入耳朵节点数组B中。

步骤七：跳转到步骤四。

 

然后通过以上算法，就得到了最终的结果，这个算法没有使用递归，算法的效率还行。

 



这个是我算法运行的结果。

算法源码：

https://download.csdn.net/download/kongxinyue/11230469

 

 

 

5047. 多边形三角剖分的最低得分
转载请注明出处

附上我的博客链接 四元君

题目难度 Medium
题目描述
给定 N，想象一个凸 N 边多边形，其顶点按顺时针顺序依次标记为 A[0], A[i], …, A[N-1]。
假设您将多边形剖分为 N-2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。
返回多边形进行三角剖分后可以得到的最低分。
示例 1：
输入：[1,2,3]
输出：6
解释：多边形已经三角化，唯一三角形的分数为 6。

示例 2：


输入：[3,7,4,5]
输出：144
解释：有两种三角剖分，可能得分分别为：3*7*5 + 4*5*7 = 245，或 3*4*5 + 3*4*7 = 144。最低分数为 144。

示例 3：
输入：[1,3,1,4,1,5]
输出：13
解释：最低分数三角剖分的得分情况为 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13。

提示：
3 <= A.length <= 50
1 <= A[i] <= 100

解法
基本的思路是动态规划。
假设我们现在有一个六边形，我们用cost[i][j]存储由第i号顶点到第j号顶点所划定的三角形的值之和。如下图：


比如说我们选定cost[0][3]，他表示从0号顶点到3号顶点的所有右侧的三角形值的和（右侧是我们的顺时针方向）。这个值的和可以有两种算法，一种是蓝色的S012+S023;一种是紫色的S013+S123。我们将所有的计算的值存储在一张表中，如下图：


将cost[i][i+1]的对角线初始化为0，意义为两个重合点无法构成三角形；cost[i][i+2]对角线初始化为由i，i+1，i+2三点构成的三角形的值。
此后更新步长step，美更新一次意味着划定的区域多加入一个三角形，新的值由新的三角形面积和老的三角形面积共同决定，核心公式为：
cost[当前目标] = min (cost[当前目标], cost[细分后三角形A] + cost[细分后三角形B]+ A[i] * A[j] * A[k]);

即
cost[i][j] = min (cost[i][j], cost[i][k] + cost[k][j]+ A[i] * A[j] * A[k]);

完整代码如下：
class Solution {
public:
    int cost[100][100];
    int minScoreTriangulation(vector<int>& A) {
        int n = A.size();
        for (int i = 0;i < n; ++ i) {
            for (int j = 0;j < n; ++ j) {
                cost[i][j] = INT_MAX;
            }
        }
        for (int i = 0;i < n - 1; ++ i) {
            cost[i][i + 1] = 0;
        }
        
        for (int step = 2; step < n; ++ step) {
            for (int i = 0;i + step < n; ++ i) {
                int j = i + step;
                for (int k = i + 1;k <= j - 1; ++ k) {
                    cost[i][j] = min (cost[i][j], cost[i][k] + cost[k][j]+ A[i] * A[j] * A[k]);
                }
            }
        }
        return cost[0][n-1];
    }
};

 　　 在三维图形学及其可视化应用中 ,三角形是

最简单、 最可靠的一种多边形 ,也即多边形的最小

单位。三维应用开发有 Open GL 及 Direct 3D 渲

染引擎两种常用开发工具 ,Open GL 有直接绘制

多边形的函数 ,但仅限于凸多边形;而在 Direc

3D中 ,只有直接绘制三角形(网)的函数。因此

多边形三角剖分是多边形绘制的基础。

Cheng Siuwing等[1 ,2 ,3 ]

从建立最优三角形条

件的角度提出了简单多边形三角剖分的算法;杨

杰等[4 ,5 ]

提出了根据顶点凹凸性进行简单多边形

三角剖分的算法。然而 ,这些算法并没有考虑存

在高程起伏特征或带岛屿的复杂多边形面状地物

(如道路、 河流)的三角剖分。　　 在三维图形学及其可视化应用中 ,三角形是

最简单、 最可靠的一种多边形 ,也即多边形的最小

单位。三维应用开发有 Open GL 及 Direct 3D 渲

染引擎两种常用开发工具 ,Open GL 有直接绘制

多边形的函数 ,但仅限于凸多边形;而在 Direc

3D中 ,只有直接绘制三角形(网)的函数。因此

多边形三角剖分是多边形绘制的基础。

Cheng Siuwing等[1 ,2 ,3 ]

从建立最优三角形条

件的角度提出了简单多边形三角剖分的算法;杨

杰等[4 ,5 ]

提出了根据顶点凹凸性进行简单多边形

三角剖分的算法。然而 ,这些算法并没有考虑存

在高程起伏特征或带岛屿的复杂多边形面状地物

(如道路、 河流)的三角剖分。距离河流流域三角剖分时 ,如加上高程信息这一

地形条件 ,可充分顾及地形特征 ,使剖分的长距离

河流流域在三维 GIS中表现更加自然、 真实。