triangulation_orient


triangulation_orient, a MATLAB code which reads a triangulation, and reorients each triangle that has a negative area. If at least one such triangle is encountered, the program writes out a new copy of the triangle file in which all the triangles have been correctly oriented.

The input file prefix_nodes.txt contains the node information for the triangulation. Each data line contains the X and Y coordinates of a single node.

The input file prefix_elements.txt contains the triangle information for the triangulation. Each line contains the indices of 3 or 6 nodes that form a triangle.

For many applications, including computer graphics and finite element computations, it is assumed that the triangles are described with a positive orientation. That is, the nodes are listed in clockwise order.

TRIANGULATION_ORIENT can check whether every triangle in a triangulation has positive orientation, and can "repair" the file if it finds one or more triangles with a negative orientation.

A misoriented order 3 triangle:

               2
              /|
             / |
            /  |
           /   |
          /    |
         1-----3
      
The corrected order 3 triangle:
               3
              /|
             / |
            /  |
           /   |
          /    |
         1-----2
      

A misoriented order 6 triangle:

               2
              /|
             / |
            4  5
           /   |
          /    |
         1--6--3
      
The corrected order 6 triangle:
               3
              /|
             / |
            6  5
           /   |
          /    |
         1--4--2
      

Usage:

triangulation_orient ( 'prefix' )
where 'prefix' is the common filename prefix:

Licensing:

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

Languages:

triangulation_orient is available in a C++ version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

triangulation, a MATLAB code which carries out various operations on order 3 ("linear") or order 6 ("quadratic") triangulations.

triangulation_boundary_edges, a MATLAB code which reads data defining a triangulation, determines which edges lie on the boundary, organizes them into connected components, and writes this information to a file.

triangulation_boundary_nodes, a MATLAB code which reads data defining a triangulation, determines which nodes lie on the boundary, and writes their coordinates to a file.

triangulation_corner, a MATLAB code which patches triangulations so that no triangle has two sides on the boundary.

triangulation_delaunay_discrepancy, a MATLAB code which measures the amount by which a triangulation fails the local delaunay test;

triangulation_display, a MATLAB code which displays the nodes and elements of a triangulation on the MATLAB graphics screen;

triangulation_histogram, a MATLAB code which computes histograms of data over a triangulation.

triangulation_l2q, a MATLAB code which reads data defining a 3-node triangulation and generates midside nodes and writes out the corresponding 6-node triangulation.

triangulation_mask, a MATLAB code which takes an existing triangulation and deletes triangles and their corresponding nodes as requested by the user.

triangulation_order3, a data directory which contains a description and examples of order 3 triangulations.

triangulation_order6, a data directory which contains a description and examples of order 6 triangulations.

triangulation_orient_test

triangulation_plot, a MATLAB code which reads data defining a triangulation and creates a postscript image of the nodes and triangles.

triangulation_q2l, a MATLAB code which reads data defining a 6-node triangulation, and subdivides each triangle into 4 3-node triangles, writing the resulting triangulation to a file.

triangulation_quad, a MATLAB code which estimates the integral of a function over a triangulated region.

triangulation_quality, a MATLAB code which reads data defining a triangulation and computes a number of quality measures.

triangulation_rcm, a MATLAB code which reads data defining a triangulation, determines an ordering of the nodes that will reduce the bandwidth of the adjacency matrix, and writes the new triangulation information to a file.

triangulation_refine, a MATLAB code which reads data defining a triangulation, replaces each triangle by four congruent smaller ones, and writes the new triangulation information to a file.

triangulation_triangle_neighbors, a MATLAB code which reads data defining a triangulation, determines the neighboring triangles of each triangle, and writes that information to a file.

Reference:

  1. Franz Aurenhammer,
    Voronoi diagrams - a study of a fundamental geometric data structure,
    ACM Computing Surveys,
    Volume 23, Number 3, September 1991, pages 345-405.
  2. Marc deBerg, Marc Krevald, Mark Overmars, Otfried Schwarzkopf,
    Computational Geometry,
    Springer, 2000,
    ISBN: 3-540-65620-0.
  3. Barry Joe,
    GEOMPACK - a software package for the generation of meshes using geometric algorithms,
    Advances in Engineering Software,
    Volume 13, Number 5, 1991, pages 325-331.
  4. Albert Nijenhuis, Herbert Wilf,
    Combinatorial Algorithms for Computers and Calculators,
    Second Edition,
    Academic Press, 1978,
    ISBN: 0-12-519260-6,
    LC: QA164.N54.
  5. Atsuyuki Okabe, Barry Boots, Kokichi Sugihara, Sung Nok Chiu,
    Spatial Tesselations: Concepts and Applications of Voronoi Diagrams,
    Second Edition,
    Wiley, 2000,
    ISBN: 0-471-98635-6,
    LC: QA278.2.O36.
  6. Joseph ORourke,
    Computational Geometry,
    Second Edition,
    Cambridge, 1998,
    ISBN: 0521649765,
    LC: QA448.D38.
  7. Per-Olof Persson, Gilbert Strang,
    A Simple Mesh Generator in MATLAB,
    SIAM Review,
    Volume 46, Number 2, June 2004, pages 329-345.

Source Code:


Last revised on 10 April 2019.