Volume of Voronoi cell (python)

As was mentioned in comments, you can compute ConvexHull of each Voronoi cell. Since Voronoi cells are convex, you will get the proper volumes.

def voronoi_volumes(points):
    v = Voronoi(points)
    vol = np.zeros(v.npoints)
    for i, reg_num in enumerate(v.point_region):
        indices = v.regions[reg_num]
        if -1 in indices: # some regions can be opened
            vol[i] = np.inf
        else:
            vol[i] = ConvexHull(v.vertices[indices]).volume
    return vol

This method works in any dimensions

I think I've cracked it. My approach below is:

• For each region of the Voronoi diagram
• perform a Delaunay triangulation of the vertices of the region
  • this will return a set of irregular tetrahedra which fill the region
• The volume of a tetrahedron can be calculated easily (wikipedia)
  • sum these volumes to get the volume of the region.

I'm sure there will be both bugs and poor coding - I'll be looking for the former, comments welcome on the latter - especially as I'm quite new to Python. I'm still checking a couple of things - sometimes a vertex index of -1 is given, which according to the scipy manual "indicates vertex outside the Voronoi diagram", but in addition, vertices are generated with coordinates well outside the original data (insert numpy.random.seed(42) and check out the coordinates of the region for point 7, they go to ~(7,-14,6), point 49 is similar. So I need to figure out why sometimes this happens, and sometimes I get index -1.

from scipy.spatial import Voronoi,Delaunay
import numpy as np
import matplotlib.pyplot as plt

def tetravol(a,b,c,d):
 '''Calculates the volume of a tetrahedron, given vertices a,b,c and d (triplets)'''
 tetravol=abs(np.dot((a-d),np.cross((b-d),(c-d))))/6
 return tetravol

def vol(vor,p):
 '''Calculate volume of 3d Voronoi cell based on point p. Voronoi diagram is passed in v.'''
 dpoints=[]
 vol=0
 for v in vor.regions[vor.point_region[p]]:
  dpoints.append(list(vor.vertices[v]))
 tri=Delaunay(np.array(dpoints))
 for simplex in tri.simplices:
  vol+=tetravol(np.array(dpoints[simplex[0]]),np.array(dpoints[simplex[1]]),np.array(dpoints[simplex[2]]),np.array(dpoints[simplex[3]]))
 return vol

x= [np.random.random() for i in xrange(50)]
y= [np.random.random() for i in xrange(50)]
z= [np.random.random() for i in xrange(50)]
dpoints=[]
points=zip(x,y,z)
vor=Voronoi(points)
vtot=0


for i,p in enumerate(vor.points):
 out=False
 for v in vor.regions[vor.point_region[i]]:
  if v<=-1: #a point index of -1 is returned if the vertex is outside the Vornoi diagram, in this application these should be ignorable edge-cases
   out=True
  else:
 if not out:
  pvol=vol(vor,i)
  vtot+=pvol
  print "point "+str(i)+" with coordinates "+str(p)+" has volume "+str(pvol)

print "total volume= "+str(vtot)

#oddly, some vertices outside the boundary of the original data are returned, meaning that the total volume can be greater than the volume of the original.