Getting 3D Voronoi Cells from Qhull output

Question

My goal is to get the individual 3D Voronoi cells (both vertices and edges) from the output of Qhull's qvoronoi subroutine. However, I'm having trouble understanding the voronoi ridges (output 'Fv'). A sample line from the output is:

7 0 1 1 0 4 5 3

The first number is the number of vertices in the line, the next two are the indices of the vertices separated by the ridge, and the rest of the numbers are the vertex indices on the ridge. I naively tried connecting adjacent vertices (i.e. 4->5, 5->3, 3->1, etc.), and it seemed to work, though I wasn't sure if that was correct. How do the points connect to each other?

Additionally, from the qvoronoi output (option 'FN'), I can get the vertices of each region, but there is no information about the connectivity between the vertices. I am wondering where this information is. Is it in the ridges output, or in a different qvoronoi output option?

Answer 1

The indices of the ridge do not seem to be in cyclic order. So, reconstructing back the polygon face might not be possible.

An alternate is to pass the output of gvoronoi of each cell to qconvex to construct the convex hull. This does not scale well, but might be okay if you have few cells you want to visualize or analyse.

For example, to get Voronoi cell of input site 5 of 30 input sites:

$ rbox 30 D3 | qvoronoi QV5 p | qconvex G

Answer 2

Try convex hull

Because Voronoi guarantees only convex polyhedra, there's a hacky way of finding this by finding a convex hull (in my case, scipy.spatial.ConvexHull()). The minimal convex hull surrounding your Voronoi region will be equivalent to what you want, and scipy.spatial even gives you further stuff for free

hull=scipy.spatial.ConvexHull(vertices)
volume=hull.volume
triangle_mesh_hull=vertices[hull.simplices] # shape is (n,3,3)

credit for the very short, elegant lines above goes to Jaime. If you want to do something to each triangular section of the mesh after this, you can access it like:

for triangle in triangle_mesh_hull:
  do_stuff_to(triangle)
  ...
  ...
  ...
  do_more_stuff_with(triangle)
  ...
  ...
  ...