我在新scipy中运行scipy.spatial.Delaunay的3D中有大约50,000个数据点(我使用的是0.10),这给了我一个非常有用的三角测量。
基于:http : //zh.wikipedia.org/wiki/Delaunay_triangulation(“与Voronoi图的关系”部分)
…我想知道是否有一种简单的方法可以得到三角剖分的“对偶图”,即Voronoi Tesselation。
有什么线索吗?我对此进行的搜索似乎没有显示预先构建的scipy函数,我发现这几乎很奇怪!
谢谢,爱德华
邻接信息可以neighbors在Delaunay对象的属性中找到。不幸的是,该代码目前还没有向用户公开周围环境,因此您必须自己重新计算这些中心。
neighbors
而且,不能以这种方式直接获得延伸到无穷大的Voronoi边缘。仍然可能,但还需要更多思考。
import numpy as np from scipy.spatial import Delaunay points = np.random.rand(30, 2) tri = Delaunay(points) p = tri.points[tri.vertices] # Triangle vertices A = p[:,0,:].T B = p[:,1,:].T C = p[:,2,:].T # See http://en.wikipedia.org/wiki/Circumscribed_circle#Circumscribed_circles_of_triangles # The following is just a direct transcription of the formula there a = A - C b = B - C def dot2(u, v): return u[0]*v[0] + u[1]*v[1] def cross2(u, v, w): """u x (v x w)""" return dot2(u, w)*v - dot2(u, v)*w def ncross2(u, v): """|| u x v ||^2""" return sq2(u)*sq2(v) - dot2(u, v)**2 def sq2(u): return dot2(u, u) cc = cross2(sq2(a) * b - sq2(b) * a, a, b) / (2*ncross2(a, b)) + C # Grab the Voronoi edges vc = cc[:,tri.neighbors] vc[:,tri.neighbors == -1] = np.nan # edges at infinity, plotting those would need more work... lines = [] lines.extend(zip(cc.T, vc[:,:,0].T)) lines.extend(zip(cc.T, vc[:,:,1].T)) lines.extend(zip(cc.T, vc[:,:,2].T)) # Plot it import matplotlib.pyplot as plt from matplotlib.collections import LineCollection lines = LineCollection(lines, edgecolor='k') plt.hold(1) plt.plot(points[:,0], points[:,1], '.') plt.plot(cc[0], cc[1], '*') plt.gca().add_collection(lines) plt.axis('equal') plt.xlim(-0.1, 1.1) plt.ylim(-0.1, 1.1) plt.show()