TRIG_TO_NEIB
Determine Adjacent Neighbors in Triangulation

TRIG_TO_NEIB is a C program which reads files defining the nodes and elements of a triangulation, and computes a list of the node neighbors, and, optionally, information about the Voronoi decomposition of the region, by Lili Ju.

The input files are a pair of "NODE" and "ELE" files that use a format specified by the triangle() program.

For each node N1, its set of "neighbors" includes every node N2 which occurs in some element that also includes node N1.

The output node neighbor file lists, for each node, the number of node neighbors, followed by the neighbors in counter clockwise order.

An image of the triangulation can be made using the showme program, or the triangle_display program.

Usage:

trig_to_neib nodes.txt elements.txt neib.txt voro.txt

• nodes.txt is an input file containing node information;
• elements.txt is an input file containing element information;
• neib.txt is an output file containing the node neighbor information;
• voro.txt is an optional output file containing Voronoi information;

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

TRIG_TO_NEIB is available in a C version.

Related Data and Programs:

SHOWME, a C program which uses the X Window library to display triangulatons, by Jonathan Shewchuk.

TRIANGLE, a C program which computes a triangulation of a geometric region, by Jonathan Shewchuk.

TRIANGLE_FILES, a data directory of examples of files used by the triangle and showme programs.

TRIANGULATION, a C library which performs various operations on order 3 (linear) or order 6 (quadratic) triangulations.

TRIANGULATION_TRIANGLE_NEIGHBORS, a C program which reads data defining a triangulation, determines the neighboring triangles of each triangle, and writes that information to a file.

Author:

Lili Ju

Reference:

1. Lili Ju,
   Conforming centroidal Voronoi Delaunay triangulation for quality mesh generation,
   International Journal of Numerical Analysis and Modeling,
   Volume 4, Number 3-4, 2007, pages 531-547.
2. Robert Renka,
   Algorithm 751: TRIPACK, A Constrained Two-Dimensional Delaunay Triangulation Package,
   ACM Transactions on Mathematical Software,
   Volume 22, Number 1, March 1996, pages 1-8.
3. Jonathan Shewchuk,
   Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator,
   in Applied Computational Geometry: Towards Geometric Engineering,
   edited by Ming Lin, Dinesh Manocha,
   Lecture Notes in Computer Science, Volume 1148,
   Springer, 1996,
   ISBN: 354061785X,
   LC: QA448.D38.A635.

Source Code:

• trig_to_neib.c, the source code.

Examples and Tests:

ELL is a set of example data which corresponds to a mesh using 21 nodes and 24 elements, constituting a mesh of an L-shaped domain.

• ell.node the node file.
• ell.ele the element file.
• ell.neib the node neighbor file.
• ell.voro the Voronoi file.

GREENLAND is a set of example data which corresponds to a mesh using 33,343 nodes and 64,125 elements, constituting a mesh of Greenland.

• greenland.node the node file.
• greenland.ele the element file.
• greenland.neib the node neighbor file.
• greenland.voro the Voronoi file.

List of Routines:

• MAIN is the main program for TRIG_TO_NEIB.
• COMP_CIRCUM computes the circumcenter of a triangle.
• COMP_NEIB computes the neighbor information.
• READ_MESH reads the input files that define the mesh.
• WRITE_NEIB writes the neighbor information to an output file.
• WRITE_VORO writes the Voronoi information to an output file.

You can go up one level to the C source codes.