Mesh Topology

You may wish to know which triangles are adjacent to a certain Delaunay edge in an .edge file, which Voronoi cells are adjacent to a certain Voronoi edge in a .v.edge file, or which Voronoi cells are adjacent to each other. All of this information can be found by cross-referencing output files with the recollection that the Delaunay triangulation and the Voronoi diagram are planar duals.

Specifically, edge i of an .edge file is the dual of Voronoi edge i of the corresponding .v.edge file, and is rotated 90 degrees counterclockwise from the Voronoi edge. Triangle j of an .ele file is the dual of vertex j of the corresponding .v.node file. Voronoi cell k is the dual of vertex k of the corresponding .node file.

Hence, to find the triangles adjacent to a Delaunay edge, look at the vertices of the corresponding Voronoi edge. If the endpoints of a Voronoi edge are Voronoi vertices 2 and 6 respectively, then triangles 2 and 6 adjoin the left and right sides of the corresponding Delaunay edge, respectively. To find the Voronoi cells adjacent to a Voronoi edge, look at the endpoints of the corresponding Delaunay edge. If the endpoints of a Delaunay edge are input vertices 7 and 12, then Voronoi cells 7 and 12 adjoin the right and left sides of the corresponding Voronoi edge, respectively. To find which Voronoi cells are adjacent to each other, just read the list of Delaunay edges.

Triangle does not write a list of the edges adjoining each Voronoi cell, but one can be reconstructed straightforwardly. For instance, to find all the edges of Voronoi cell 1, search the output .edge file for every edge that has input vertex 1 as an endpoint. The corresponding dual edges in the output .v.edge file form the boundary of Voronoi cell 1.

For each Voronoi vertex, the .neigh file gives a list of the three Voronoi vertices attached to it. You might find this more convenient than the .v.edge file.


Return to Triangle home page.
jrs@cs.berkeley.edu