Improve performance of Voronoi volume estimation

Question

I need to estimate the volumes associated with a set of Voronoi cells in a multi-dimensional space. From this question Volume of Voronoi cell (python) I tested this answer and it works, but it is really slow.

In the code below, obtaining the volumes takes up almost 90% of the time:

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)

That 90% is almost entirely used by the calls to scipy.spatial.ConvexHull.

Can this be improved in any way?

Answer 1

The call to scipy.spatial.ConvexHull creates a lot of overhead. When calling the attribute volume the object has to decide on its outer points first which is essentially the smallest circumference around all the points passed (in this case). Therefore, the use of a function that calculates the surface area of a polygon given n points should be sufficient. See Area of a convex polygon for an implementation of such a function, under the assumption that the voronoi cells are convex (which is usually the case.)

See this StackOverflow answer for a Python specific implementation.