10号文献收获总结.docx

  1. 1、本文档共11页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
Delaunay三角剖分Voronoi图定义2.计算Delaunay三角剖分的算法及分析3.例子程序代码大话点集的三角剖分(Triangulation),对数值分析(比如有限元分析)以及图形学来说,都是极为重要的一项预处理技术。尤其是Delaunay三角剖分,由于其独特性,关于点集的很多种几何图都和Delaunay三角剖分相关,如Voronoi图,EMST树,Gabriel图等。Delaunay三角剖分有几个很好的特性:1.最大化最小角,“最接近于规则化的“的三角网。2.唯一性(任意四点不能共圆)。概念及定义二维实数域(二维平面)上的三角剖分定义1:假设V是二维实数域上的有限点集,边e是由点集中的点作为端点构成的封闭线段, E为e的集合。那么该点集V的一个三角剖分T=(V,E)是一个平面图G,该平面图满足条件:1.除了端点,平面图中的边不包含点集中的任何点。2.没有相交边。3.平面图中所有的面都是三角面,且所有三角面的合集就是点集V的凸包。那什么是Delaunay三角剖分呢?不过是一种特殊的三角剖分罢了。从Delaunay边说起。Delaunay边定义2:假设E中的一条边e(两个端点为a,b),e若满足下列条件,则称之为Delaunay边:存在一个圆经过a,b两点,圆内不含点集V中任何的点,这一特性又称空圆特性。Delaunay三角剖分定义3:如果点集V的一个三角剖分T只包含Delaunay边,那么该三角剖分称为Delaunay三角剖分。我们看几个图:由上面的图引出Delaunay三角剖分的另一种定义:定义4:假设T为V的任一三角剖分,则T是V的一个Delaunay三角剖分,当前仅当T中的每个三角形的外接圆的内部不包含V中任何的点。?Voronoi图定义5:V的Voronoi图是由多边形区域的集合(有些区域可能不是闭合的),该区域仅含点集中的一个点v,区域中的任何位置到v的距离都比该位置到点集中其它所有点的距离短。由Voronoi图和Delaunay三角剖分的关系,可以引出另一个Delaunay三角剖分的定义:定义6:将Voronoi图相邻区域(共边的区域)中的点连接起来构成的图,称为Delaunay三角剖分。如下图:概念部分到此,下面看看怎么求Delaunay三角剖分。计算Delaunay三角剖分问题1:计算二维Delaunay三角剖分问题输入:二维实数域上的点集V问题输出:Delaunay三角剖分DT = (V, E).算法由不同的定义对应有不同的算法。用得较多的是基于定义3或4的算法。目前常用的算法又分为好几种,被不同的家伙发现。什么扫描线法(Sweepline),随机增量法(Incremental),分治法(Divide and Conquer)啊等等。随机增量法(Incremental)其中,随机增量法较为简单,遵循增量法的一贯思路,即按照随机的顺序依次插入点集中的点,在整个过程中都要维护并更新一个与当前点集对应的Delaunay三角剖分。考虑插入vi点的情况,由于前面插入所有的点v1,v2,...,vi-1构成的DT(v1,v2,...,vi-1)已经是Delaunay三角剖分,只需要考虑插入vi点后引起的变化,并作调整使得DT(v1,v2,...,vi-1) U vi成为新的Delaunay三角剖分DT(v1,v2,...,vi)。(插入调整过程:首先确定vi落在哪个三角形中(或边上),然后将vi与三角形三个顶点连接起来构成三个三角形(或与共边的两个三角形的对顶点连接起来构成四个三角形),由于新生成的边以及原来的边可能不是或不再是Delaunay边,故进行边翻转来调整使之都成为Delaunay边,从而得出DT(v1,v2,...,vi)。)其Pseudocode如下:Algorithm IncrementalDelaunay(V)Input: 由n个点组成的二维点集VOutput: Delaunay三角剖分DT1.add a appropriate triangle boudingbox to contain V ( such as: we can use triangle abc, a=(0, 3M), b=(-3M,-3M), c=(3M, 0), M=Max({|x1|,|x2|,|x3|,...} U {|y1|,|y2|,|y3|,...}))2.initialize DT(a,b,c) as triangle abc3.for i - 1 to n? do (Insert(DT(a,b,c,v1,v2,...,vi-1), vi))???4.remove the boundingbox and relative triangle which cotains any vertex of triangle

文档评论(0)

5500046 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档