用 Python 实现 Delaunay Triangulation

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

下面贴上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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)

贴上结果: