python三角网格代码-三角剖分算法（delaunay）

python三⾓⽹格代码_三⾓剖分算法（delaunay）开篇在做⼀个LowPoly的课题，⽽这种低多边形的成像效果在现在设计中越来越被喜欢，其中的低多边形都是由三⾓形组成的。⽽如何⾃动⽣成这些看起来很特殊的三⾓形，就是本章要讨论的内容。选择其是最先是由很多离散的点组成，基于这个确定的点集，将点集连接成⼀定⼤⼩的三⾓形，且分配要相对合理，才能呈现出漂亮的三⾓化。这时则要求使⽤三⾓剖分算法(Delaunay)，引于【定义】三⾓剖分：假设V是⼆维实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段,E为e的集合。那么该点集V的⼀个三⾓剖分T=(V,E)是⼀个平图G，该平图满⾜条件：1.除了端点，平图中的边不包含点集中的任何点。2.没有相交边。3.平图中所有的⾯都是三⾓⾯，且所有三⾓⾯的合集是散点集V的凸包。在实际中运⽤的最多的三⾓剖分是Delaunay三⾓剖分，它是⼀种特殊的三⾓剖分。先从Delaunay边说起：【定义】Delaunay边：假设E中的⼀条边e(两个端点为a,b)，e若满⾜下列条件，则称之为Delaunay边：存在⼀个圆经过a,b两点，圆内(注意是圆内，圆上最多三点共圆)不含点集V中任何其他的点，这⼀特性⼜称空圆特性。【定义】Delaunay三⾓剖分：如果点集V的⼀个三⾓剖分T只包含Delaunay边，那么该三⾓剖分称为Delaunay三⾓剖分。【定义】假设T为V的任⼀三⾓剖分，则T是V的⼀个Delaunay三⾓剖分，当前仅当T中的每个三⾓形的外接圆的内部不包含V中任何的点。如图，将离散点联结成Delaunay三⾓形算法关于Delaunay三⾓形的算法，有翻边算法、逐点插⼊算法、分割合并算法、Bowyer-Watson算法等。⽽在这⼏种算法中，逐点插⼊算法⽐较简单、易懂，在本⽂中只针对该算法进⾏讨论，该算法也是⽬前使⽤最为⼴泛的Delaunay算法。在该算法中，主要应⽤Delaunay三⾓形【定义4】，理解下来就是每⼀个三⾓形的外接圆圆内不能存在点集内的其它任何⼀点，⽽有时候会出现点在外接圆上的情况，这种情况被称为“退化”。在⽂章⾥对该⽅法进⾏了分析，并提出了伪代码思路：subroutinetriangulateinput:vertexlistoutput:trianglelistinitializethetrianglelistdeterminethesupertriangleaddsupertriangleverticestotheendofthevertexlistaddthesupertriangletothetrianglelistforeachsamplepointinthevertexlistinitializetheedgebufferforeachtrianglecurrentlyinthetrianglelistcalculatethetrianglecircumcirclecenterandradiusifthepointliesinthetrianglecircumcirclethenaddthethreetriangleedgestotheedgebufferremovethetrianglefromthetrianglelistendifendfordeletealldoublyspecifiededgesfromtheedgebufferthisleavestheedgesoftheenclosingpolygononlyaddtothetrianglelistalltrianglesformedbetweenthepointandtheedgesoftheenclosingpolygonendforremoveanytrianglesfromthetrianglelistthatusethesupertriangleverticesremovethesupertriangleverticesfromthevertexlistend其⽅法虽然可实现三⾓化，但是效率还是不太⾼在看过优化后的伪代码为：input:顶点列表(vertices)//vertices为外部⽣成的随机或乱序顶点列表output:已确定的三⾓形列表(triangles)初始化顶点列表创建索引列表(indices=newArray(vertices.length))//indices数组中的值为0,1,2,3,......,vertices.length-1基于vertices中的顶点x坐标对indices进⾏sort//sort后的indices值顺序为顶点坐标x从⼩到⼤排序(也可对y坐标，本例中针对x坐标)确定超级三⾓形将超级三⾓形保存⾄未确定三⾓形列表(temptriangles)将超级三⾓形push到triangles列表遍历基于indices顺序的vertices中每⼀个点//基于indices后，则顶点则是由x从⼩到⼤出现初始化边缓存数组(edgebuffer)遍历temptriangles中的每⼀个三⾓形计算该三⾓形的圆⼼和半径如果该点在外接圆的右侧则该三⾓形为Delaunay三⾓形，保存到triangles并在temp⾥去除掉跳过如果该点在外接圆外(即也不是外接圆右侧)则该三⾓形为不确定//后⾯会在问题中讨论跳过如果该点在外接圆内则该三⾓形不为Delaunay三⾓形将三边保存⾄edgebuffer在temp中去除掉该三⾓形对edgebuffer进⾏去重

