Introduction to Voro++ 0.4.6: Efficient Calculation of 3D Voronoi Diagrams in C++
What is a Voronoi Diagram?
Before introducing Voro++, we first need to understand Voronoi diagrams. Imagine a flat area with several trees (which we call “seed points” or “sites”). The task of a Voronoi diagram is to partition this flat area into multiple regions, with the rule being: for any tree, its region contains all points on the plane that are closer to it than to any other tree.
Extending this concept to three-dimensional space, the seed points become points in space, and the partitions are no longer flat regions but polyhedral cells. This three-dimensional Voronoi diagram has extremely wide applications in fields such as physics (e.g., simulating granular materials), chemistry (e.g., simulating molecular structures), geography, and computer graphics.
Introduction to Voro++
Voro++ is an open-source C++ software library developed by Chris Rycroft, specifically designed for calculating Voronoi diagrams of points in three-dimensional space. Its name is derived from “Voronoi” itself. The main features of Voro++ are:
- High Performance: It uses a cell decomposition algorithm to break the computational container into multiple blocks, significantly improving computational efficiency.
- Memory Efficiency: It supports incremental computation, meaning it does not require all data to be loaded into memory at once, making it particularly suitable for handling large-scale particle systems.
- Flexibility: It provides various container classes that can handle periodic boundaries, non-periodic boundaries, and mixed boundary conditions, which aligns well with the needs of physical simulations.
- Focus on Three Dimensions: Unlike many general-purpose geometric libraries, Voro++ specializes in three-dimensional problems and has been deeply optimized for this purpose.
Version 0.4.6 is a stable and widely used version.
Core Concepts and Code Examples
The core workflow of Voro++ is: Create a container -> Insert particle points into the container -> Traverse each cell in the container and retrieve its information.
Example 1: Basic Usage – Calculating the Voronoi Diagram Inside a Cubic Box
Suppose we have a cubic box with a side length of 10, containing 200 randomly distributed points. We want to calculate their Voronoi cells.
// filename: basic_example.cc
#include "voro++.hh"
using namespace voro;
// Note: This example demonstrates the most basic usage of Voro++
int main() {
// 1. Set the boundaries of the container [x_min, x_max], [y_min, y_max], [z_min, z_max]
double x_min = 0, x_max = 10;
double y_min = 0, y_max = 10;
double z_min = 0, z_max = 10;
// 2. Set the number of blocks to decompose during computation. Typically, dividing each direction into 6-10 blocks yields good performance.
int n_x = 6, n_y = 6, n_z = 6;
// 3. Create a non-periodic container
// container( x_min, x_max, y_min, y_max, z_min, z_max, n_x, n_y, n_z,
// x_periodicity, y_periodicity, z_periodicity )
container con(x_min, x_max, y_min, y_max, z_min, z_max, n_x, n_y, n_z,
false, false, false);
// 4. Randomly add particles to the container
// put( particle_id, x, y, z )
for (int i = 0; i < 200; i++) {
double x = x_min + (x_max - x_min) * (rand() / (double)RAND_MAX);
double y = y_min + (y_max - y_min) * (rand() / (double)RAND_MAX);
double z = z_min + (z_max - z_min) * (rand() / (double)RAND_MAX);
con.put(i, x, y, z);
}
// 5. Output all particle Voronoi cell information to a file
con.draw_cells_gnuplot("pack_gnuplot.out");
// Custom format information can also be output, e.g., particle ID, position, volume, number of faces, etc.
con.print_custom("pack_custom.out", "ID=%i, Pos=(%x,%y,%z), Volume=%v, Faces=%s");
return 0;
}Compilation and Execution: Assuming the Voro++ header files and libraries are correctly installed, you can compile using the following command:
g++ -O2 -I/path/to/voro++/include basic_example.cc -L/path/to/voro++/lib -lvoro++Output File Description:
pack_gnuplot.out: This file can be read by gnuplot to plot the contours of the Voronoi diagram.pack_custom.out: This file contains custom information for each cell. Format description:%i: Particle ID.%x, %y, %z: Particle coordinates.%v: Volume of the cell.%s: Number of faces of the cell.
Example 2: Using Periodic Boundary Conditions
In many physical simulations (e.g., simulating liquids or crystals), the system is considered to be infinitely extended, which is achieved through periodic boundaries. Voro++ has excellent support for this.
// filename: periodic_example.cc
#include "voro++.hh"
using namespace voro;
int main() {
// Define a cubic periodic box
double x_min = 0, x_max = 10;
double y_min = 0, y_max = 10;
double z_min = 0, z_max = 10;
int n_x = 6, n_y = 6, n_z = 6;
// Create a container with periodicity in all directions
// Change the last three `false` to `true`
container_poly con_poly(x_min, x_max, y_min, y_max, z_min, z_max, n_x, n_y, n_z,
true, true, true, 8); // Note that here we use container_poly, and the last parameter is the initial memory allocation size
// Add some particles
con_poly.put(0, 1.0, 1.0, 1.0); // Particle 0
con_poly.put(1, 9.5, 9.5, 9.5); // Particle 1
// In a periodic system, particle 1 and particle 0 are very close at the boundary
// Their Voronoi cells will interact across the boundary
// Calculate and output the neighbor information for each cell
con_poly.print_custom("periodic_neighbors.out", "ID=%i, Pos=(%x,%y,%z), Neighbors=%n, Volume=%v");
return 0;
}In this example, we used container_poly, which is more versatile than the basic container and can support periodic boundaries and future possible feature expansions. The %n format specifier will output the IDs of all neighboring particles of that cell, which is very useful for analyzing the local topological structure between particles.
Example 3: Analyzing Cells Individually
Sometimes we do not need to output all cells but want to programmatically access the data of each cell and process it.
// filename: cell_analysis.cc
#include "voro++.hh"
#include <iostream>
using namespace voro;
using namespace std;
int main() {
container con(0, 10, 0, 10, 0, 10, 5, 5, 5, false, false, false);
// Add some particles
con.put(0, 2.0, 5.0, 5.0);
con.put(1, 5.0, 5.0, 5.0);
con.put(2, 8.0, 5.0, 5.0);
// Create a voronoicell object to store the computation results of a single cell
voronoicell c;
// Traverse all particles in the container
int particle_id = 1; // We want to compute the cell for the particle with ID 1
double x, y, z;
// Use the compute_cell method to calculate the cell of the specified particle
if (con.compute_cell(c, particle_id, x, y, z)) {
cout << "Particle " << particle_id << " at (" << x << ", " << y << ", " << z << ")" << endl;
cout << " Volume: " << c.volume() << endl;
cout << " Surface Area: " << c.surface_area() << endl;
cout << " Number of Faces: " << c.number_of_faces() << endl;
// Get the total number of edges (sum of edges of all faces)
vector<int> face_vertices;
c.face_vertices(face_vertices);
cout << " Total number of edges (sum over all faces): " << face_vertices.size() << endl;
} else {
cerr << "Error computing cell for particle " << particle_id << endl;
}
return 0;
}This example demonstrates how to interact directly with the voronoicell object, extracting geometric information for further analysis.
Conclusion
Voro++ 0.4.6 is a powerful and efficient tool that encapsulates the complex computation of three-dimensional Voronoi diagrams into an easy-to-use C++ interface. With its flexible container system, it can easily handle a variety of scenarios from simple closed boxes to complex fully periodic systems. Whether for data preprocessing in scientific research or as a component in large simulation software, Voro++ is a reliable choice.