Skip to main content
ARS Home » Southeast Area » Oxford, Mississippi » National Sedimentation Laboratory » Watershed Physical Processes Research » Research » Publications at this Location » Publication #240397
Title: A Simple Quality Triangulation Algorithm for Complex Geometries

Author
item ZHANG, YAOXIN - University Of Mississippi
item JIA, YAFEI - University Of Mississippi
item CHAN, H. C. - University Of Mississippi
item WANG, SAM - University Of Mississippi

Submitted to: International Journal for Numerical Methods in Fluids
Publication Type: Peer Reviewed Journal
Publication Acceptance Date: 1/10/2010
Publication Date: N/A
Citation: N/A

Interpretive Summary: A quality triangulation algorithm for complex geometries is proposed in this study. Despite of the Delaunay triangulation method used, little calculation is involved in the proposed triangulation algorithm. The present algorithm is simple and easy to implement. The present algorithm begins with an equilateral triangle meshes generated in a super triangle. Four different orientations are considered to construct this ST. It is found that the orientation of ST has little effects on the mesh quality and mesh size. To make the input edges and vertices included into the triangulation, the concept of “encroach” is adopted to treat the vertices around the boundaries. The mesh size reduction technique is used to generate non-uniform meshes with varied densities. Local refinements can be achieved by the faked boundaries which are defined for refinement purpose only. It is proved that the present algorithm bounds all angles between 19.50 and 1410 excluding the input small angles. The resulting non-uniform meshes always have fine meshes around the boundaries, which may cause redundancy problems. Since this problem is caused by the boundary refinement at the beginning, it is possible to apply some kind of coarsening technique combined with the size reduction technique to resolve it, which will be studied in the future.

Technical Abstract: This paper presents a new and simple algorithm for quality triangulation in complex geometries. The proposed algorithm is based on an initial equilateral triangle mesh covering the whole domain. The mesh nodes close to the boundary edges satisfy the so-called non-encroaching criterion: the distance from any inserted node to any boundary vertices and midpoints of any boundary edge is greater than a given characteristic length. Both nearly uniform and non-uniform triangle meshes can be generated using the mesh size reduction technique. It is proved that a bound of all angles can be provided by the proposed algorithm.