国内python 做的网站,网站建站流程图,备案号查询平台官网,阿里巴巴运营课程目录 一、分而治之算法二、三角网生长算法三、逐点插入算法四、约束Delaunay三角网1、方法一1、原始点云2、构网结果 1、方法二1、原始点云2、普通Delaunay3、约束Delaunay Delaunay三角剖分分为直接三角剖分和间接三角剖分。间接三角剖分首先计算为Voronoi图,然后由Voronoi图产… 目录 一、分而治之算法二、三角网生长算法三、逐点插入算法四、约束Delaunay三角网1、方法一1、原始点云2、构网结果 1、方法二1、原始点云2、普通Delaunay3、约束Delaunay Delaunay三角剖分分为直接三角剖分和间接三角剖分。间接三角剖分首先计算为Voronoi图,然后由Voronoi图产生Delaunay三角网。这种方法的算法复杂、内存开销大、效率低,现今很少使用。直接Delaunay三角剖分是利用离散点按照空外接圆或者最大最小内角性质,直接生成Delaunay三角网,是目前基于离散点三角剖分的主流算法。 Delaunay三角剖分分成三类分而治之算法、三角网增长算法和逐点插入算法。 一、分而治之算法 分而治之算法最早是1975年由Shamos和Hoey提出的Lewis和Rovinson在1978年利用该方法进行了三角网的剖分随后Lee和Schachter、Dwyer等对他们的算法进行了改进和优化。 分而治之算法的思路是将复杂问题简单化首先将数据点分割成包含少量点的子集如一个子集中包括三个、四个点然后每个子集进行三角剖分并用局部优化算法LOP进行优化保证三角剖分为Delaunay三角网最后是对每个子集的三角剖分进行合并形成最终的整体三角网。不同的实现方法可有不同的点集划分方法、子网生成方法及合并方法。Lee和Schachter提出了分而治之的经典算法其基本步骤如下
把点集 V V V以横坐标为主纵坐标为辅按升序排序即数据点之间满足条件 ( x i , y i ) ( x i 1 , y i 1 ) (x_i,y_i)(x_{i1},y_{i1}) (xi,yi)(xi1,yi1)把点集 V V V分为近似相等的两个子集 V L V_L VL和 V R V_R VR在 V L V_L VL和 V R V_R VR中生成三角网使用局部优化算法使之成为Delaunay三角网找出连接 V L V_L VL和 V R V_R VR中两个凸壳的底线和顶线由底线至顶线合并 V L V_L VL和 V R V_R VR中两个三角网结束。 该算法的时间复杂度为 ( N l o g N ) (NlogN) (NlogN)其中 N N N为数据点数因此该算法执行时间效率高但在 V L V_L VL和 V R V_R VR中生成三角网时采用了递归运算需占用较大的系统内存。
二、三角网生长算法 三角网生长算法最早由Green和Sibson在V图中实现稍后Brassel和Teif也发表了类似的算法。分为收缩生长算法和扩张生长算法收缩生长算法是先生成凸壳并以凸壳为源头逐步缩小以形成整个三角网。收缩生长算法与数据点的分布密度有关实际情况比较复杂。扩张生成算法与收缩算法过程刚好相反算法是从一个三角形开始向外层扩展,最终形成覆盖整个区域的三角网是常用的三角网生长算法。 扩张生长算法的思想是先找出点集中最近两点连接成一条边按照Delaunay三角网构成原则找出第三点将这三点连接成初始三角形再以该三角形的每一条边为基线扩展连接相邻离散点组成新三角形初始三角形的三边处理之后继续以新三角形的边连接其他离散点直到所有的离散点均包含在三角网中。该算法的基本步骤
在区域内所有离散点任取一点作为初始三角形的第一个顶点找距离第一个顶点最近的点作为初始三角形的第二个顶点两点相连生成初始基线找出距离初始基线中点最近且不和已有两点在一条直线上的点作为初始三角形的第三个顶点三点连接成三角形即为初始三角形三角形的两条新边作为新的基线重复步骤3、4直到所有基线处理完毕。 该算法的时间复杂度在一般情况下为 O ( N 3 / 2 ) O(N^{3/2}) O(N3/2),最坏情况下达到 O ( N 2 ) O(N^2) O(N2)。因此该算法的时间效率低,优点是占用内存空间较小。在该算法的基础上有许多的改进算法,其改进点主要集中在“第三点”的搜索和三角形重复的判断上。
三、逐点插入算法 逐点插入算法的思想最早由Lawson1977提出随后Lee和Schachter1980、Bowyer1981、Watson1981、Tsai1993等先后对其进行改进是一种动态的构网方式。 逐点插入算法的思路是将未处理的点加入到己经存在的Delaunay三角网中然后判断点所在的三角形如果点在三角形内连接点与三角形的各顶点利用三角剖分准则找出影响区域删除影响区域中的边对影响区域利用三角剖分准则重新构网直到区域中所有的点都加入到三角网中。该算法的基本步骤如下
首先定义一个包含所有数据点的初始多边形即包含所有数据点的凸闭包在凸闭包中构建初始Delaunay三角网从内部数据点中取出一点加入到三角网中搜寻包含该点的三角形将该点与此三角形的三个顶点相连形成三个三角形利用Delaunay三角网的剖分准则找出影响区域从里到外更新所有生成的三角形重复步骤3、4、5直到处理完点集中所有点。 该算法一般情况下时间复杂度为 O ( N 3 / 2 ) O(N^{3/2}) O(N3/2)最坏情况下达到 O ( N 2 ) O(N^2) O(N2)。该算法的时间效率低优点是算法思路较简单占用内存空间较小空间性能较好。 通常,分而治之算法的效率是最高的但是当数据量比较大分块比较多时块之间的合并算法复杂且花时也多并且递归执行内存消耗大三角网生长算法和逐点插入法的执行效率差不多但是在构网的过程中逐点插入法能保持较好的空间特性。
四、约束Delaunay三角网
1、方法一
1、原始点云 2、构网结果 1、方法二
1、原始点云 2、普通Delaunay 3、约束Delaunay
