“凸”字形单调多边形三角剖分算法的研究

凸三角形剖分算法引言：凸三角形剖分算法是计算机图形学中的一个重要算法，用于将凸多边形分割成多个三角形。

凸三角形剖分算法在计算机图形学中有广泛的应用，如三维模型的渲染和物体表面的三角化等。

本文将介绍凸三角形剖分算法的原理、步骤以及应用。

一、凸三角形剖分算法的原理凸三角形剖分算法的原理是通过将凸多边形分割成多个三角形来表示其形状。

凸多边形是一个没有凹角的多边形，因此可以通过将顶点连接成三角形来表示其形状。

凸三角形剖分算法的目标是找到一种分割方式，使得分割后的三角形尽可能接近原来的凸多边形。

二、凸三角形剖分算法的步骤1. 找到凸多边形的一个顶点作为起始点。

2. 选择一个可见的相邻顶点，并将其与起始点连接成一条边。

3. 判断新连接的边是否与凸多边形的其他边相交，如果相交则进行下一步，否则转到步骤2。

4. 在相交的边上选择一个顶点作为新的起始点，并将其与之前的起始点连接成一条边。

5. 重复步骤3和步骤4，直到所有的边都被连接成三角形。

三、凸三角形剖分算法的应用1. 三维模型的渲染：凸三角形剖分算法可以将三维模型表面分割成多个三角形，从而方便进行渲染和光照计算。

通过将三维模型分割成三角形，可以更好地表示其形状和曲面细节。

2. 物体表面的三角化：在计算机图形学中，凸三角形剖分算法也常用于对物体表面进行三角化。

通过将物体表面分割成多个三角形，可以更好地描述物体的形状和曲面特征，方便进行后续的计算和分析。

3. 网格生成：凸三角形剖分算法可以用于生成网格，在计算机图形学中常用于网格建模和网格编辑等应用。

通过将凸多边形分割成多个三角形，可以更好地表示网格的形状和结构。

4. 地图生成：凸三角形剖分算法还可以应用于地图生成，特别是地形地图的生成。

通过将地形区域分割成多个三角形，可以方便地表示地形的高度和坡度等信息，为后续的地图渲染和分析提供基础数据。

结论：凸三角形剖分算法是计算机图形学中的一个重要算法，通过将凸多边形分割成多个三角形来表示其形状。

凸多边形的三角划分卡特林数凸多边形的三角划分问题是指如何将一个凸多边形划分成一些不重叠的三角形。

这个问题在计算几何中具有重要的应用，如有限元分析、多边形网格生成等。

卡特林数是解决凸多边形的三角划分问题的一种计数方法。

卡特林数是一个组合数列，其中第n个卡特林数表示将一个凸n+2边形划分成三角形的不同划分数目。

首先，我们来介绍一下卡特林数的递归关系。

设C(n)表示将一个凸n+2边形划分成三角形的不同划分数目。

我们可以考虑凸n+2边形的一个顶点，将其与其他n+1个顶点分别连接，得到n+1个划分情况。

如果选择的顶点与其他顶点构成一条对角线，那么我们将得到两个凸多边形，分别是一个边长为k+2的凸多边形和一个边长为n-k+1的凸多边形。

其中k的取值范围是0到n，表示选择的对角线一侧顶点的个数。

因此有递推关系式：C(n) = C(0) * C(n) + C(1) * C(n-1) + C(2) * C(n-2) + ...+ C(n) * C(0)其中，C(0) = C(1) = 1，表示一个凸2边形和一个凸3边形的划分数目均为1。

我们可以使用动态规划的方法求解卡特林数。

设一个数组C，其中C[i]表示C(i-2)。

我们从小到大计算C[i]，通过递推关系式可以得到C[n]的值。

最终，C[n]就表示了将一个凸n+2边形划分成三角形的不同划分数目。

利用卡特林数，我们可以解决一些与凸多边形的三角划分相关的问题。

例如，我们可以计算一个凸n+2边形的所有不同划分数目。

对于划分数目较大的情况，我们可以使用大数计算来解决。

另外，卡特林数也可以求解一些特定的凸多边形划分问题。

例如，给定一个凸n+2边形，我们希望找到一条对角线，使得将凸多边形划分成的两个子多边形中，其中一个子多边形有恰好k条边。

我们可以利用卡特林数的递归关系式，在计算中判断划分的结果是否满足要求。