将edgebuffer中的边与当前的点进⾏组合成若⼲三⾓形并保存⾄temptriangles中将triangles与temptriangles进⾏合并除去与超级三⾓形有关的三⾓形end⼤多数同学看过伪代码后还是⼀头雾⽔，所以⽤图来解释这个过程，我们先⽤三点来做实例：如图，随机的三个点根据离散点的最⼤分布来求得随机⼀个超级三⾓形(超级三⾓形意味着该三⾓形包含了点集中所有的点)我的⽅法是根据相似三⾓形定理求得与矩形⼀半的⼩矩形的对⾓三⾓形，扩⼤⼀倍后则扩⼤后的直⾓三⾓形斜边经过点(Xmax,Ymin)但是为了将所有的点包含在超级三⾓形内，在右下⾓对该三⾓形的顶点进⾏了横和⾼的扩展，并要保证这个扩展三⾓形底⼤于⾼，才能实现包含这样求得的超级三⾓形不会特别⼤使得计算复杂，⽽且过程也简单，并将超级三⾓形放⼊temptriangles中接下来就像是伪代码中描述的那样，对temptriangle中的的三⾓形遍历画外接圆，这时先对左边的第⼀个点进⾏判断，其在圆内所以该三⾓形不为Delaunay三⾓形，将其三边保存⾄edgebuffer中，temptriangle中删除该三⾓形将该点与edgebuffer中的每⼀个边相连，组成三个三⾓形，加⼊到temptriangles中再将重复对temptriangles的遍历并画外接圆，这时使⽤的是第⼆个点来进⾏判断该点在三⾓形1外接圆右侧，则表⽰左侧三⾓形为Delaunay三⾓形，将该三⾓形保存⾄triangles中该点在三⾓形2外接圆外侧，为不确定三⾓形，所以跳过(后⾯会讲到为什么要跳过该三⾓形)，但并不在temptriangles中删除该点在三⾓形3外接圆内侧，则这时向清空后的edgebuffer加⼊该三⾓形的三条边，并⽤该点写edgebuffer中的三⾓边进⾏组合，组合成了三个三⾓形并加⼊到temptriangles中再次对temptriangles进⾏遍历，这⾥该数组⾥则含有四个三⾓形，⼀个是上次检查跳过的含有第⼀个点的三⾓形和新根据第⼆个点⽣成的三个三⾓形该点在三⾓形1外接圆右侧，则该三⾓形为Delaunay三⾓形，保存⾄triangles中，并在temptriangles中删除该点在三⾓形2外接圆外侧，跳过该点在三⾓形3外接圆内侧，将该三边保存⾄tempbuffer中，并在temptriangles中删除该点在三⾓形4外接圆内侧，将该三边保存⾄tempbuffer中，并在temptriangles中删除这时，tempbuffer中有六条边，triangles中有两个三⾓形，temptriangles中有1个三⾓形对tempbuffer中的六条边进⾏去重，得到五条边，将该点与这五条边组合成五个三⾓形并加⼊到temptriagnles中，这时temptriangles中有6个三⾓形由于三个点已经遍历结束，到了不会再对第三个点形成的三⾓形做外接圆，这时则将triangles与temptrianlges合并，合并后的数组表⽰包含已经确定的Delaunay三⾓形和剩下的三⾓形这时除去合并后数组中的和超级三⾓形三个点有关的所有三⾓形，即进⾏数组坐标的限定，则得到了最后的结果：这是⽤最少的三个点来做讲解，点数越多的话计算量会越⼤，但是都是在上⾯步骤下进⾏的。问题在⽤点对三⾓形外接圆位置关系进⾏判断的时候，为什么点在外接圆的右侧的话可以确定该三⾓形是Delaunay三⾓形⽽当点外接圆的外侧且⾮右侧时，为什么要路过三⾓形，不把该三⾓形确定为Delaunay三⾓形呢？⾸先，我们在开始的时候对原始⽅法进⾏优化时，我们增加了⼀个indices数组来操作vertices，并对indices依据vertices的x坐标进⾏了从⼩到⼤的排序则我们在后⾯遍历点时是从点集的最左侧开始的，如图：当遍历下⼀个点时，该点在外接圆的右侧，则表⽰以后所有的点都在该外接圆的右侧，则保证了Delaunay三⾓形的空圆特性⽽当点在外接圆外，并⾮外接圆右侧时，如图：在该三⾓形的外切圆中，当遍历到点1时，符合在外侧的条件，但是不能确定后⾯所有的点都保持在外接圆外侧如果说该三⾓形就为Delaunay三⾓形的话，如图中的点2及后⾯可能出现