资源描述：
《平面离散点集的边界搜索算法_陈涛》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第21卷第3期计算机仿真2004年3月文章编号:1006-9348(2004)03-0021-03平面离散点集的边界搜索算法陈涛,李光耀(湖南大学机械与汽车工程学院,湖南长沙410082)摘要:进行有限元仿真首先要建立有限元网格模型。使用不含有任何拓扑信息的离散点集直接进行网格划分可以快速、精确地建立网格模型。使用铺路法进行网格剖分是从边界开始向内生成网格单元。该文提出一种使用搜索盒的搜索平面离散点集边界的算法。该方法将离散点分配到搜索盒中,遍历位于边界的搜索盒,将其中的点连接成边界点链表。该算法能正确地搜索包含有凹点、孔洞特征的离散点集的边界,具有较强的通用性。文
2、中介绍了算法的基本思想,并给出算例。关键词:离散点集;边界搜索;搜索盒中图分类号:TP391.72文献标识码:A1引言2平面离散点集边界搜索算法概述有限元方法(FEM)是在工程领域广泛应用的数值分析本文提出一种使用搜索盒(SearchingBox)的边界搜索算方法,有限元方法要求对求解域进行离散化处理。传统的作法。由于搜索盒的大小对算法的正确性和效率有非常大的法是,先在CAD系统,如Unigraphics,Pro/E等生成CAD模型,影响,因此首先使用一个经验公式得出一个粗略的搜索盒尺然后传送给有限元建模软件,如Ansys,Hypermesh等生成有限寸。由此进行第
3、一次搜索,得到的结果再用来精确地调整搜元模型。但是通常要对数据进行修复,同时CAD模型往往包索盒的尺寸。搜索过程中,将离散点都放入到搜索盒中,如含许多有限元建模不需要的细节,如细小的尖面、小面、狭长果某个非空的搜索盒周围出现了空的搜索盒,那么就认为这[1]面等。成艾国提出了使用数控轨迹点来直接生成全四边个搜索盒是一个边界搜索盒。找到所有的边界搜索盒,而后形网格,可以避免烦杂的数据修复和细小特征消除。作者使从某一个边界搜索盒开始,搜寻出封闭的边界。最后,完善[2]用铺路法对离散点进行四边形化。铺路法是许多现有的算法以便能够处理凹点集和孔洞。商业有限元前处理软件上使用的
4、四边形网格划分方法。铺搜索盒使用C++中的类来定义。主要的数据成员包路法具有生成网格质量高、边界单元形态好等优点。即给定括:搜索盒位于边界的标志位(b-OnBound)、空盒的标志位(b-n空间的离散点集S={Pi}i=1,使用铺路法的思想对点集进行Empty)、是否已搜索的标志位(b-Searched)、优先级标志(I-Pri2直接的四边形网格划分。算法是从封闭的边界节点开始,向ority)以及保存内部离散点的点链表(PtList)。搜索盒用二维区域内部生成四边形网格,直到把整个区域填满。因此,正的数组BoxVector存储,便于对相邻搜索盒的查询。搜索到的确地从
5、离散点集搜索出封闭的边界点链是后面进行有限元边界节点保存在链表PtList中。网格划分的前提和基础。为了拓宽算法的适用性,不仅要能够正确处理凸点集,还要能处理凹点集,以及原始曲面包含3搜索盒大小的确定有孔洞特征的点集。当搜索盒的尺寸太小的时候,构造平面点集的凸壳(凸集)已经有相当成熟的算法,如在内部会出现“假的”空盒,如图1[3]著名的格雷汉姆方法,但都只能求出点集边缘的凸点。在中间的空盒。同样,图2中搜索盒图象处理领域也提出了许多边界提取方法,通常采用的方法的尺寸过大,在盒中有多个点,在[4][5]包括:局部算子法。朱汗华的论文中对平面的离散测量连接边界盒内的节点
6、构成边界时,图1搜索盒划分过小点首先进行三角化,得到平面点集的三角形网格,而后用网会产生锯齿现象。当非空的搜索的情况格的边界作为离散点的边界。本文提出新的搜索算法适应盒中包含的离散点的平均值为1性强,能够搜索出平面的凹、凸点集和包含空洞特征的点集或者接近1的时候,就可以在很大边界,算法效率高。程度上避免上述两种情况的出现。在实际的算法中,搜索盒的大小是通过计算离散点集内点的平图2搜索盒划分过大基金项目:国家自然科学基金(50075025);高等学校博士点基金均点距daver得到的。在Liu(2003)的情况(20020532021);教育部优秀青年教师资助计划(教人
7、司中给出了二维情况下的平均点距[2002]350号)收稿日期:2003-07-04的近似公式(1)。通常点的数量可以准确的知—21—A盒定义为低优先级的边界搜索盒。第二次遍历搜索盒,寻找daver=(1)n-1并纪录高、低优先级的边界搜索盒的数量Ncell1、Ncell2。4.2边界搜索道,但因为点集的边界没有确定,面积难以计算。从任意的一个边界搜索盒BoxBegin开始,将盒内的点加使用二维数组来存储搜索盒。首先求出点集中x,y坐入到代表边界的离散点链表中。具体的搜索过程是,当某一标的最小值(xmin,ymin)作为搜索盒的参考起点:刻边界搜索盒2,如图4所示
