【无约束离散点的Delaunay三角网建立案例分析4600字】

数学家M.G.Voronoi于1908年从数学上定义了平面Voronoi图[6],如下：假设P={p₁,P₂,…,Pn.}(n>3)是欧几里德平面上的点p,的Voronoi区域为所有到点p,的距离最小的点的集合V(p)(如图3-1所p={p|d(p,pi)≤d(p,pj),i=1,2,…,n,j=1,2,…,n,图记作Vor(P),它具有很多优良性质，如下：(1)Vor(P)把平面划分为n个区域，每个区域V(p;)只包含一个点pi(2)n个点的点集的Voronoi图最多有2n-5个顶点和3n-6条边；(3)当且仅当p,属于凸包外界的点集时，V(p,)是无界的；(5)每个Voronoi点恰好是三条Voronoi边的交点。由于Voronoi图具备影响范围性、侧向邻近性、空外接圆性以及局域动态性等特性，因此它为研究和发展空间分析与模型提供了主要手段。Voronoi图的生成算法通常有矢量法和栅格法两种，目前Voronoi图的研究对象大多集中在离散Delaunay三角网和Voronoi图间的关系如图3-2所示，Voronoi图用实线表示，1.1.2Delaunay三角网性质(1)唯一性一个点当作起始点，最后构建的Delaunay三角网是唯一存在的，如图3-3所示。图3-3三角剖分图(2)空外接圆性是建立Delaunay三角网的基本准则，如图3-4所示。图3-4空外接圆(3)最大最小内角性角形的最小内角一定比替换对角线后大。Lawson于1977年根据这个特性提出了角线来得到三角网[2],如图3-5所示。(4)局部性1.2经典Delaunay三角网生成算法目前，按照Delaunay三角网构建过程的不同，其主要生成1.2.1三角网生长法三角网生长法的中心思想是：选取任意1点，找出距离该点最近的1点，连接两点形成-条线段作为初始基准线，找出距离该线段最近的1点，构成一个三(1)选取点集内任意1点，找出距离该点最近的点，然后将连接两点的线(2)找出初始基准线右侧距离它们最近的第3个点；(4)重复(2)、(3),依次判断，直到所有离散点都处理完。大多是在寻找第3点上。1.2.2分治算法分治算法构网思想是：首先将离散点分为2个相对独立的点集，然后分别构(1)将数据集V以x坐标为主、y坐标为辅按升序排列；(2)将数据集V分成点数近似相同的两个相对独立子集V,和V;(3)对子集v和V分别构建三角网；(4)局部优化两个子三角网；(6)重复(2)至(5),直到Delaunay三角网完成。时间复杂度最差的情况为O(nlogn),最理想的情况为O(nloglogn),但该方法需1.2.3逐点插入法用LOP优化，最后生成Delaunay三角网(1)建立包括全部离散点的多边形并构建初始三角网；(2)从离散点中选取一点P插入到初始三角网中，把该点和该点所在三角(4)重复(2)、(3),直至插入完所有离散点。图3-6插入点P综上所述，三角网生长法相对简单，效率差，平均时间复况下为O(nlogn),最理想情况下为O(nloglogn):而逐点插入法原理简单，占用内存少，容易完成，但执行效率低，算法平均时间复杂度为O(nlogn),最差情况下1.3逐点插入法的实现很多学者已提出了许多相应的点定位算法。宋占峰等人[提出了方向搜索法，通三角形重心和点的连接线(即方向线)是否与三角形边有交点，验证表明算法效率可提高4倍多；蒲浩等人提出最速方向定位法，若三角形委包含该插入点，则下一个搜索三角形为和三角形重心和插入点的连接线有交点的边毗邻的三角形；分利用了点和三角形的关系，减少了重心计算次数和运算步骤，搜索路径唯一，形内，如图3-7所示。图3-7点位与△ABC关系按逆时针排列，三角形面积为S,任意点P的坐标为P(xp,Yp),点P和△ABC0、小于0或等于0的情况。如果存在三角形矢量面积Si>0、S2>0、S₃>0的情况，则点P处在三角形内；如果存在至少有一个三角形矢量面积小于0的情况，则点P处在三角形外；如果存在三角形矢量面积等于0的情况，则点P处在三角形的边上(不考虑点P与三角形顶点重合的情况)。1.1.3算法步骤角形，最后LOP优化生成Delaunay三角网，实现流程如图3-8所示。NNY图3-8算法流程图1)建立凸壳和初始三角网(2)选取凸壳链表中两个毗邻的点Pi和Pi+1,找出在其右侧距离最大的1点，(3)重复(2),直到每次没有插入点的次数等于链表中顶点的总数，完成凸壳2)改进的点定位算法(2)利用矢量面积公式判定点P与三角形的关系，如果有3个矢量面积全部大于0或有1个矢量面积等于0的情况，那么点P处在该三角形中或者在三角形边上，继续执行步骤5,否则执行步骤3或4;(3)如果有2个矢量面积小于0的情况，那么计算三角形的重心G,下一个搜步骤2;(4)如果有1个矢量面积小于0的情况，那么下一搜索三角形为该边右侧的三角形，继续执行步骤2;△ABC3个顶点是按逆时针方向排列，点和外接圆的关系有三种，分别为点处在外接圆上、点处在外接圆外和点处在外接圆内，如图3-9所示。图3-9点P与外接圆的关系接圆上；当α>α'时，点P