在实际应用中，我们可以将凸多边形的三角划分问题转化为求解卡特林数的问题，并通过动态规划的方法来求解。

凸多边形最优三⾓剖析_动态规划⼀、问题描述多边形的三⾓剖分：将多边形分割成互不相交的三⾓形的弦的集合T。

最优剖析：给定凸多边形的三⾓剖分，使得该三⾓剖分中诸三⾓形上权之和最⼩(是所有的三⾓形的权值之和，不是只计算边和弦的权值之和)。

⼆、解题思路及所选算法策略的可⾏性分析基本思路：动态规划。

最优⼦结构：若凸(n+1)边形p={V0,V1,…,VN}的最优三⾓剖分T包含三⾓形V0VkVn, 1<=k<n。

则T的权为3个部分权的和：三⾓形V0VkVn的权，⼦多边形{V0,V1,…,Vk}和{Vk,Vk+1,…,Vn}的权之和。

可断⾔，有T确定的这2个⼦多⼥性的三⾓剖析也是最优。

因为若有更⼩的三⾓剖析将导致T不是最优的三⾓剖析的⽭盾递归结构：定义t[i][j],1<=i<j<=n为凸⼦多边形{Vi-1，Vi,…,Vj}的最优三⾓剖分所对应的权函数值，即其最优值。

最优剖分包含三⾓形Vi-1VkVj的权，⼦多⼥性{Vi-1,Vi,…,Vk}和{Vk,Vk+1,…,Vj}的权之和。

凸(n+1)边形P的最优权值为t[1][n]。

T[1][n]=min{t[1][k]+t[k+1][n]+w(V0VkVn)|1<=k<n}设退化的多边形{Vi-1,Vi}具有的权值为0，因为此刻够不成多边形。

