原⽂链接：
不规则三⾓⽹（Triangulated Irregular Network，TIN）在表⽰地形的形态⽅⾯具有较好的表现，其⽣成算法⼀直备受关注。Delaunay三⾓剖分⽣成的⽹格正则性好，因此在实际⼯程计算中应⽤很⼴。⽣成 Delaunay 三⾓⽹格的⽅法中，⽬前⼤都基于 Bowyer-Watson法，它是⼀种逐点插⼊法，基本思路是 ：先由给定的点集⽣成⼀初始⽹格，再根据 Delaunay 剖分原理，逐次向⽹格内加点 ，并重新连接⽣成新⽹格，直到所有点添加完毕。 下⾯我们就该算法的思路、步骤进⾏解析。
地磁指数预报基本思想：
1. 假定已⽣成了连接若⼲个顶点的 Delaunay 三⾓⽹格
增压供水
2. 加⼊⼀个新的节点，出所有外接圆包含新加⼊节点的三⾓形，并将这些三⾓形删除，形成⼀个空腔3. 空腔的节点与新加⼊的节点连接，形成新的 Delaunay 三⾓形⽹格
4. 不断循环直到遍历完所有点
⽰意图如下：
通过上述思路我们总结出算法需要解决的⼏⼤问题：
1. 初始格⽹的⽣成
高温熔化炉
2. 新增点所影响三⾓形的查
3. 空腔的⽣成
下⾯我们就这些问题提出解决⽅法。
我们可以通过显⽰窗⼝的四个顶点来⽣成包含所有离散点的两个三⾓形，算法结束后删除就好，如图
⽽外接圆包含新增点的三⾓形，这⾥我们称为坏三⾓形，坏三⾓形的查是本算法的核⼼。
⼀般来说，如果采⽤暴⼒遍历的⽅法，随着算法后⾯三⾓格⽹的复杂度不断增加，坏三⾓形的查也会变得越来越困难。所以我们希望可以有⽅法加速这⼀进程，但这⾥我们不做讨论，因为我没有实际运⽤。没错我的算法很暴⼒。
那么问题来了，新增点的坏三⾓形可能不⽌⼀个，如果要⼀直遍历出所有坏三⾓，就算是我也没暴⼒到这种程度。
这⾥我们发现，如果⼀个三⾓形是坏三⾓，那么它邻接的三⾓肯定有两个也是坏三⾓。那么我们可以通过构建⼀个三⾓形邻接表，到⼀个坏三⾓就等于到了⼀圈坏三⾓。
滤扇ds.append(p)
# 计算外接圆包括p点的三⾓（坏三⾓形）
bad_triangles = []
for T iangles:
# 距离跟半径的⽐较
if self.inCircle(T, p):
自助硬币存取款机bad_triangles.append(T)
# 空腔边缘。
boundary = []
T = bad_triangles[0]
edge = 0
while True:
# 检查三⾓形T的边缘是否在boundary⾥...
tri_op = iangles[T][edge]
if tri_op not in bad_triangles:
boundary.append((T[(edge+1) % 3], T[(edge-1) % 3], tri_op))
edge = (edge + 1) % 3
# 是否完⼀圈
if boundary[0][0] == boundary[-1][1]:
break
else:
# 下⼀条边
减温减压装置技术要求edge = (iangles[tri_op].index(T) + 1) % 3
T = tri_op
# delete删除，删出⼀个空洞
for T in bad_triangles:
iangles[T]
del self.circles[T]
代码中boundary即是图中绿⾊空腔边缘。删掉所有坏三⾓形成空腔，再通过空腔边缘与新增点形成新的三⾓格⽹完成更新，当然不要忘了更新各种附加数据。
最终效果图如下，右⽅的括号内是三⾓形顶点点号
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议