上QQ阅读APP看书，第一时间看更新
3.10.4 德劳内三角化
德劳内三角化算法对给定的点集合的凸包进行三角形分割，使得每个三角形的外接圆都不含任何点。下面的程序演示了德劳内三角化的效果：
Delaunay对象dy的simplices属性是每个三角形的顶点在points2d中的下标。可以通过三角形的顶点坐标计算其外接圆的圆心，不过这里使用同一点集合的沃罗诺伊图的vertices属性，vertices就是每个三角形的外接圆的圆心。
x = np.array([46.445, 263.251, 174.176, 280.899, 280.899,
189.358, 135.521, 29.638, 101.907, 226.665])
y = np.array([287.865, 250.891, 287.865, 160.975, 54.252,
160.975, 232.404, 179.187, 35.765, 71.361])
points2d = np.c_[x, y]
dy = spatial.Delaunay(points2d)
vo = spatial.Voronoi(points2d)
dy.simplices vo.vertices
------------ --------------------------------
[[8, 5, 7], [[ 104.58977484, 127.03566055],
[1, 5, 3], [ 235.1285 , 198.68143374],
[5, 6, 7], [ 107.83960707, 155.53682482],
[6, 0, 7], [ 71.22104881, 228.39479887],
[0, 6, 2], [ 110.3105 , 291.17642838],
[6, 1, 2], [ 201.40695449, 227.68436282],
[1, 6, 5], [ 201.61895891, 226.21958623],
[9, 5, 8], [ 152.96231864, 93.25060083],
[4, 9, 8], [ 205.40381294, -90.5480267 ],
[5, 9, 3], [ 235.1285 , 127.45701644],
[9, 4, 3]] [ 267.91709907, 107.6135 ]]
下面是用delaunay_plot_2d()绘制德劳内三角化的结果，此外还绘制每个外接圆及其圆心。可以看到三角形的所有顶点都不在任何外接圆之内，效果如图3-63所示：
图3-63 德劳内三角形的外接圆与圆心
cx, cy = vo.vertices.T
ax = pl.subplot(aspect="equal")
spatial.delaunay_plot_2d(dy, ax=ax)
ax.plot(cx, cy, "r.")
for i, (cx, cy) in enumerate(vo.vertices):
px, py = points2d[dy.simplices[i, 0]]
radius = np.hypot(cx - px, cy - py)
circle = pl.Circle((cx, cy), radius, fill=False, ls="dotted")
ax.add_artist(circle)
ax.set_xlim(0, 300)
ax.set_ylim(0, 300)