三、伪代码描述及复杂度分析伪代码：Public class triangle{初始化各点两两相连权重；初始化所有⼆顶点多边形权值为0；//循环求解t[i][j]For(⼦多边形的始末顶点间隔步长){For(起始点位置){该层循环起始点对应末点的位置；求解t[i][j];记录第三点位置；找到最⼩权值位置；}}}复杂度分析：对于n规模的问题，算法需要申请n*n空间的⼆位数组，所以空间复杂度为O(n^2)。

求解问题⽤到三层for循环，所以时间复杂度为O(n^3)。

四、代码实现package 动态规划;public class triangle {private int n;// n多边形private int[][] weight;// 边的权值数组public triangle(int n) {this.n = n;this.weight = new int[n][n];}public static void main(String[] args) {triangle triangulation = new triangle(6);initTriangulation(triangulation);int n = triangulation.getN();// 凸多边形的边数int[][] t = new int[n][n];// t[i][j]表⽰顶点{Vi-1,Vi...Vj}组成的多边形的最优三⾓形剖分的权值 int[][] s = new int[n][n];// s[i][j]表⽰与Vi-1和Vj⼀起构成三⾓形的第三个顶点的位置triangulation.minWeightTriangulation2(triangulation.getN() - 1, t, s);System.out.println(t[1][5]);}// 初始化weight数组的信息public static void initTriangulation(triangle triangulation) {int[][] weight = { { 0, 2, 2, 3, 1, 4 }, { 2, 0, 1, 5, 2, 3 }, { 2, 1, 0, 2, 1, 4 },{ 3, 5, 2, 0, 6, 2 }, { 1, 2, 1, 6, 0, 1 }, { 4, 3, 4, 2, 1, 0 } };triangulation.setWeight(weight);}// 得到最优的三⾓形剖分，n是总边数-1public void minWeightTriangulation(int n, int[][] t, int[][] s) {// 初始化所有的⼆顶点多边形权值为0for (int i = 1; i <= n; i++) {t[i][i] = 0;}// 循环求解t[i][j]for (int r = 2; r <= n; r++) {// (j-i)的范围[2,n]// 当r=2时，循环实际上是在给t赋边的值，即相邻的两个顶点的权值，例如t[1][2],t[2][3]... for (int i = 1; i <= n - r + 1; i++) {// i的范围[1,n+1-r]，这⾥i要保证i+r<=nint j = i + r - 1;t[i][j] = t[i + 1][j] + getWeight(i - 1, i, j);// 这⾥实际上就是k=i// t[i][j] = t[i][i] + t[i + 1][j] + getWeight(i - 1, i, j)s[i][j] = i;// i-1,i,j// 循环k，范围是[i+1,j-1]，求出最⼩的t[i][j]for (int k = i + 1; k < j; k++) {// k是i和j之间的中间顶点int u = t[i][k] + t[k + 1][j] + getWeight(i - 1, k, j);// 以k作为划分得到的权值if (u < t[i][j]) {// 如果权值更⼩，那么同时更新t[i][j]和s[i][j]t[i][j] = u;s[i][j] = k;}}}}}// 我的写法，在第⼆个循环这⾥不同，没有什么差别，只是我易于我理解public void minWeightTriangulation2(int n, int[][] t, int[][] s) {// 初始化所有的⼆顶点多边形权值为0for (int i = 1; i <= n; i++) {t[i][i] = 0;}// 循环求解t[i][j]for (int r = 1; r <= n; r++) {// r=(j-i)的范围[1,n]// 当r=1时，循环实际上是在给t赋边的值，即相邻的两个顶点的权值，例如t[1][2],t[2][3],t[3][4]... for (int i = 1; i <= n - r; i++) {// i的范围[1,n-r]，这⾥i要保证 j=i+r<=nint j = i + r;t[i][j] = t[i + 1][j] + getWeight(i - 1, i, j);// 这⾥实际上就是k=i// t[i][j] = t[i][i] + t[i + 1][j] + getWeight(i - 1, i, j)s[i][j] = i;// i-1,i,j// 循环k，范围是[i+1,j-1]，求出最⼩的t[i][j]for (int k = i + 1; k < j; k++) {// k是i和j之间的中间顶点int u = t[i][k] + t[k + 1][j] + getWeight(i - 1, k, j);// 以k作为划分得到的权值if (u < t[i][j]) {// 如果权值更⼩，那么同时更新t[i][j]和s[i][j]t[i][j] = u;s[i][j] = k;}}}}}// 计算⼀个三⾓形的权值之和public int getWeight(int i, int j, int k) {return weight[i][j] + weight[j][k] + weight[i][k];}public int getN() {return n;}public void setN(int n) {this.n = n;}public int[][] getWeight() {return weight;}public void setWeight(int[][] weight) {this.weight = weight;}}五、代码运⾏结果截图。

三角剖分算法例题
三角剖分算法的例题可以参考以下内容：
给定一个凸多边形P，其顶点数为n。

要求用P中的n-3条弦将P剖分成n-2个三角形，使得n-3弦的长度之和最小。

首先，建立一个超级三角形PQR，这个三角形要把所有点都包含进去。

然后分析每个顶点，如果某个顶点在超级三角形的外接圆内部，那么利用这个顶点将超级三角形分拆成三个子三角形。

接下来，对于不在超级三角形外接圆内的顶点，如果它在某个子三角形内，那么再将这个子三角形分拆成三个子三角形。

然后，对每个子三角形检查其顶点是否在其它三角形的外接圆内。

如果某个顶点在某个三角形的外接圆内，那么删除这个三角形的公共边，并用这个顶点与其它边组成新的三角形。

最后，对于所有的子三角形，找出那些没有在其它三角形外接圆内的顶点，它们就是最优三角剖分的弦。

计算这些弦的长度之和即可。

注意：以上内容仅供参考，可以阅读数据结构与算法相关书籍获取更多信息。

凸三⾓形最优三⾓剖分问题相关定义：(1)凸多边形的三⾓剖分：将凸多边形分割成互不相交的三⾓形的弦的集合T。

(2)最优剖分：给定凸多边形P，以及定义在由多边形的边和弦组成的三⾓形上的权函数w。

要求确定该凸多边形的三⾓剖分，使得该三⾓剖分中诸三⾓形上权之和为最⼩。

下图为剖分案例。

若凸(n+1)边形P={V0,V1……Vn}的最优三⾓剖分T包含三⾓形V0VkVn,1<=k<=n，则T的权为三个部分权之和：三⾓形V0V k V n的权，多边形{V0,V1……V k}的权和多边形{V k,V k+1……V n}的权之和。

如下图所⽰：可以断⾔，由T确定的这两个⼦多边形的三⾓剖分也是最优的。

因为若有{V0,V1……V k}和{V0,V1……V k}更⼩权的三⾓剖分，将导致T不是最优三⾓剖分的⽭盾。

因此，凸多边形的三⾓剖分问题具有最优⼦结构性质。

3、递推关系：设t[i][j],1<=i<j<=n为凸多边形{V i-1,Vi……Vj}的最优三⾓剖分所对应的权值函数值，即其最优值。

最优剖分包含三⾓形Vi-1VkVj的权，⼦多边形{Vi-1,Vi……Vk}的权，⼦多边形{Vk，Vk+1……Vj}的权之和。

因此，可得递推关系式：凸(n+1)边形P的最优权值为t[1][n]。

三⾓剖分的结构及其相关问题。

凸三⾓形的三⾓剖分与表达式的完全加括号之间具有⼗分密切的关系。

正如所看到的⼀样，矩阵连乘的最优计算次序等价于矩阵链的最优完全加括号⽅式。

其实更加奇妙的地⽅是，这些问题似乎都是⼀个模⼦刻出来的！其实本质原因就是因为它们所对应的完全⼆叉树的同构性。

⼀个表达式的完全加括号⽅式相应于⼀棵完全⼆叉树，称为表达式的语法树。

⽽恰恰恰好的是，凸多边形的剖分也可以⽤语法数表⽰。

（请原谅“草滩⼩恪”画图功夫不⾏，⽆法画出对应的图） 模板主要代码：//t[][] 记忆路径， s[][] 记录最优路径 W（，，）为权值函数const int maxn = 100;void minWeightTriangulation(int n, int t[][100], int s[][100]){for(int i=1; i<=n; i++) t[i][i] = 0;for(int r=2; r<=n; r++)for(int i=1; i<=n-r+1; i++){int j = i + r - 1;t[i][j] = t[i+1][j] + w(i-1, i, j);s[i][j] = i;for(int k = i+1; k<j; k++){int u = t[i][k] + t[k+1][j] + w(i-1, k, j);if(u<t[i][j]){t[i][j] = u;s[i][j] = k;}}}}代码如有疑问可参见“矩阵连乘”。

凸多边形最优三⾓剖分相关概念凸多边形：当⼀个简单多边形及其内部构成⼀个闭凸集时，则称该简单多边形为⼀个凸多边形。

即凸多边形边界上或内部的任意两点所连成的直线段上所有点均在凸多边形的内部或边界上。

通常，⽤多边形顶点的逆时针序列表⽰凸多边形，即表⽰具有 n 条边，的凸多边形。

其中，约定。

弦：若与是多边形上不相邻的两个顶点，则线段称为多边形的⼀条弦。

弦将多边形分割成两个多边形和。

多边形的三⾓剖分三⾓剖分多边形的三⾓剖分是将多边形分割成互不相交的三⾓形的弦的集合 T。

下图为⼀个凸 7 边形的两个不同的三⾓剖分。

在凸多边形 P 的⼀个三⾓剖分 T 中，各弦互不相交，且集合T 已达到最⼤，即 P 的任⼀不在 T 中的弦必与 T 中某⼀弦相交。

在有 n 个顶点的凸多边形中，恰有 (n-3) 条弦和 (n-2) 个三⾓形。

最优三⾓剖分给定凸多边形，以及定义在由凸多边形的边和弦组成的三⾓形上的权函数 w ，要求确定该凸多边形的三⾓剖分，使得该三⾓剖分所应对的权，即三⾓剖分中诸三⾓形上权之和为最⼩。

最优⼦结构性质凸多边形的最优三⾓剖分问题有最优⼦结构性质。

事实上，若凸 (n+1) 边形，的最优三⾓剖分 T 包含三⾓形，则 T 的权为三⾓形的权，⼦多边形和的权之和。

可以断⾔，由 T 确定的这两个⼦多边形的三⾓剖分也是最优的。

因为若有和的更⼩权的三⾓剖分，将导致 T 不是最优三⾓剖分⽭盾。

最优三⾓剖分的递归结构令为凸⼦多边形的最优三⾓剖分对应的权函数值，即其最优值。

实现#include <bits/stdc++.h>using namespace std;const int N=7;int s[N][N],t[N][N],weight[][N]={{0,2,2,3,1,4},{2,0,1,5,2,3},{2,1,0,2,1,4},{3,5,2,0,6,2},{1,2,1,6,0,1},{4,3,4,2,1,0}};int dp(int n);void Traceback(int i,int j);int Weight(int a,int b,int c);int main(){cout<<"此多边形的最优三⾓剖分值为："<<dp(N-1)<<endl;cout<<"最优三⾓剖分结构为："<<endl;Traceback(1,N-2);system("pause");return0;}int dp(int n){int i,r,j,k,u;for(i=1;i<=n;i++) t[i][i] = 0;for(r=2;r<=n;r++){for(i=1;i<=n-r+1;i++){j=i+r-1;t[i][j]=t[i+1][j]+Weight(i-1,i,j);s[i][j]=i;for(k=i+1;k<j;k++){u =t[i][k]+t[k+1][j]+Weight(i-1,k,j);if(u<t[i][j]){t[i][j]=u;s[i][j]=k;}}}}return t[1][N-2];}void Traceback(int i,int j){if(i==j) return;Traceback(i,s[i][j]);Traceback(s[i][j]+1,j);cout<<"三⾓剖分顶点：V"<<i-1<<",V"<<j<<",V"<<s[i][j]<<endl; }int Weight(int a,int b,int c){return weight[a][b]+weight[b][c]+weight[a][c];}。

凸多边形最优三角剖分的最小弦长大家好，今天我们来聊聊一个有趣的话题：凸多边形最优三角剖分的最小弦长。

这个问题听起来有点高深，但其实它就是让我们去找出一种方法，把一个凸多边形分成若干个三角形，使得这些三角形的总周长最小。

这个问题在数学上叫做“平面三角剖分”，是一个非常经典的问题。

那么，这个问题有什么实际应用呢？其实它在很多领域都有用处，比如建筑设计、地理信息系统等等。

下面我们就来详细讲解一下这个问题。

我们要明确一点：凸多边形是什么样的图形呢？凸多边形就是指在一个平面上，由若干个点组成的封闭图形，其中任意两点之间的距离都小于它们之间的线段长度。

换句话说，凸多边形就是一个顶点都在内部的封闭图形。

这样的图形有很多特点，比如它的边界是光滑的，没有凹陷的地方；它的内部是空心的，没有实心的部分；它的面积和周长都是有限的等等。

接下来，我们就要想办法把这个凸多边形分成若干个三角形。

这个问题的关键在于如何找到一个合适的划分方法。

我们知道，一个三角形有三条边，而一个凸多边形有无数条边。

如果我们随便把这个多边形分成若干个小三角形，那么这些小三角形的总周长可能会很大。

所以我们需要找到一种方法，让这些小三角形尽可能地接近彼此，从而使得整个划分方案的总周长最小。

为了解决这个问题，我们可以先从一个简单的问题开始思考：如何把一个三角形分成两个更小的三角形？答案很简单，只要在三角形的一条边的中点处画一条线段即可。

这样一来，原来的大三角形就被分成了两个小三角形，而且这两个小三角形的总周长之和等于原来大三角形的周长减去这条中线段的长度。

这个结论对于任意形状的三角形都是成立的。

那么，对于一个凸多边形来说，我们能不能也用同样的方法来把它分成若干个更小的三角形呢？答案是肯定的。

我们只需要沿着凸多边形的边界一直画线段，直到把它分成若干个小多边形为止。

然后再对每个小多边形重复上面的步骤，把它分成更小的多边形。

这样一来，我们就可以得到一个无穷级数的结果：凸多边形被分成了若干个越来越小的三角形。

王博一种加权剖分简单多边形为三角形和凸四边形子域的算
法
王博，一种加权剖分简单多边形为三角形和凸四边形子域的算法。

该算法可以将简单多边形划分为三角形和凸四边形的子域，其主要思想如下：
1. 首先，找到简单多边形的凸包，即该多边形的外围凸多边形。

这可以通过一些计算凸包的方法来实现，如Graham扫描算法
或Jarvis步进算法。

2. 对凸包中的每个凸点，构建一个划分线段，将简单多边形沿着该划分线段分割为两个凸四边形。

3. 对于剩余的边，根据其几何特征进行分类处理。

- 如果是一条凹边，即边内部的角度大于180度，则将其与
与之相邻的凸点构成的三角形进行分割。

- 如果是一条凸边，即边内部的角度小于等于180度，将其
与相邻的两个凸点构成的三角形进行分割。

4. 重复上述过程，直到所有的子域都被划分为三角形和凸四边形为止。

需要注意的是，在每个步骤中，我们需要根据一些加权策略选
择最优的划分方式，以确保生成的子域尽可能接近原始简单多边形的形状。

总结起来，该算法可以按照凸包和凹凸边的特征，将简单多边形划分为凸四边形和三角形子域。

三角剖分的算法设计及其应用三角剖分是计算几何学中的重要问题，它将平面上的一个多边形分割成一系列三角形。

这个问题在计算机图形学、地图制图和有限元分析等领域中都有广泛的应用。

三角剖分的核心问题是如何确定一个合适的剖分方案，使得生成的三角形数量足够少且满足一些特定的性质。

本文将介绍三角剖分的算法设计及其应用。

首先，我们将介绍三角剖分的基本概念，包括 Delaunay 三角剖分和 Voronoi 图。

然后，我们将讨论常见的三角剖分算法，包括 Dwyer 算法、Lawson 算法和 Ruppert 算法。

最后，我们将介绍一些三角剖分的应用，包括地图制图、计算机图形学和有限元分析。

一、基本概念1.1 Delaunay 三角剖分Delaunay 三角剖分是一种最小化三角形最大角度的三角剖分方案。

它可以保证三角形的质量较高，同时具有良好的几何性质。

给定一组点，Delaunay 三角剖分将这些点连接成一组非重叠的三角形。

在 Delaunay 三角剖分中，对于任意两个不在同一个三角形中的点，它们之间都没有其他点，且连接它们的线段都在三角剖分中。

1.2 Voronoi 图Voronoi 图是与 Delaunay 三角剖分相对应的图形结构。

在Voronoi 图中，每个点都与某个三角形的外接圆心相连，形成一组多边形。

这些多边形称为 Voronoi 多边形。

在 Voronoi 图中，一个点的 Voronoi 多边形是由所有与该点相邻的三角形的外接圆心组成的凸包。

二、三角剖分算法2.1 Dwyer 算法Dwyer 算法是一种有效的增量式三角剖分算法，适用于平面上的任意多边形。

该算法基于 Delaunay 三角剖分的特殊性质，每次添加一个点时只需修改最近的三角形即可。

Dwyer 算法的时间复杂度为 O(n log n)，其中 n 表示顶点数。

2.2 Lawson 算法Lawson 算法是一种优化型三角剖分算法，可以消除 Delaunay 三角剖分中存在的低质量三角形。

凸多边形最优三角剖分一、问题描述多边形是平面上的分段线性闭合曲线。

换句话说，多边形由一系列端到端连接的直线段组成。

构成多边形的每条直线段称为多边形的边。

多边形的两条边之间的连接点称为多边形的顶点。

如果多边形的边除了连接顶点之外没有其他公共点，则该多边形称为简单多边形。

一个简单的多边形将平面分为三部分：多边形中包围的所有点构成多边形的内部；多边形本身构成多边形的边界；平面上的其余点构成多边形的外部。

当一个简单多边形及其内部形成一个闭凸集时，它被称为凸多边形。

也就是说，由凸多边形边界上或内部的任意两点连接的直线段上的所有点都位于凸多边形的内部或边界上。

通常，用多边形顶点的逆时针序列来表示一个凸多边形，即p={v0,v1,?,vn-1}表示具有n条边v0v1，v1v2，?,vn-1vn的一个凸多边形，其中，约定v0=vn。

若vi与vj是多边形上不相邻的两个顶点，则线段vivj称为多边形的一条弦。

弦将多边形分割成凸的两个子多边形{vi,vi+1,?,vj}和{vj,vj+1,?,vi}。

多边形的三角剖分是一个将多边形分割成互不相交的三角形的弦的集合t。

图1是一个凸多边形的两个不同的三角剖分。

图一凸多边形的两种不同三角剖分在凸多边形p的一个三角剖分t中，各弦互不相交，且弦数已达到最大，即p的任一不在t中的弦必与t中某一弦相交。

在一个有n个顶点的凸多边形的三角剖分中，恰好有n-3条弦和n-2个三角形。

凸多边形的最优三角剖分问题是给出一个凸多边形P={V0，V1，？，vn-1}和定义在由多边形ω的边和弦组成的三角形上的权函数。

需要确定凸多边形的三角剖分，以便与三角剖分对应的权重，即三角剖分中三角形上的权重之和，这是最低要求。

三角形上的各种权函数可以定义为ω。

例如：fixed义ω(vivjvk)=|v ivj|+|vivk|+|vkvj|，其中，|vivj|是点vi到vj的欧氏距离。

相应该权函数的最佳三角剖分是最小弦长三角剖分。