Python 实现 Delaunay Triangulation

Delaunay Triangulation 是一种空间划分的方法，它能使得分割形成的三角形最小的角尽可能的大，关于 Delaunay Triangulation 的详细介绍，请参考这里，Delaunay Triangulation在很多领域都有应用，科学计算领域它是有限元和有限体积法划分网格的重要方法，除此之外在图像识别、视觉艺术等领域也有它的身影。
贴一段有趣的油管视频，用 Delaunay Triangulation 进行人脸识别的演示：Delaunay Triangulation and Voronoi Diagram in OpenCV
接下来写一下怎么用 Python 实现 Delaunay Triangulation，需要用到的模块有Numpy, Matplotlib 和 Scipy，基本的思路是随机制造几个点，然后利用scipy.spatial.Delaunay对这些点进行处理配对三角形，最后用matplotlib的tripcolor(填充三角形颜色，如果不需要填充颜色，可以用triplot).

下面贴上代码：

from scipy.spatial import Delaunay
import numpy as np
import matplotlib.pyplot as plt

# Triangle Settings
width = 200
height = 40
pointNumber = 1000
points = np.zeros((pointNumber, 2))
points[:, 0] = np.random.randint(0, width, pointNumber)
points[:, 1] = np.random.randint(0, height, pointNumber)

# Use scipy.spatial.Delaunay for Triangulation
tri = Delaunay(points)

# Plot Delaunay triangle with color filled
center = np.sum(points[tri.simplices], axis=1)/3.0
color = np.array([(x - width/2)**2 + (y - height/2)**2 for x, y in center])
plt.figure(figsize=(7, 3))
plt.tripcolor(points[:, 0], points[:, 1], tri.simplices.copy(), facecolors=color, edgecolors='k')


# Delete ticks, axis and background
plt.tick_params(labelbottom='off', labelleft='off', left='off', right='off',
                bottom='off', top='off')
ax = plt.gca()
ax.spines['right'].set_color('none')
ax.spines['bottom'].set_color('none')
ax.spines['left'].set_color('none')
ax.spines['top'].set_color('none')

# Save picture
plt.savefig('Delaunay.png', transparent=True, dpi=600)

贴上结果：

来自fangs.in