Talk on Surfaces and Volumes (Slide 23)

23 Better way to calculate Voronoi volume (step 2)

Want to traverse the vertices associated with a particular atom center (atom 0) to find the volume of its Voronoi polyhedron.
Pick all the vertices that share two common atoms -- atom 0 and another atom, atom 1. These vertices form the edges around a face. Pick an arbitary vertex on the edge to start (e.g. vertex 012) and walk around the perimeter of the face. You can tell which vertices are neighboring on the perimeter because they will have a third atom in common (in addition to atom 0 and atom 1). With reference to the starting vertex the face can be divided into triangles, for which it is trivial to calculate areas and volumes.
The total area of the face comes from summing all its triangular areas. The volume of the pyramid from atom 0 to the face is calculated from the usual formula Ad/3, where A is the area of the face and d is distance to the face (half the distance between atom 0 and atom 1).
This sequential walking procedure also gives you a way to draw polyhedra on a graphics device.