# MODFLOW-USG and Voronoi Cells

July 19, 2013

Traditional versions of MODFLOW (2005, NWT, LGR) work with structured rectilinear grids that require a prescribed set of rows, columns, and layers. The new MODFLOW-USG (UnStructured Grids) allows you to discretize the model domain with any grid geometry and varying degrees of cell sizes. This allows you to define smaller cell sizes around the areas of interest, resulting in more accurate results and reduced run-times. In this blog article, I will discuss Voronoi Cells which is one of the MODFLOW-USG geometries that will be supported in the next release of Visual MODFLOW Flex.

What is a Voronoi Diagram?

In euclidean geometry, a Voronoi Diagram is a way of dividing space into a number of regions. A set of points (called seeds or node generators) is specified beforehand.  For each seed there is a corresponding region consisting of all points closer to that seed than to any other. These regions are called Voronoi cells. The Voronoi Diagram is dual to the Delaunay Triangulation.The Delaunay Triangulation for a set of points is a collection of edges satisfying an “empty circle” property which states that “for each edge we can find a circle containing the edge’s endpoints but not containing any other points”.2

How are Voronoi Cells Created?

In Visual MODFLOW Flex, Voronoi Cells are created using a built-in mesh generator called “Triangle”. Triangle is a quick, robust 2D mesh generator commonly used for 2D finite element mesh generationin groundwater modeling programs such as FEFLOWTM. In Visual MODFLOW Flex, you define your conceptual model structure and boundary conditions using shapes.  For example, a polygon defines the model boundary, polylines and polygons define your boundary conditions, and points define your pumping/observation well locations. The vertices from these shapes (along with the points for well locations) are extracted and used as “seeds” for Triangle.  Triangle will insert other nodes to the mesh generation to create a stable mesh. In order to create Voronoi Cells, the option to “Force all Triangles to be Delaunay” must be used in Triangle. An example of a Delaunay Triangulation is shown below.

In Visual MODFLOW Flex, the process of Delaunay Triangulation is done “behind-the-scenes”; you will only see the resulting Voronoi Diagram that is created as a “by-product” of the Delaunay Triangulation. The following figure shows an example of a Voronoi Diagram for the same set of seeds.

If we overlay both the Delaunay Triangulation (in red) and Vornoi Diagram (in beige), you can see that these geometrical objects share the same set of seeds (node generators).

Voronoi Cells and MODFLOW-USG

MODFLOW-USG uses a Control Volume Finite Difference (CVFD) formulation, which has a few constraints related to the grid geometry.  For example, if you draw a connecting line between the centers of adjacent cells, this line should be perpendicular to the shared edge and should bisect the shared edge between these cells. A Voronoi Diagram is an unstructured grid geometry that closely honors CVFD constraints: the line connecting the node generators is always perpendicular to the shared edges (as shown in green in the figure below); and the connecting line will “nearly” bisect the shared edge, when the adjacent cell size is close.

In some scenarios, the connecting line may not bisect the shared edge.  This typically occurs when you have a large cell adjacent to a smaller cell. Fortunately, this can be improved by adjusting the cell size refinement and smoothing options built-into Triangle and then re-generating a new grid. Since Visual MODFLOW Flex provides a multi-model environment, you can re-generate several unstructured grids with ease and run the numerical simulations to quickly identify mass balance or convergence issues.

Benefits of Voronoi Cells

Voronoi Cells can handle complex geometries and boundaries with ease, similar to triangles. You can achieve efficient refinement around wells and other boundary condition objects without the tradeoff of an excessive number of cells. This results in higher accuracy “where it counts” and coarser cell size outside the areas of interest, and also should result in reduced run-times. An example is shown below with detailed grid refinement around a river, pumping well, and the edges of the model domain.

Finally, by using grid geometry that closely meets the CVFD requirements, this reduces the need to use Ghost Node Correction (GNC) package, and thus should result in higher accuracy and better model convergence in your MODFLOW-USG model runs.

A benchmark example of using Voronoi Polygons as UnStructured Grids for a MODFLOW-USG run is explained in this following blog post.

### References

1. Voronoi Tesselation: http://en.wikipedia.org/wiki/Voronoi_diagram

2. Delaunay Triangulation: http://en.wikipedia.org/wiki/Delaunay_triangulation

3. Triangle: http://www.cs.cmu.edu/~quake/triangle.html

MODFLOW–USG Version 1: An Unstructured Grid Version of MODFLOW for Simulating Groundwater Flow and Tightly Coupled Processes Using a Control Volume Finite-Difference Formulation. USGS Techniques and Methods 6–A45.  More details: http://water.usgs.gov/ogw/mfusg/

TM FEFLOW is a registered trademark of DHI-WASY