凸多边形最优三角剖分
凸多边形最优三角剖分
一、问题描述
多边形是平面上一条分段线性的闭曲线。也就是说，多边形是由一系列首尾相接的直线段组成的。组成多边形的各直线段称为该多边形的边。多边形相接两条边的连接点称为多边形的顶点。若多边形的边之间除了连接顶点外没有别的公共点，则称该多边形为简单多边形。一个简单多边形将平面分为3个部分：被包围在多边形内的所有点构成了多边形的内部；多边形本身构成多边形的边界；而平面上其余的点构成了多边形的外部。当一个简单多边形及其内部构成一个闭凸集时，称该简单多边形为凸多边形。也就是说凸多边形边界上或内部的任意两点所连成的直线段上所有的点均在该凸多边形的内部或边界上。
通常，用多边形顶点的逆时针序列来表示一个凸多边形，即P={v0 ,v1 ,… ,v n-1}表示具有n条边v0v1，
v1v2，… ,v n-1v n的一个凸多边形，其中，约定v0=v n。
若v i与v j是多边形上不相邻的两个顶点，则线段v i v j称为多边形的一条弦。弦将多边形分割成凸的两个子多边形{v i ,v i+1 ,… ,v j}和{v j ,v j+1 ,… ,v i}。多边形的三角剖分是一个将多边形分割成互不相交的三角形的弦的集合T。图1是一个凸多边形的两个不同的三角剖分。
图1 一个凸多边形的2个不同的三角剖分
在凸多边形P的一个三角剖分T中，各弦互不相交，且弦数已达到最大，即P的任一不在T中的弦必与T 中某一弦相交。在一个有n个顶点的凸多边形的三角剖分中，恰好有n-3条弦和n-2个三角形。
凸多边形最优三角剖分的问题是：给定一个凸多边形P={v0 ,v1 ,… ,v n-1}以及定义在由多边形的边和弦组成的三角形上的权函数ω。要求确定该凸多边形的一个三角剖分，使得该三角剖分对应的权即剖分中诸三角形上的权之和为最小。
可以定义三角形上各种各样的权函数ω。例如：定义ω(v i v j v k)=|v i v j|+|v i v k|+|v k v j|，其中，|v i v j|是点v i到v j 的欧氏距离。相应于此权函数的最优三角剖分即为最小弦长三角剖分。
二、算法思路
凸多边形的三角剖分与表达式的完全加括号方式之间具有十分紧密的联系。正如所看到过的，矩阵连乘积的最优计算次序问题等价于矩阵链的完全加括号方式。这些问题之间的相关性可从它们所对应的完全二叉树的同构性看出。
一个表达式的完全加括号方式对应于一棵完全二叉树，人们称这棵二叉树为表达式的语法树。例如，与完全加括号的矩阵连乘积((A1(A2A3))(A4(A5A6)))相对应的语法树如图2(a)所示。
图2 表达式语法树与三角剖分的对应
语法树中每一个叶子表示表达式中一个原子。在语法树中，若一结点有一个表示表达式E1的左子树，以及一个表示表达式E r的右子树，则以该结点为根的子树表示表达式(E1E r)。因此，有n个原子的完全加括号表达式对应于惟一的一棵有n个叶结点的语法树，反之亦然。
凸多边形{v0 ,v1 ,… ,v n-1}的三角剖分也可以用语法树来表示。例如，图1(a)中凸多边形的三角剖分可用图
2(b)所示的语法树来表示。该语法树的根结点为边v0v6，三角剖分中的弦组成其余的内部结点。多边形中除v0v6边外的每一条边是语法树的一个叶结点。树根v0v6是三角形v0v3v6的一条边，该三角形将原多边形分为3个部分：三角形v0v3v6，凸多边形{v0 ,v1 ,… ,v3}和凸多边形{v3 ,v4 ,… ,v6}。三角形v0v3v6的另外两条边，即弦v3v6和v0v3为根的两个儿子。以它们为根的子树分别表示凸多边形{v0 ,v1 ,… ,v3}和凸多边形
{v3 ,v4 ,… ,v6}的三角剖分。
在一般情况下，一个凸n边形的三角剖分对应于一棵有n-1个叶子的语法树。反之，也可根据一棵有n-1个叶子的语法树产生相应的一个凸n边形的三角剖分。也就是说，凸n边形的三角剖分与n-1个叶子的语法树之间存在一一对应关系。由于n个矩阵的完全加括号乘积与n个叶子的语法树之间存在一一对应关系，因此n个矩阵的完全加括号乘积也与凸(n+1)边形的三角剖分之间存在一一对应关系。图2的(a)和(b)表示出了这种对应关系，这时n=6。矩阵连乘积A1A2..A6中的每个矩阵A i对应于凸(n+1)边形中的一条边v i-1v i。三角剖分中的一条弦v i v j，i 事实上，矩阵连乘积的最优计算次序问题是凸多边形最优三角剖分问题的一个特殊情形。对于给定的矩阵链A1A2..A n，定义一个与之相应的凸(n+1)边形P={v0 ,v1 ,… ,v n}，使得矩阵A i与凸多边形的边v i-1v i一一对应。若矩阵A i的维数为p i-1×p i,i=1,2,…,n，则定义三角形v i v j v k上的权函数值为：ω(v i v j v k)=p i p j p k。依此权函数的定义，凸多边形P的最优三角剖分所对应的语法树给出矩阵链A1A2..A n的最优完全加括号方式。 三、实验源程序 新建一个类CTriangle，Class type选择Generic Class。 Triangle.h代 码 typedef struct { int x; int y; }point; class CTriangle { public: bool Run(); CTriangle(); virtual ~CTriangle(); private: //用递归的方法输出剖分后的各个三角形 void Traceback(int i,int j,int **s); //计算最优值算法 bool minWeightTriangulation(); //处理键盘输入，同时判断能否构成一个凸多边形 bool Input(); //计算三角形权值的函数 int w(point X,point Y,point Z); //计算平面上任意两点间距离的函数 int distance(point X,point Y); //记录最优三角剖分中所有三角形信息 int **s; //记录最优三角剖分所对应的权函数值 int **t; //记录凸多边形各顶点坐标 point *v; //记录坐标在直线方程中的值 int *total; int M; }; Triangle.cpp代 码 #define N 50 #include #include #include #include "Triangle.h" CTriangle::CTriangle() { M = 0; t = new int *[N]; s = new int *[N]; for(int i=0 ; i { t[i] = new int[N]; s[i] = new int[N]; } v = new point[N]; total = new int[N]; } CTriangle::~CTriangle() { for(int i=0 ; i { delete []t[i]; delete []s[i]; } delete []t; delete []s; delete []v; delete []total; } int CTriangle::distance(point X, point Y) { int dis = (Y.x-X.x)*(Y.x-X.x) + (Y.y-X.y)*(Y.y-X.y); return (int)sqrt(dis); } int CTriangle::w(point X, point Y, point Z) { return distance(X,Y) + distance(Y,Z) + distance(Z,X); } bool CTriangle::Input() { int m; int a,b,c; cout<<"请输入凸多边形顶点个数："; cin>>m; M = m-1; for(int i=0 ; i { cout<<"输入顶点v"< } //根据顶点坐标判断是否能构成一个凸多边形 for(int j=0 ; j { int p = 0; int q = 0; if(m-1 == j) { a = v[m-1].y - v[0].y; b = v[m-1].x - v[0].y; c = b * v[m-1].y - a * v[m-1].x; } else { a = v[j].y - v[j+1].y; b = v[j].x - v[j+1].x; c = b * v[j].y - a * v[j].x; } for(int k=0 ; k { total[k] = a * v[k].x - b * v[k].y + c; if(total[k] > 0) { p = p+1; } else if(total[k] < 0) { q = q+1; } } if((p>0 && q>0) || (p==0 && q==0)) { cout<<"无法构成凸多边形！"< } } if(NULL != v) return true; else return false; } bool CTriangle::minWeightTriangulation() { if(NULL == v) return false; for(int i=1 ; i<=M ; i++) t[i][i] = 0; for(int r=2 ; r<=M ; r++) for(int i=1 ; i<=M-r+1 ; i++) { int j = i+r-1; t[i][j] = t[i+1][j] + w(v[i-1],v[i],v[j]); s[i][j] = i; for(int k=i+1 ; k { int u = t[i][k] + t[k+1][j] + w(v[i-1],v[k],v[j]); if(u < t[i][j]) { t[i][j] = u; s[i][j] = k; } } } return true; } void CTriangle::Traceback(int i, int j, int **s) { if(i == j) return; /*{ cout<<"分成的三角形依次为："< else*/ Traceback(i,s[i][j],s); Traceback(s[i][j]+1,j,s); cout<<"三角形： v"< } bool CTriangle::Run() { if(Input()) { if(CTriangle::minWeightTriangulation()) { CTriangle::Traceback(1,M,s); cout< cout<<"最优权值之和为： "< return true; } else return false; } else return false; } main.cpp代 码 #include "Triangle.h" void main() { CTriangle triangle; triangle.Run(); } 四、测试结果 给定的七个顶点坐标分别为(8,26)、(0,20)、(0,10)、(10,0)、(22,12)、(27,21)、(15,26)，测试结果如下： 该程序有一定的灵活性，用户可以自己选择顶点的个数以及顶点坐标，并对顶点坐标进行分析，判断这些顶点能否构成一个凸多边形，例如输入四个点坐标(0,0)、(0,10)、(4,4)、(10,0)，这四个点构成的多边形显然是一个凹多边形，测试结果为： 五、总结 （1）凸多边形的最优三角剖分本来是一个几何问题，但通过分析，它本质上于矩阵连乘积的最优计算次序问题极为相似，从而可以将问题进行转化，用动态规划算法有效的解决这个问题。 （2）本实验的七个顶点坐标数据是给定的，可以构成一个凸多边形，但对于未知的数据，事先并不知道所给数据能否构成一个凸多边形。所以我在这里多做了一点工作，就是如何判断所给的顶点能否构成凸多边形。解决思路是： 用两点式推导直线一般方程，设已知的两点坐标分别为(x1,y1),(x2,y2),得 x*(y1-y2)-y*(x1-x2)+(x1-x2)*y2-x1*(y1-y2)=0, 令a=y1-y2,b=x1-x2,c=(x1-x2)*y1-x1*(y1-y2)。即ax+by+c=0。 对于任一条直线ax+by+c=0 (a,b不同时为0)，则其余非构成直线的点的坐标(x,y)代入直线方程，若 ax+by+c>0,则该点在直线右侧；若ax+by+c<0,则点在直线左侧;若ax+by+c=0,则在直线上。例：有一直线5x-6y+3=0,一点(5,0)代入直线方程，则方程左式>0所以点(5,0)在直线右侧。 程序中用指针v来记录各点坐标，按逆时针依次输入。用*total来记录坐标在直线方程中的值。用p和q 分别记录点代入方程所得值的正或负的点的个数。若是凸多边形，则应全为正或全为负，即p>0和q>0不同时成立；若是凹多边形，则p>0和q>0同时成立。而其中若p=0和q=0同时成立，则不能构成多边形。 《算法分析与设计》期末复习题 一、选择题 1.算法必须具备输入、输出和（ D ）等4个特性。 A．可行性和安全性B．确定性和易读性 C．有穷性和安全性D．有穷性和确定性 2.算法分析中，记号O表示（ B ），记号Ω表示（ A ） A.渐进下界 B.渐进上界 C.非紧上界 D.紧渐进界 3.假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。在某台计算机上实现并完 成概算法的时间为t秒。现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题（ B ）解题方法：3*2^n*64=3*2^x A．n+8 B．n+6 C．n+7 D．n+5 4.设问题规模为N时，某递归算法的时间复杂度记为T(N)，已知T(1)=1， T(N)=2T(N/2)+N/2，用O表示的时间复杂度为（ C ）。 A．O(logN) B．O(N) C．O(NlogN) D．O(N2logN) 5.直接或间接调用自身的算法称为（ B ）。 A．贪心算法B．递归算法 C．迭代算法D．回溯法 6.Fibonacci数列中，第4个和第11个数分别是（ D ）。 A．5，89 B．3，89 C．5，144 D．3，144 7.在有8个顶点的凸多边形的三角剖分中，恰有（ B ）。 A．6条弦和7个三角形B．5条弦和6个三角形 C．6条弦和6个三角形D．5条弦和5个三角形 8.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A．重叠子问题B．最优子结构性质 C．贪心选择性质D．定义最优解 9.下列哪个问题不用贪心法求解（ C ）。 A．哈夫曼编码问题B．单源最短路径问题 C．最大团问题D．最小生成树问题 10.下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A．备忘录法B．动态规划法 C．贪心法D．回溯法 11.下列算法中不能解决0/1背包问题的是（ A ）。 A．贪心法B．动态规划 C．回溯法D．分支限界法 12.下列哪个问题可以用贪心算法求解（ D ）。 三角形的分割（一） 同学们大家好！三角形的面积的计算方法大家已经知道了，今天我再告诉大家一个规律：等底等高的三角形面积相等。这是一个非常重要的规律，在解决多边形面积的许多问题中都要用到它。 今天，我们就一起来研究应用这一规律可以解决哪些问题。 【典型例题】 一. 阅读思考： 例1. 有一个三角形花坛，想把它平均分成两个相等的三角形，可以怎样分？ 分析与解答：因为“等底等高的三角形面积相等”，所以要把这个三角形花坛平均分成两个相等的三角形，就是把这个三角形花坛分成两个等底等高的三角形就可以了。而三角形的每条边都可以作三角形的底，所以我们只要把这三条边分别二等分，再把中点与这条边相对的顶点连接起来就可以了。 例2. 将任一三角形分成面积相等的六个三角形，应怎么分？ 分析与解：根据等底等高的三角形面积相等这一结论，只要把原三角形分成六个等底等高的小三角形，它们的面积就必然相等。而要找这六个等底等高的小三角形，只需把三角形的某一边六等分，再将各分点与这边相对的顶点连结起来即可。如图（1） 图（1） 又因为6163223=?=?=?，所以，如果我们把每一个小三角形的面积看成1，即16? 而32?可以看成是先把原三角形等分两份，再把每一份分别等分成三份。 C C 图（2） 同理，23?可以看成是先把原三角形等分成三份，然后再把每一份等分成两份。 即 A A A B C 图（3） 类似于这样的分法，我们还可以画出许多，这里就不一一列举了。 这两道例题有一个共同的思路，就是想办法找出等底等高的三角形，而找这种三角形，就要几等分某一条线段。 如果两个三角形的底相等，高不相等，它们的面积有什么关系呢？ 如果两个三角形底的长度相等，高的长度不相等，那么它们的面积之比正好等于这两个三角形高的长度比。 同样的道理，我们还可以推出，如果两个三角形高的长度相等，底的长度不相等，那么这两个三角形的面积之比正好等于它们的底的长度比，因此我们有下面的结论： 如果甲、乙两个三角形的底（高）的长度相等，那么甲、乙两个三角形的面积之比等于它们的高（底）的长度之比。 例3. 把三角形ABC 分成甲、乙、丙三部分，使甲的面积是乙的面积的3倍，丙的面积是乙的面积的4倍。 分析与解：要想使三角形甲的面积是三角形乙的面积的3倍，可以使这两个三角形的高相同，而三角形甲的底是三角形乙的底的3倍，同样使三角形丙的高和三角形乙的高相同，而三角形丙的底是三角形乙的底的4倍，这样一来，我们将三角形ABC 的一条边 8等分，使乙占其中的一份，甲占其中的3份，丙占其中的4份，即可达到目的。 B C 例4. 三角形ABC 中，DC=2BD ，CE=3AE ，阴影部分的面积是20平方厘米，求三角形ABC 的面积。（如图） B D C 分析与解：根据如果两个三角形的高相等，那么这两个三角形的面积比等于它们底的比的结论，即可 西安电子科技大学网络教育 2010学年上学期期末考试模拟试题一 一、 填空题（每小题4分，共计40分） 1. 通常只考虑三种情况下的时间复杂度，即 情况、 情况和 情况 下的时间复杂度，分别记为T max (N)、T min (N) 和T avg (N)，实践表明可操作性最好且最有实 际价值的是 情况下的时间复杂度。 2. n n 1032 的渐近表达式是 ， )log(3n 的渐近表达式是 。 3. 根据符号O 的定义易知O(1)=O(2)，用O(1)和O(2)表示同一个方法时，差别仅在于其中 的 。 4. 递归算法是指 的算法， 递归函数是指 的函数。 5. 贪心算法总是做出在当前看来_____________的选择，也就是说，贪心算法并不从整体最优考虑它 所做出的选择只是在某种意义上的________________。 6. 如果某问题具有________________________和___________________________两个重要性质，该问题可以用贪心算法求解。 7. 单源最短路径问题适合用_______________算法来求解、0-1背包问题适合用_____________算法来 求解。 8. 分治法是将一个规模为n 的问题分解为k 个规模________的子问题，这些子问题___________且与 原问题__________。递归地求解这些子问题，然后将各个子问题的解_________得到原问题的解。 9. 动态规划算法的两个基本要素是____________________和____________________。 10.___ 算法可以有效地解凸多边形最优三角剖分问题，而____________算法是求解最优 装载问题的有效方法。 二、简答题（每小题10分，共计40分） 1. 如果只需要求解问题的最优值，动态规划算法步骤是什么？如果需要构造最优解，则还需要加上什么步骤？ 2. 请简述什么是贪心选择性质 3. 请简述什么是最小生成树。 4. 请简述贪心算法比动态规划算法效率高的原因。 凸多边形最优三角剖分 一、问题描述 多边形是平面上一条分段线性的闭曲线。也就是说，多边形是由一系列首尾相接的直线段组成的。组成多边形的各直线段称为该多边形的边。多边形相接两条边的连接点称为多边形的顶点。若多边形的边之间除了连接顶点外没有别的公共点，则称该多边形为简单多边形。一个简单多边形将平面分为3个部分：被包围在多边形内的所有点构成了多边形的内部；多边形本身构成多边形的边界；而平面上其余的点构成了多边形的外部。当一个简单多边形及其内部构成一个闭凸集时，称该简单多边形为凸多边形。也就是说凸多边形边界上或内部的任意两点所连成的直线段上所有的点均在该凸多边形的内部或边界上。 通常，用多边形顶点的逆时针序列来表示一个凸多边形，即P={v0 ,v1,… ,v n-1}表示具有n条边v0v1，v1v2，… ,v n-1v n的一个凸多边形，其中，约定v0=v n。 若v i与v j是多边形上不相邻的两个顶点，则线段v i v j称为多边形的一条弦。弦将多边形分割成凸的两个子多边形{v i ,v i+1 ,… ,v j}和 {v j ,v j+1 ,… ,v i}。多边形的三角剖分是一个将多边形分割成互不相交的三角形的弦的集合T。图1是一个凸多边形的两个不同的三角剖分。 图1 一个凸多边形的2个不同的三角剖分 在凸多边形P的一个三角剖分T中，各弦互不相交，且弦数已达到最大，即P的任一不在T中的弦必与T中某一弦相交。在一个有n个顶点的凸多边形的三角剖分中，恰好有n-3条弦和n-2个三角形。 凸多边形最优三角剖分的问题是：给定一个凸多边形P={v0 ,v1 ,… ,v n-1}以及定义在由多边形的边和弦组成的三角形上的权函数ω。要求确定该凸多边形的一个三角剖分，使得该三角剖分对应的权即剖分中诸三角形上的权之和为最小。 可以定义三角形上各种各样的权函数ω。例如：定义ω(v i v j v k)=|v i v j|+|v i v k|+|v k v j|，其中，|v i v j|是点v i到v j的欧氏距离。相应于此权函数的最优三角剖分即为最小弦长三角剖分。 二、算法思路 凸多边形的三角剖分与表达式的完全加括号方式之间具有十分紧密的联系。正如所看到过的，矩阵连乘积的最优计算次序问题等价于矩阵链的完全加括号方式。这些问题之间的相关性可从它们所对应的完全二叉树的同构性看出。 Delaunay三角剖分算法 默认分类2009-12-16 11:41:23 阅读33 评论0 字号：大中小订阅 转载：https://www.wendangku.net/doc/4a14363781.html,/renliqq/archive/2008/02/06/1065399.html 1. 三角剖分与Delaunay剖分的定义 如何把一个散点集合剖分成不均匀的三角形网格，这就是散点集的三角剖分问题，散点集的三角剖分，对数值分析以及图形学来说，都是极为重要的一项预处理技术。该问题图示如下： 1.1.三角剖分定义 【定义】三角剖分：假设V是二维实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段, E为e的集合。那么该点集V的一个三角剖分T=(V,E)是一个平面图G，该平面图满足条件： 1.除了端点，平面图中的边不包含点集中的任何点。 2.没有相交边。 3.平面图中所有的面都是三角面，且所有三角面的合集是散点集V的凸包。 1.2. Delaunay三角剖分的定义 在实际中运用的最多的三角剖分是Delaunay三角剖分，它是一种特殊的三角剖分。先从Delaunay边说起： 【定义】Delaunay边：假设E中的一条边e（两个端点为a,b），e若满足下列条件，则称之为Delaunay边：存在一个圆经过a,b两点，圆内(注意是圆内，圆上最多三点共圆)不含点集V中任何其他的点，这一特性又称空圆特性。 【定义】Delaunay三角剖分：如果点集V的一个三角剖分T只包含Delaunay边，那么该三角剖分称为Delaunay三角剖分。 1.3.Delaunay三角剖分的准则 要满足Delaunay三角剖分的定义，必须符合两个重要的准则： 算法设计与分析第三章程序作业 源程序代码 1.最长公共子序列 #include #define N 1000 int e[N][N],f[N][N]; void LCSLength(int m,int n,char *x,char *y,int c[][N],int b[][N])//构造数组b[i][j] { int i,j; for (i=1; i<=m;i++) c[i][0]=0; //初始化, Y[j]为空时 for (i=1;i<=n;i++) c[0][i]=0; //初始化，X[i]为空时 for (i=1;i<=m;i++) //两重循环，自下而上，// 计算子问题{X(i), Y(j)} for (j=1;j<=n;j++){ if(x[i]==y[j]) { //情况1 c[i][j]=c[i-1][j-1]+1; b[i][j]=1; } else if(c[i-1][j]>=c[i][j-1]) { //情况2 c[i][j]=c[i-1][j]; b[i][j]=2; } else //情况3 { c[i][j]=c[i][j-1]; b[i][j]=3; } } } void LCS(int i,int j,char *x,int b[][N]) { if (i==0||j==0) return; if (b[i][j]==1) { LCS(i-1,j-1,x,b); printf("%c",x[i]); /*第1种情况下，X(i)和Y(j)的最长公共子序列由X(i-1)和Y(j-1)的解LCS(i-1, j-1, x, b)，加上位于最后的X[i] 组成*/ 网格中的三角形 河北张家口市第十九中学 贺峰 随着新课程的实施，在近几年的中考试卷中出现了许多新颖的网格型试题，这类试题具有很强的直观性、可操作性、开放性及综合性等特点，不仅能够考查学生的数学知识，体现分类、数形结合等重要的数学思想，同时也考查和培养学生的识图、归纳、动手操作、自主探究等多种能力，有利于培养学生的探究意识和创新精神。现以近几年中考试题中出现的“网格中的三角形”为例，为同学们加以归类分析： 一、网格中的“等面积三角形” 例1 已知在正方形网格中，每个小方格都是边长为1的正方形，A 、B 两点在小方格的顶点上，位置如图1所示，点C 也在小方格的顶点上，且以A 、B 、C 为顶点的三角形面积为1，则点C 的个数为（ ） （A ）3个 （B ）4个 （C ）5个 （D ）6个 析解：此题以网格为载体来考查同学们等面积三角形的构成，体现分类讨论思想，若使点C 在小方格的顶点上，且以A 、B 、C 为顶点的三角形面积为1， 即保证△ABC 的底为2，高为1，因此须分类讨论的思想方法，即按AC ＝2时、BC ＝2时进行分类求解。答案如图2所示： 说明：此题也可通过对图形对称变换进行求解，即确定第（1）、（3）、（5）三种情况，分别以AB 所在的直线为对称轴将△ABC 翻折，使点C 落在格点上即可求解。 即可求解。 二、网格中的“等腰三角形” 例2如图3所示，A 、B 是4×5网络中的格点，网格中的每个小正方形的边长为1，请在图中清晰标出使以A 、B 、C 为顶点的三角形是等腰三角形的 所有格点C 的位置． 析解：此题以网格为载体来考查同学们等腰三角形的构成，体现分类讨论思 想，若使点C 在小方格的顶点上，且以A 、B 、C 为顶点的三角形为等腰三角形，即保证△ABC 中AB ＝AC 或AB ＝BC 或AC ＝AB ，即分别以AC 、AB 、BC 为腰时进行分类求解。答案如图4所示： 说明：此题也可通过对图形旋转变换进行求解，即以AB 为腰，分别以点A 、点B 为旋转中心，将线段AB 进行旋转，使点B 、点A 落在格点上即可求解。 三、网格中的“直角三角形” 例3如图5，正方形网格中，小格的顶点叫做格点，小华按下列要求作图： ①在正方形网格的三条不同实线上各取一个格点，使其中任意两点不在同一条实线 上；②连结三个格点，使之构成直角三角形， 小华在左边的正方形网格中作出了Rt △ABC ，请你按照同样的要求，在右边的两个 正方形网格中各画出一个直角三角形，并使三个网格中的直角三角形互不全等。 析解：此题开放性很强， 给学生广阔的思维空 图1 A 图3 图 4 A B C 图5 图6 C C C C C C （1） （2） （3） （5） （6） 图2 凸多边形的最优三角剖分程序清单： #include ICEM 二维三角形结构化网格(Y-Block) 1 三角形结构 ①构建如图1.1a所示的三角形结构(蓝)、建立如图1.1b所示的辅助线和点(红)； Fig. 1.1a Generate the triangle Fig. 1.1b Create the auxiliary curves and points ②创建2D planar block，如图1.2； Fig. 1.2 Create the 2D Planar Block ③分割块(O-Grid)：选择block，选择两条edge(11-13和13-21)，如图1.3a，分割结果如图1.3b (a) (b) Fig. 1.3 Split the block ④映射关联点：模型树中选择Geometry →Points →Show Point Names；Blocking →Vertices →Numbers。如图1.4a；注意：vertex number和point name 随个人作图顺序不一样。 作映射： Vertex 34 →Point 08; Vertex 19 →Point 03; Vertex 21 →Point 00; Vertex 35 →Point 04; Vertex 13 →Point 02; Vertex 33 →Point 05; Vertex 11 →Point 01; 映射结果见图1.4b； (a) Show Point Names and Vertices Numbers (b) Fig. 1.4 Associate Vertex ⑤构建网格，及检查质量，如图1.5 Fig. 1.5 Meshing 一、问题描述 多边形是平面上一条分段线性的闭曲线。也就是说，多边形是由一系列首尾相接的直线段组成的。组成多边形的各直线段称为该多边形的边。多边形相接两条边的连接点称为多边形的顶点。若多边形的边之间除了连接顶点外没有别的公共点，则称该多边形为简单多边形。一个简单多边形将平面分为3个部分：被包围在多边形内的所有点构成了多边形的内部；多边形本身构成多边形的边界；而平面上其余的点构成了多边形的外部。当一个简单多边形及其内部构成一个闭凸集时，称该简单多边形为凸多边形。也就是说凸多边形边界上或内部的任意两点所连成的直线段上所有的点均在该凸多边形的内部或边界上。 通常，用多边形顶点的逆时针序列来表示一个凸多边形，即P={v0 ,v1 ,… ,v n-1}表示具有n条边v0v1，v1v2，… ,v n-1v n的一个凸多边形，其中，约定v0=v n。 若v i与v j是多边形上不相邻的两个顶点，则线段v i v j称为多边形的一条弦。弦将多边形分割成凸的两个子多边形{v i ,v i+1 ,… ,v j}和{v j ,v j+1 ,… ,v i}。多边形的三角剖分是一个将多边形分割成互不相交的三角形的弦的集合T。图1是一个凸多边形的两个不同的三角剖分。 图1 一个凸多边形的2个不同的三角剖分 在凸多边形P的一个三角剖分T中，各弦互不相交，且弦数已达到最大，即P的任一不在T中的弦必与T中某一弦相交。在一个有n个顶点的凸多边形的三角剖分中，恰好有n-3条弦和n-2个三角形。 凸多边形最优三角剖分的问题是：给定一个凸多边形P={v0 ,v1 ,… ,v n-1}以及定义在由多边形的边和弦组成的三角形上的权函数ω。要求确定该凸多边形的一个三角剖分，使得该三角剖分对应的权即剖分中诸三角形上的权之和为最小。 第9卷 第5期 1997年9月计算机辅助设计与图形学学报J.CAD &CG V o l .9,N o.5Sep.,1997 任意曲面的三角形网格划分 陈永府 张 华 陈 兴 李德群 (华中理工大学塑性模拟及模具技术国家重点实验室 武汉 430074) 摘要 把曲面分为可展曲面和不可展曲面,对可展曲面用曲面展开算法展成平面,对不可展曲面用曲面分割算法转化成平面片,在平面上运用D elaunay 三角划分法进行网格划分,然后把网格节点反映射到曲面上,从而实现任意曲面的三角形网格划分。 关键词 D elaunay 三角划分,可展曲面,不可展曲面,曲面展开算法,曲面分割算法。 1996201203收稿,1996211222收到修改稿。本文得到“八五”重点攻关项目“注塑成形的计算机仿真与交互计算”资助。陈永府,1972年生,硕士研究生,研究方向为注塑模CA E 的前处理。张 华,博士研究生,研究方向为注塑模CA E 。陈 兴,副教授,研究方向为注塑模CAD 。李德群,博士生导师,研究方向为模具CAD 、CA E 、CAM 。 1 引 言 网格划分是计算机图形学研究的重要内容。目前,有很多种网格划分算法,如拓扑分解法、节点连接法、映射单元法、基于栅格法等。这些算法在二维网格划分上各有千秋,但对三维任意曲面的网格划分,成功的例子却很少。俄国数学家D elaunay 在1934年就证明了:对于任意给定的平面点集,有且仅有一种三解剖分方法能够满足“最大2最小角”优化准则,即所有三角形的最小内角之和最大。Sib son [1]证明了平面任意给定点集的D elauay 三角划分具有整体最优化的性质,这就是说,对于任意给定的平面点集,D elaunay 三角划分能够得到整体最优的三角形网格,能尽可能地避免病态三角形的出现。所以,D elaunay 三角划分在许多应用领域,尤其是在实体几何造型和有限元网格自动生成等研究领域,受到广泛的重视。但是传统的D elaunay 三角划分不能对三维任意曲面进行网格划分,为了解决这个问题,本文把曲面分为可展曲面和不可展曲面,分别对可展曲面采用曲面展开算法,对不可展曲面采用曲面分割算法;将曲面转化为平面,然后在平面上利用D elaunay 三角划分的优化性质进行网格划分,再将网格节点反映射到曲面上(限于篇幅,本文略去网格节点反映射到曲面上的算法),从而实现任意曲面的三角形网格划分。 2 平面任意多边形域的D elaunay 三角划分 L aw son [2]根据“最大2最小角”优化准则,通过“对角线交换”法则实现了二维给定点 集的D elaunay 三角划分。W atson [3]首次提出 “插入多边形”,并在此基础上,利用“外接__________________________________________________________https://www.wendangku.net/doc/4a14363781.html, 三角形分割成等腰三角形的条件和分法 制作人：陈预立林大中谢恒基 放学回家的路上，走进小区，小区内有一个三角形小花坛。现在工匠们想把它分割成两个三角形的花坛，使之可以种上不同的花。 这时我想到了数学课本中的探究活动中，有着类似的图形题。题中欲要将一个三角形，分割成两个等腰三角形。如图： (1) 原三角形有一个角是另一个角的3倍； (2) 原三角形有一个角是另一个角的3倍； (3) 原三角形是一个直角三角形。 一、直角三角形是否可分割？ 因为直角三角形斜边上的中线等于斜边的一半，所以直角三 角形斜边上的中线一定分这个直角三角形为两个等腰三角 形。 已知：在直角三角形ABC中, ∠C=90，问：△ABC一定能够被分割成两个等腰三角形吗? 结论1：直角三角形是可分割的。直角三角形斜边上的中线 为分割线。一般直角三角形的直角顶点只有这样一种分法。 特别地，如果直角三角形中有一个锐角为22.5°（或有一个 锐角为67.5°），则还有另外一种分法如图： 二、一般三角形是否可分割？ 我们先讨论如果经过三角形的一个顶点把一个三角形分成两 个等腰三角形时，三角形中的角之间存在怎样的关系。三角 形的和为180°，设其中一角未知，根据角的倍数关系可以 得出 1. 设角倍数为2倍 设角B为a°，角C为2a°，则第三个角为（180-3a）°。 则180-3a大于0，得a°小于60°。 分割角C时不难发现，若a大于45°，三角形无法以两倍角的方式分割 所以，a>45°时，此题无解 若a大于45°，则如图分割角A,得角BAP等于a，根据三角形外角等于不相邻两内角之和，则角APC等于2a 所以，a小于45°时，此题有解，分割第三角。 2.设角倍数为3倍 设角A为a°，角B为3a°，则第三个角为（180-4a）° 平面域三角形网格的自动剖分 倪培桐,江 洧 (广东省水利水电科学研究所,广东 广州 510610) 摘 要:利用前沿生成法生成平面计算区域的三角形单元,提出了最小角最长边原则,并用该方法生成的三角形单元网格运用到思贤 水流数学模型计算中,取得良好的效果。 关键词:平面域;三角形网格;剖分;最小角最长边 中图分类号:T V 131.2 文献标识码:A 文章编号:1001-9235(2001)02-0010-03收稿日期:2000-07-28; 修回日期:2000-08-30 作者简介:倪培桐(1971—),男,山东泰安人,助理工程师,硕士,研究方向为河口动力学,目前从事水利水电工程数值模拟工作。 1 前言 求解具有复杂几何形状的流场时,网格的选取和生成是十分困难的问题。要做到边界适应性好,符合该密的区域网格密,该疏的区域网格疏等要求,有限元法是较为理想的计算网格模式。在有限元计算中,网格的生成往往需要较大的工作量,是数值计算分析工作的“瓶颈”。鉴于此,自动生成技术成为目前计算流体力学有限元方法数值计算前处理的研究热点。 三角形单元的自动生成是有限元计算前处理的重要步骤,基于散点三角形自动生成已经比较成熟。对于任意平面域而言,前沿生成法在具有复杂边界的平面域三角形网格自动剖分过程中有较大的实用价值,该方法不需要事先在计算域内布置好内部节点。2 前沿生成法 前沿生成法和Delaunay 方法是目前最为流行的三角形自动剖分方法。其原理是将区域边界点划分为变化均匀的外围三角形的边,然后以这些边为三角形的始边向内生成近似的正三角形,同时形成新的区域边界。重复上述步骤即可得到正三角形。刘春太等提出,对离散的区域边界按最长边算法中,优先考虑最长边。本文经试验发现当区域相邻两边长度差别较大时,优先考虑最长边容易导致生成钝角三角形,而流体力学数值计算要求三角形尽可能接近正三角形,因此本文优先考虑最小角,提出最小角最长边原则,即对复杂区域而言,优先在最小角的最长边开始生成三角形。具体实施步骤如下: (1)首先确定区域边界离散的均匀变化的线段,线段的长度视数值模型计算要求而定。 (2)三角形节点生成、单元生成算法: a )计算离散后的封闭区域的有向边,由小到大排列为 前沿队列。该队列变量包含的信息为:边序号、边始点坐标、终点坐标、边前点、边后点。以A 1A 2为例前沿队列存储信息分别为:A 1A 2的序号、A 1A 2边的始点A 1、A 1A 2边的终点A 2、A 1A 2边的前点A 3、A 1A 2边的后点A 4,如图1所示 。 图1 前沿队列存储变量示意图 b )用前沿队列信息计算出封闭区域的最小内角,该内角的有向最长边AB 为优先生成三角形的边。 c )从现有边界离散点中寻找与AB 形成有效三角形的前沿节点C 记入候选点表(约束条件为:C 位于AB 的左侧邻域,半径R <3 AB ;C 与AB 不共线;CA 、CB 与除AB 外的边不相交、不共线,或C 对AB 可见)。 d )取出所有当前候选点表中顶角值最大的点C ,若AB 为三角形的最长边,那么三角形ABC 作为候选三角形,记入候选三角形队列。执行f )步骤。 e )在区域内部生成新的节点D ,初步确定D 的位置为等边三角形ABD 的顶点,调整D 到AB 的距离h ,重新确定D 点的坐标。 h =0.3a 当p <0.3a (1) h =0.3+0.566/0.7(p /a -0.3) 当0.3a ≤p 回专题模式 回学习阶段模式 【题目名称、来源】 凸多边形三角剖分数 【问题描述】 在一个凸多边形中，通过若干条互不相交的对角线，可以把多边形剖分成若干个三角形。现在的任务是输入凸多边形的边数N ，求不同的剖分方案数Sn 。例如 当n ＝7时，下面两个图就是两种不同的剖分方案。 输入： n 输出： 总剖分数 【所属专题】 递推，递归 【适合学习阶段】 第二阶段 【解题思路】 问题分析： 首先，根据凸多边形的特征可知，凸n 边形可以有n －3条互不相交的对角线，将多边形划分为n －2个三角形。 其次，假设Sn 表示凸n 边形的所有三角剖分数，可以看出从V0～V1这条边可以和其他n －2个点任意一个组成一个三角形，假设和k 点组成三角形V0～V1～Vk ，那么这个三角形将多边形分成了三个部分：多边形V1～V2…～Vk ，三角形V0～V1～Vk ，多边形Vk ～Vk ＋1…～V0。第一个多边形有k 个顶点，划分数为Sk ；第二个多边形有n －k ＋1个顶点，划分数为Sn －k ＋1。根据乘法原理确定V0～V1～Vk 这个三角形后，凸多边形的划分数为Sk ×Sn －k ＋1。又因为k 可以从2～n －1，所以根据加法原理， 凸多边形最优三角剖分 在一个凸多边形中，通过若干条互不相交的对角线，可以把多边形剖分成若干个三角形。现在的任务是输入凸多边形的边数N ，和n 个点的平面坐标(x,y)，求一种剖分方案，使所有对角线长度之和最小。例如 当n ＝7时，下面两个图就是两种不同的剖分方案。 ∑-====+-=1 22 )4(1)3(1)2(),1(*)()(n k S S S k n S K S n S 其中 三角形的分割（二） 同学们大家好！在上一讲中，我们一起研究了“三角形的分割”的一些知识。其中有一条很重要的知识“等底等高的三角形面积相等”。今天我们这一讲一起来研究这些知识的应用。 【典型例题】 一. 阅读思考： 例1. 如图，点D 、E 、F 与点G 、H 、N 分别是三角形ABC 与三角形DEF 各边的中点。那么阴影部分的三角形面积的和是三角形ABC 的面积的()() 。（十一届迎春杯决赛题） B E C 分析与解答：因为D 、E 、F 分别为AB 、BC 、AC 的中点，所以DE 、EF 、DF 分别平行于AC 、AB 、BC ，所以??BDE EFC 和是等底等高的三角形，??A EFC DE 和，??BDE DEF 和分别是等底等高的三角形。 解：S S DEF ABC ??=14 S S S S S S S GHN DEF ABC DEF GHN ABC ??????= =∴=-=12116316 阴 即S S ABC 阴 ?=316 例2. 下图中，三角形ABC 的面积是12平方厘米。并且BE=2EC ，F 是CD 的中点。那么阴影部分的面积是（ ）平方厘米。（第十二届迎春杯训练题） B 分析与解答：因为??ACE ABE 和的高相等，而BE=2EC ，所以?ABE 的面积是?ACE 面积的2倍。 解：S ABE ?=8（平方厘米） S A C E ?=4（平方厘米） 又因为S S S S ACF ADF BCF BDF ????==, 所以S S S ACF BCF ABC ???+==12 6（平方厘米） 于是S S S S BEF ACF BCF ACE ????=+-() =-=64 2()平方厘米 又S S CEF BEF ??==?=12212 1（平方厘米） 所以S S S S BDF BCF BEF CEF ????==+=+=213（平方厘米） S S S B D F BEF 阴影=+=+=??325（平方厘米） 【模拟试题】（答题时间：30分钟） 二. 尝试练习： 三角形的分割（一） 同学们大家好！三角形的面积的计算方法大家已经知道了，今天我再告诉大家一个规律：等底等高的三角形面积相等。这是一个非常重要的规律，在解决多边形面积的许多问题中都要用到它。 今天，我们就一起来研究应用这一规律可以解决哪些问题。 【典型例题】 一. 阅读思考： 例1. 有一个三角形花坛，想把它平均分成两个相等的三角形，可以怎样分？ 分析与解答：因为“等底等高的三角形面积相等”，所以要把这个三角形花坛平均分成两个相等的三角形，就是把这个三角形花坛分成两个等底等高的三角形就可以了。而三角形的每条边都可以作三角形的底，所以我们只要把这三条边分别二等分，再把中点与这条边相对的顶点连接起来就可以了。 例2. 将任一三角形分成面积相等的六个三角形，应怎么分？ 分析与解：根据等底等高的三角形面积相等这一结论，只要把原三角形分成六个等底等高的小三角形，它们的面积就必然相等。而要找这六个等底等高的小三角形，只需把三角形的某一边六等分，再将各分点与这边相对的顶点连结起来即可。如图（1） 图（1） 又因为6163223=?=?=?，所以，如果我们把每一个小三角形的面积看成1，即16? 而32?可以看成是先把原三角形等分两份，再把每一份分别等分成三份。 C C 图（2） 同理，23?可以看成是先把原三角形等分成三份，然后再把每一份等分成两份。 即 A A A B C 图（3） 类似于这样的分法，我们还可以画出许多，这里就不一一列举了。 这两道例题有一个共同的思路，就是想办法找出等底等高的三角形，而找这种三角形，就要几等分某一条线段。 如果两个三角形的底相等，高不相等，它们的面积有什么关系呢？ 如果两个三角形底的长度相等，高的长度不相等，那么它们的面积之比正好等于这两个三角形高的长度比。 同样的道理，我们还可以推出，如果两个三角形高的长度相等，底的长度不相等，那么这两个三角形的面积之比正好等于它们的底的长度比，因此我们有下面的结论： 如果甲、乙两个三角形的底（高）的长度相等，那么甲、乙两个三角形的面积之比等于它们的高（底）的长度之比。 例3. 把三角形ABC分成甲、乙、丙三部分，使甲的面积是乙的面积的3倍，丙的面积是乙的面积的4倍。 分析与解：要想使三角形甲的面积是三角形乙的面积的3倍，可以使这两个三角形的高相同，而三角形甲的底是三角形乙的底的3倍，同样使三角形丙的高和三角形乙的高相同，而三角形丙的底是三角形乙 的底的4倍，这样一来，我们将三角形ABC的一条边8等分，使乙占其中的一份，甲占其中的 3份，丙 占其中的4份，即可达到目的。 B C 例4. 三角形ABC中，DC=2BD，CE=3AE，阴影部分的面积是20平方厘米，求三角形ABC的面积。（如图） B D C 网格划分基本实用技巧——圆和椭圆 ————————————————————————————————作者：————————————————————————————————日期： 基本技巧（圆或者椭圆的画法）：三角形拓扑和钱币原理的比较 画法, 钱币, 三角形, 椭圆, 拓扑画法, 钱币, 三角形, 椭圆, 拓扑 先上图，拓扑关系如图所表示。 第一图是三角形（或者扇形）画法，第二种是钱币原理。 于我个人来说，前者略快一点，前者需要MESHSTLY进行控制，从而内部 方形的大小可以控制，而钱币权利分面略慢，而且控制方形的大小的选择 也不那么方便---拓扑分开了就不能自由选择了。 我个人是基本上才用前者。不知道大家的喜好是什么。 提供给初学者作为一个最基础的练习吧，因为我看到很多人，包括一些周围的人，工作也2年3年了，连画一个标准面都乱七八糟。 1 评分次数 lzkhnu 本主题由 lzkhnu 于 2010-12-2 08:52 分类 收藏分享评分 回复引用 订阅报告道 具 TOP lionkingsimba 1级会员 帖子 80 积分 仿真币 -72 阅读权限 5 2# 发表于2010-11-11 20:44| 只看该 作者 版主可否详细介 绍一下两种的画 法 三角画法如何使 用meshstly控制？钱币原理如何控制方形大小？多大控制的 网格会比较好？ 版主分享一下经 验 俺是菜鸟，有时用钱币原理画的网 格质量还是不太 好 忘赐教 回复引用 报告道具 TOP chengang2001ren 3# 发表于 2010-11-11 20:49 | 只看该作者 我一般用后者，是比较慢一点 奥数专题——三角形的分割（一） 同学们大家好！三角形的面积的计算方法大家已经知道了，今天我再告诉大家一个规律：等底等高的三角形面积相等。这是一个非常重要的规律，在解决多边形面积的许多问题中都要用到它。 今天，我们就一起来研究应用这一规律可以解决哪些问题。 【典型例题】 一. 阅读思考： 例1. 有一个三角形花坛，想把它平均分成两个相等的三角形，可以怎样分？ 分析与解答：因为“等底等高的三角形面积相等”，所以要把这个三角形花坛平均分成两个相等的三角形，就是把这个三角形花坛分成两个等底等高的三角形就可以了。而三角形的每条边都可以作三角形的底，所以我们只要把这三条边分别二等分，再把中点与这条边相对的顶点连接起来就可以了。 例2. 将任一三角形分成面积相等的六个三角形，应怎么分？ 分析与解：根据等底等高的三角形面积相等这一结论，只要把原三角形分成六个等底等高的小三角形，它们的面积就必然相等。而要找这六个等底等高的小三角形，只需把三角形的某一边六等分，再将各分点与这边相对的顶点连结起来即可。如图（1） 图（1） =?=?=?，所以，如果我们把每一个小三角形的面积看成1，又因为6163223 ? 即16 ?可以看成是先把原三角形等分两份，再把每一份分别等分成三份。 而32 C C 图（2） 可以看成是先把原三角形等分成三份，然后再把每一份等分成两份。 同理，23 即 A A A B C 图（3） 类似于这样的分法，我们还可以画出许多，这里就不一一列举了。 这两道例题有一个共同的思路，就是想办法找出等底等高的三角形，而找这种三角形，就要几等分某一条线段。 如果两个三角形的底相等，高不相等，它们的面积有什么关系呢？ 如果两个三角形底的长度相等，高的长度不相等，那么它们的面积之比正好等于这两个三角形高的长度比。 同样的道理，我们还可以推出，如果两个三角形高的长度相等，底的长度不相等，那么这两个三角形的面积之比正好等于它们的底的长度比，因此我们有下面的结论：如果甲、乙两个三角形的底（高）的长度相等，那么甲、乙两个三角形的面积之比等于它们的高（底）的长度之比。 例3. 把三角形ABC分成甲、乙、丙三部分，使甲的面积是乙的面积的3倍，丙的面积是乙的面积的4倍。 分析与解：要想使三角形甲的面积是三角形乙的面积的3倍，可以使这两个三角形的高相同，而三角形甲的底是三角形乙的底的3倍，同样使三角形丙的高和三角形乙的高相同，而三角形丙的底是三角形乙的底的4倍，这样一来，我们将三角形ABC的一条边8等分，使乙占其中的一份，甲占其中的3份，丙占其中的4份，即可达到目的。 有限元网格生成方法正在发展。要将众多研究者所用的纷繁的方法加以适当的分类，或将某一种具体方法准确地归入某一类，并不是一件容易的事。本节从两个不同的角度对网格生成方法进行分类。 自动与半自动网格生成方法的综合分类 二维网格生成方法先于三维网格生成而发展。一些三维网格生成方法是二维方法的直接推广或受到二维方法的启发。若将自动或半自动的网格生成方法综合起来，大体上可分成七种类型： 1.网格平整法(Mesh Smoothing Approach) 这一方法用来平整、改进已经生成的质量不好的初始网格，所采用的手段是拉普拉斯平整和参数平整。 2.拓扑分解法(Topology Decomposition Approach) 将被剖分实体原本具有的顶点取为仅有的节点，然后将节点连成三角形（或四边形）单元，形成数量最少的三角形集合，这样形成的单元形状主要由被剖分实体的几何形状决定。由于实体的复杂拓扑结构被分解成简单的三角形拓扑结构，因而这种方法称为拓扑分解法。这样生成的网格只能是初始网格，必须采用网格细化技术改进网格质量。 3.节点连接法(Node Connection Approach) 节点连接法研究在已知节点分布的情况下如何将这些节点连接起来，以构成在给定条件下形状最好的单元集合。 4.基于栅格的方法(Grid-Based Approach) 这一方法利用一种栅格模板来生成网格，最初用于二维网格生成。栅格模板是一种无限延伸的矩形或三角形网格。将栅格模板重叠在被剖分的二维形体上，将落在形体外面的网格线移去，并对与物体边界相交的网格进行调整，以适合于物体的外形，这样做能够保证产生内部单元质量很好的网格。这一方法已经推广到三维网格剖分。 图X07 单元映射法 a)将物体分割成宏单元b) 网格模板映射到每个宏单元c) 构成最后的网格 5.单元映射法(Mapped Element Approach)算法分析与设计》期末考试复习题纲(完整版)
小学奥数-三角形的分割(一)
算法设计与分析试题(三合一).(优选)
凸多边形最优三角剖分
三角剖分
北邮-算法设计和分析-第三章实验报告
网格中的三角形
凸多边形的最优三角剖分
Ansys ICEM 二维三角形结构化网格-Y Block
凸多边形三角划分
任意形状的三角形网格划分
三角形分割成等腰三角形的条件和分法-精选.
平面域三角形网格的自动剖分_倪培桐
凸多边形的所有三角剖分数
三角形的分割(二)含答案-
小学奥数 三角形的分割(一)
网格划分基本实用技巧——圆和椭圆
奥数专题——三角形的分割(一)-
网格划分方法笔记