下载文档原格式
Delaunay三角网剖分注记自动配置算法研究1引言由于人工地图注记配置效率低，因此，有许多学者对计算机注记自动配置算法进行了研究，并且提出了一些非常好的算法。
其中针对面状要素的水平切割中点线法、长对角线法对于狭长多边形、扇形多边形、半环状多边形、等都不能取得较好的效果，甚至无法标注。
但Delaunay 三角网剖分法则可以适应多种多边形，故本文重点描述Delaunay三角网剖分注记自动配置算法。
2 化简面状要素面状要素：原始数据精度高，坐标点多，有些坐标点相距很近甚至重合，所以必须对原始多边形进行预处理，去除冗余数据，只保留特征点，才能很大程度上减少计算量，保证建网效率。
数据压缩的方法有很多，本文选取垂距法对面状元素进行压缩。
垂距法压缩数据的方法已经十分成熟，本文不再赘述。
3 基于最小距离简单多边形的Delaunay三角剖分算法3.1生成初始三角网算法描述（1）建立双链表L1，顺序存入简单多边形的各个结点及其凹凸性。
（2）根据每个结点的凹凸性算出对应的距离。
如果是第1次计算，就全部计算，否则只计算需要计算的结点，并将距离保存在双链表L1 中，其中凹點的距离为无穷大。
（3）在L1中找出最小的距离值及所对应的结点Pi。
建立单链表L2，存储结点Pi的前驱与后继，表示边；建立单链表L，存储结点Pi 及其前驱和后继表示三角形。
删除结点Pi，重新计算L1中与Pi 相关的点Pi+1，Pi-1 的距离及凹凸性，若第一次计算的点Pi+1 或Pi-1 为凸点，则不需计算它的凹凸性，反之则需要计算。
（4）重复（3），再判断L1中的结点数，若结点数<3，结束。
3.2 Delaunay 剖分三角网的算法综上所述，L中纪录了初始三角网的三角形，单链表L2中记录了三角网的边，用L和L2 进行三角网的Delaunay 剖分。
（1）取出L2中Pi 的数据，形成一条边Edge。
（2）在L中遍历找出共用Edge的两个三角形，判断这两个三角所组成的四边形的凹凸性。
收稿日期:2007207227;修改稿收到日期:20082062261基金项目:国家杰出青年科学基金(10125208);国家汽车电子产业化重大专项(No.200422563)联合资助项目1作者简介:郑国君(19812),男,博士生;狄 驰(19792),男,博士生;胡 平(19562),男,教授,博士生导师;郭 威3(19572),男,教授(E 2mail :guowei @ ).第26卷第2期2009年4月 计算力学学报 Chinese Journal of Computational MechanicsVol.26,No.2April 2009文章编号:100724708(2009)022*******改进的栅格法有限元网格剖分郑国君2, 狄 驰3, 胡 平1,2, 郭 威33(1.大连理工大学汽车工程学院工业装备结构分析国家重点实验室,大连116024;2.吉林大学汽车动态模拟国家重点实验室,长春130022;3.吉林大学材料科学与工程学院,长春130022)摘 要:提出一种改进的栅格法网格剖分算法,该算法综合了栅格法和Delaunay 算法的优点,生成了四边形和三角形混合单元,保证了整体性能与局部性态最优,满足汽车覆盖件冲压成形模拟软件对有限元网格质量的需求。
实践证明,本文提出的改进的栅格法网格剖分算法可行有效,生成网格的质量高,程序容易实现。
该算法已经成功集成到商业化冲压成形模拟软件KMAS 中。
关键词:栅格法;有限元;网格剖分;汽车覆盖件;CA E 中图分类号:O242.21 文献标识码:A1 引 言随着CAD/CA E/CAM 技术的日益发展,有限元网格自动剖分技术也受到越来越多的关注,网格剖分的质量直接影响着有限元分析的计算精度和效率,已经成为有限元分析中非常关键的技术之一[1]。
根据曲面的参数信息,可以把三维区域映射成一个平面域,因此平面域内的网格剖分是整个网格剖分的基础。
目前,比较流行的平面网格生成算法有:Delaunay 三角剖分、波前法[2]及栅格法。
任意多介质区域变尺寸有限元网格自动剖分
吴振君;施斌;祁长青
【期刊名称】《工程地质计算机应用》
【年(卷),期】2002(000)004
【摘要】以Bowyer／watson算法为基础，结合Lawson算法等对有限元网格进行Delaunay剖分，引入节点间距函数，在区域内通过布置约束点和边来控制特定位置网格的尺寸，并实现网格的尺寸均匀过渡．采用了多种优化技术对生成的网格进行优化。
对Bowyer／Watson算法和Delaunay剖分的一些缺陷及问题作了探讨，并提出了相应的处理办法。
编写的网格自动剖分软件具有良好。
的可视化界面，其图形生成、显示及修改功能十分完善，极大地提高了有限元网格剖分的效率和准确性.
【总页数】5页(P3-7)
【作者】吴振君;施斌;祁长青
【作者单位】南京大学地球环境计算工程研究所,南京210093
【正文语种】中文
【中图分类】O29
【相关文献】
1.基于二维温度场的平面任意区域三角形网格自动剖分 [J], 汪维安;余钱华;张建仁
2.多介质复杂区域四边形网格自动剖分算法及应用 [J], 付成华;周洪波
3.任意平面区域有限元三角形网格全自动剖分 [J], 潘子杰;杨文通;郭九生
4.任意平面区域的变尺寸有限元网格划分 [J], 刘春太;杨晓东;申长雨;陈静波
5.任意平面区域的高质量有限元网格自动剖分 [J], 李梅娥;周进雄
因版权原因，仅展示原文概要，查看原文内容请购买。
计算机图形学中的平面和实体剖分技术研究计算机图形学中的平面和实体剖分技术在计算机辅助设计、计算机动画、计算机游戏等领域发挥着重要作用。
平面剖分技术可以将复杂模型分解成简单的平面多边形，使得计算机可以更容易地处理和显示。
实体剖分技术则可以将复杂的三维实体分解成简单的几何体素，方便进行求交、拓扑操作等。
本文将对平面和实体剖分技术进行介绍和分析。
一、平面剖分技术1.1 基本概念平面剖分是将一个多边形分解成若干个互不相交的三角形的过程。
平面剖分有很多种方法，最常见的是三角剖分和四边形剖分。
三角剖分是将多边形分解成若干个三角形的过程。
三角剖分的优点是简单高效，计算量小，易于处理。
但三角剖分会产生大量的边界，不利于后续处理。
四边形剖分是将多边形分解成若干个四边形的过程。
四边形剖分的优点是产生的边界少，更适合于经过后续处理的模型。
但是四边形剖分的计算量相对于三角剖分较大，操作复杂度较高。
1.2 平面剖分算法平面剖分算法有很多，其中比较常见的有：Ear Clipping算法、Delaunay分割算法、Greedy算法、Steiner点算法等。
Ear Clipping算法是一种基于三角形的平面剖分算法，通过找出多边形中的耳朵来进行分割。
耳朵就是一个凸多边形的三角形部分，Ear Clipping算法通过不断剪掉耳朵直到无法剪去为止，完成平面剖分。
Delaunay分割算法是一种优化的平面剖分算法，它可以生成具有最小角度的三角剖分。
Delaunay分割算法的基本思想是找出能够覆盖多边形内所有点的最小圆，然后将最小圆内的点连接起来，形成三角形。
这个过程可以类比泡泡排序，先将所有点按照一个顺序连接起来，然后逐渐调整使得三角形的圆心符合Delaunay条件。
Greedy算法是一种启发式算法，它通过不断选择合适的直线来剖分多边形。
Greedy算法的核心思想是：在两个点之间连一条线段，如果这条线段可以截断多边形，就将多边形分割成两个部分，然后通过递归的方式继续进行分割，直到多边形已经无法分割。
第3章网格划分技术及技巧-图文创建几何模型后，必须生成有限元模型才能分析计算，生成有限元模型的方法就是对几何模型进行网格划分，网格划分主要过程包括三个步骤：⑴定义单元属性单元属性包括单元类型、实常数、材料特性、单元坐标系和截面号等。
⑵定义网格控制选项★对几何图素边界划分网格的大小和数目进行设置；★没有固定的网格密度可供参考；★可通过评估结果来评价网格的密度是否合理。
⑶生成网格★执行网格划分，生成有限元模型；★可清除已经生成的网格并重新划分；★局部进行细化。
3.1定义单元属性3.1.1单元类型1.定义单元类型命令：ET,ITYPE,Ename,KOP1,KOP2,KOP3,KOP4,KOP5,KOP6,INOPRITYPE---用户定义的单元类型的参考号。
KOP1~KOP6---单元描述选项，此值在单元库中有明确的定义，可参考单元手册。
也可通过命令KEYOPT进行设置。
INOPR---如果此值为1则不输出该类单元的所有结果。
例如：et,1,link8!定义LINK8单元，其参考号为1；也可用ET,1,8定义et,3,beam4!定义BEAM4单元，其参考号为3；也可用ET,3,4定义2.单元类型的KEYOPT命令：KEYOPT,ITYPE,KNUM,VALUEITYPE---由ET命令定义的单元类型参考号。
KNUM---要定义的KEYOPT顺序号。
VALUE---KEYOPT值。
该命令可在定义单元类型后，分别设置各类单元的KEYOPT参数。
例如：et,1,beam4!定义BEAM4单元的参考号为1et,3,beam189!定义BEAM189单元的参考号为3keyopt,1,2,1!BEAM4单元考虑应力刚度时关闭一致切线刚度矩阵keyopt,3,1,1!考虑BEAM189的第7个自由度，即翘曲自由度!当然这些参数也可在ET命令中一并定义，如上述四条命令与下列两条命令等效：et,1,beam4,,1et,3,beam189,13.自由度集命令：DOF,Lab1,Lab2,Lab3,Lab4,Lab5,Lab6,Lab7,Lab8,Lab9,Lab104.改变单元类型命令：ETCHG,Cnv5.单元类型的删除与列表删除命令：ETDELE,ITYP1,ITYP2,INC列表命令：ETLIST,ITYP1,ITYP2,INC3.1.2实常数1.定义实常数命令：R,NSET,R1,R2,R3,R4,R5,R6续：RMORE,R7,R8,R9,R10,R11,R12NSET---实常数组号（任意），如果与既有组号相同，则覆盖既有组号定义的实常数。
平面有限元网格自动剖分法
刘风秋;李健宗
【期刊名称】《广西电力》
【年(卷),期】2003(26)B10
【摘要】提出了一套新的完整的平面有限元网格自动剖分方法，着重介绍网格自动剖分的基本原理、推导过程、程序设计思路以及其它计算数据的前处理。
【总页数】6页(P20-24,41)
【作者】刘风秋;李健宗
【作者单位】广西电力工业勘察设计院，广西南宁530023
【正文语种】中文
【中图分类】TP311.1
【相关文献】
1.旋转体结构有限元网格自动划分法 [J], 许贤泽
2.平面有限元网格自动剖分法 [J], 刘风秋;李健宗
3.平面有限元网格自动剖分法 [J], 刘凤秋;李健宗
4.有限元网格全自动生成的九分法 [J], 王宗木;王造奇
5.平面有限元网格自动剖分法 [J], 刘风秋;李健宗
因版权原因，仅展示原文概要，查看原文内容请购买。
三角形网格自动生成的一种快速算法
姚磊华
【期刊名称】《煤田地质与勘探》
【年(卷),期】1999(000)001
【摘要】提出了一种三角形网格自动生成的快速算法:从边界点出发逐步向内部联网,不仅联网速度快,而且很容易处理凹边界.
【总页数】3页(P39-41)
【作者】姚磊华
【作者单位】煤炭科学研究总院西安分院,710054
【正文语种】中文
【中图分类】TP31
【相关文献】
1.一种三角形网格自动生成技术 [J], 谷汉斌;李炎保;李焱;戈龙仔
2.一种基于STL几何模型的有限元三角形网格的自动生成方法 [J], 刘静珏;韩利芬;彭爱连;李海波
3.一种三角形网格空洞修复算法 [J], 刘全;杨凯;伏玉琛;张书奎
4.任意平面区域三角形网格的全自动生成算法 [J], 张修忠;金生
5.一种曲边三角形区域中的三角形网格自动生成方法 [J], 张琦跃
因版权原因，仅展示原文概要，查看原文内容请购买。
平面域三角形网格的自动剖分
倪培桐,江 洧
(广东省水利水电科学研究所,广东 广州 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 <a h =[0.866+0.334/2(p /a -1)]a 当a ≤p <3a h =1.2a 当p ≥3a 式中 a ———AB 的长度。
10
人民珠江 PEA RL RIV ER ·2001年第2期
p (x ,y )=
∑N
i =1
p (x i ,y i )/d 2i
∑N
i =1
1/
d 2
i
(2)
式中 N ———边界节点总数;p (x i ,y i )———边界节点的间距
函数;d i ———区域内任意一节点距离。
D 点的约束条件为:D 点位于区域内侧;D 点不能落在已生成的三角形内(由面积判断);D 点与区域内的点重合;D 点落在区域内的边上。
f )从当前候选点表中选出顶角值最大的点C ,将ABC 作为生成三角形。
g )更新前沿队列。
首先从前沿队列中删去有向边AB ,然后判断C 点类型若为当前内部节点表中的点,将有向边AC 、AB 记入前沿队列表中,若C 为前沿上的点,判断AC 、AB 是否与前沿中已有的有向边重合,若重合则需将其从已有队列中删去,若不重合则将AC 、BC 的属性加入队列中去。
h )最后判断前沿队列是否为空,若为空则结束循环,否则继续上述步骤。
由于候选点C 的选择与D 的生成中有许多限制条件,
如共线、左侧邻域、区域内部、点与直线可见等约束条件,这些约束条件多需要用反余弦函数求角度,可以用近似处理以防止数值溢出。
应用最小角最长边原则进行三角形的自动生成,其生成过程实质是由“区域边界”向内层层推进,且优先在最为曲折的边界处生成三角形使“区域边界”不断光滑。
(3)三角形网格的光滑处理
应用前沿生成法产生的三角形不均匀,可选用最小能量法将每个节点的坐标优化处理,能量E =∑N
k =1C k l 2k ,其中l k 为
线段的长度,C k 为弹性系数,可取值为1,N 为总的线段数,令 E / x i =0, E / y i =0得到2N 个线性方程,从而可以重新确定各点的位置,达到优化目的。
其中完整的三角形生成过程见图2所示。
图3是思贤
区域枯水季节思贤
生
成的三角形网格。
图4、5分别是思贤区域水流数值模拟
结果,模拟试验为2000年1月20—21日的枯季水流流态,
计算值与实测值吻合较好。
图2
三角形网格的自动生成过程
图3 思贤三角形网格
11
图4 思贤枯季流态时刻(20日20时
)
图5 思贤
枯季流场(21日01时)
3 结语
本文应用前沿生成法对平面计算域进行了三角形网格的自动生成,在前人研究的基础上提出最小角最长边原则,并利用生成的三角形网格计算了西北江交汇点—思贤枯
季水流流态。
参考文献:
[1]Bowyer A .Computing Dirichlet Tes sell ations [J ].The Computer
Journal ,1981,24(2):162-167.
[2]Los .H .A New M esh Generation scheme for Arbitary Planar Do -mains [J ].Int .J ..for Numerical M eth .In Eng .1985,21:l403-1426.
[3]苏铭德,黄素逸.计算流体力学基础[M ].北京:清华大学出版
社,1997.
[4]刘春太等.任意平面域渐变三角形网格的自动划分[J ].计算机
辅助设计与图形学报,1999,11(4).
[5]朱心雄等.自由曲线曲面造型技术[M ].北京:科学出版社,
2000.
Automatic Triangulation for Planar Domain
NI Pei _tong ,JIANG Wei
(Guangdong S cien tific Res earch Institute of Watar Cons ervancy an d Hydropower ,Guangz hou ,Guangdong ,510610,China )
A bstract :T his paper presents the principle of the least angle and the largest side by using the method of adv ancing front to generate the triangular element for planar domain .T he triargular meshes g enerated have been applied to the numerical mo deling for Six ianjiao and satisfactory results have been achieved .
Key words :planar domain ;triang ular mesh ;triangulation ;the least ang le and the largest side
12。
