Delaunay 三角剖分3D（原理 + 源码）

Delaunay 三角剖分

原理部分请参照我的上一篇博文，传送门：Delaunay 三角剖分2D（原理 + 源码）

3D三角剖分参考文献：

• vvvv is free for non-commercial use
• delaunayTriangulation
• CGAL 4.13 - 3D Triangulations
• 强烈推荐：PCL： Delaunay三角剖分（关于三维实体分块思想总结）

二维与三维的区别

• 二维时，插入新的一点 P，然后判断 P 与 triangle 列表里每个三角形的外接圆的相对位置关系
• 三维时，插入新的一点 P，然后判断 P 与 tetrahedron 列表里每个四面体的外接球的相对位置关系

二维

三维

代码实现< Python版本 >

用到的 lib：

• matplotlib
• numpy

原文链接：https://stackoverflow.com/questions/26434726/return-surface-triangle-of-3d-scipy-spatial-delaunay

import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
import matplotlib.tri as mtri
from scipy.spatial import Delaunay# u, v are parameterisation variables
u = np.array([0,0,0.5,1,1]) 
v = np.array([0,1,0.5,0,1]) x = u
y = v
z = np.array([0,0,1,0,0])# Triangulate parameter space to determine the triangles
#tri = mtri.Triangulation(u, v)
tri = Delaunay(np.array([u,v]).T)print('polyhedron(faces = [')
#for vert in tri.triangles:
for vert in tri.simplices:print('[%d,%d,%d],' % (vert[0],vert[1],vert[2]))
print('], points = [')
for i in range(x.shape[0]):print('[%f,%f,%f],' % (x[i], y[i], z[i]))
print(']);')fig = plt.figure()
ax = fig.add_subplot(1, 1, 1, projection='3d')# The triangles in parameter space determine which x, y, z points are
# connected by an edge
#ax.plot_trisurf(x, y, z, triangles=tri.triangles, cmap=plt.cm.Spectral)
ax.plot_trisurf(x, y, z, triangles=tri.simplices, cmap=plt.cm.Spectral)plt.show()

效果图：

代码实现< Matlab 版本 >

原文链接：https://www.mathworks.com/help/matlab/ref/delaunaytriangulation.html

x = gallery('uniformdata',[30 1],0);
y = gallery('uniformdata',[30 1],1);
z = gallery('uniformdata',[30 1],2);
DT = delaunayTriangulation(x,y,z)tetramesh(DT,'FaceAlpha',0.3);

效果图：