1

我需要估计与多维空间中一组 Voronoi 单元相关的体积。从这个问题Volume of Voronoi cell (python)我测试了这个答案并且它有效，但它真的很慢。

在下面的代码中，获取卷占用了几乎 90% 的时间：

import numpy as np
from scipy.spatial import Voronoi
from scipy.spatial import ConvexHull
import time as t

points = np.random.uniform(0., 100., (5000, 4))

s = t.time()
v = Voronoi(points)
print(t.time() - s)

s = t.time()
vol = np.zeros(v.npoints)
for i, reg_num in enumerate(v.point_region):
    indices = v.regions[reg_num]
    if -1 in indices:  # non-closed regions
        vol[i] = np.inf
    else:
        vol[i] = ConvexHull(v.vertices[indices]).volume
print(t.time() - s)

这 90% 几乎完全被调用使用scipy.spatial.ConvexHull。

这可以以任何方式改进吗？

4

1 回答 1

0

调用scipy.spatial.ConvexHull会产生很多开销。调用属性时volume，对象必须首先确定其外部点，这基本上是所有通过点周围的最小周长（在这种情况下）。因此，在给定 n 个点的情况下，使用计算多边形表面积的函数就足够了。假设 voronoi 单元是凸的（通常是这种情况），请参阅凸多边形的面积以了解此类函数的实现。

有关Python 特定实现，请参阅此StackOverflow 答案。

于 2020-03-19T14:15:13.700 回答