生成三角网格的三种基本方法 TT整理.doc

生成三角网格的三种基本方法_TT整理Forpersonaluseonlyinstudyandresearch;mercialuse分治算法 Shamos和Hoey提出了分治算法思想[10],并给出了一个生成V-图的分治算法。Lewis和Robinson将分治算法思想应用于生成D-三角网[11]。他们给出了一个“问题简化”算法,递归地分割点集,直至子集中只包含三个点而形成三角形,然后自下而上地逐级合并生成最终的三角网。逐点插入法 Lawson提出了用逐点插入法建立D-三角网的算法思想[11]。逐点插入算法的基本步骤是: 定义一个包含所有数据点的初始多边形;在初始多边形中建立初始三角网,然后迭代以下步骤,直至所有数据点都被处理:插入一个数据点P,在三角网中找出包含P的三角形t,把P与t的三个顶点相连,生成三个新的三角形;三角网生长法三角网生长算法的基本步骤是: 以任一点为起始点; 找出与起始点最近的数据点相互连接形成D-三角形的一条边作为基线,按D-三角网的判别法则,即它的两个基本性质找出与基线构成D-三角形的第三点:任何一个Delaunay三角形的外接圆的内部不能包含其他任何点[Delaunay1934]。最大化最小角原则:每两个相邻的三角形构成凸四边形的对角线,在相互交换后,六个内角的最小角不再增大。基线的两个端点与第三点相连,成为新的基线;迭代以上两步直至所有基线都被处理。上述过程表明,三角网生长算法的思路是,先找出点集中相距最短的两点连接成为一条Delaunay边,然后按D-三角网的判别法则找出包含此边的D-三角形的另一端点,依次处理所有新生成的边,直至最终完成。以下无正文仅供个人用于学****研究;不得用于商业用途。 толькодлялюдей,которыеиспользуютсядляобучения,исследованийинедолжныиспользоватьсявкоммерческихцелях. Forpersonaluseonlyinstudyandresearch;ürdenpersönlichenfürStudien,Forschung,'étudeetlarechercheuniquementàdesfinspersonnell