Voronoi体积估计的改进性能

Question

我需要估计与多维空间中的一组Voronoi细胞相关的体积。根据这个问题Volume of Voronoi cell (python)，我测试了this answer，它可以工作，但是速度确实很慢。

在下面的代码中，获取卷几乎占用了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的调用。

可以通过任何方式对此进行改进吗？

Answer 1

scipy.spatial.ConvexHull的调用会产生大量开销。调用属性scipy.spatial.ConvexHull时，对象必须首先确定其外部点，该外部点实质上是所有通过的点（在这种情况下）周围的最小圆周。因此，使用给定n个点来计算多边形表面积的函数应该足够了。在voronoi细胞是凸形的情况下（通常是这种情况），请参见volume以实现此功能。

有关特定于Python的实现，请参见Area of a convex polygon StackOverflow答案。