Abstract
An algorithm is proposed for generating a conformal quasi-hierarchical triangular mesh that approximates a set of given polygonal lines to accuracy δ. The solvability of the problem is guaranteed by the possibility of shifting the polygonal lines within their δ-neighborhood. The resulting mesh consists of a small number of triangles and admits a multigrid implementation. An estimate is given for the growing number of mesh triangles with decreasing δ (of order log 22 δ−1). The algorithm is applied to a particular set of polygonal lines.
Similar content being viewed by others
References
A. Skvortsov, Delaunay Triangulation and Applications (Tomsk. Gos. Univ., Tomsk, 2002) [in Russian].
V. V. Shaidurov, Multigrid Finite Element Methods (Nauka, Moscow, 1989) [in Russian].
M. Rivara, “Mesh Refinement Processes Based on the Generalized Bisection of Simplexes,” SIAM J. Numer. Anal. 21, 604–613 (1984).
B. Baker, E. Grosse, and C. S. Rafferty, “Nonobtuse Triangulation of Polygons,” Disc. Comput. Geometry 3, 147–168 (1988).
M. Bern, D. Eppstein, and J. R. Gilbert, “Provably Good Mesh Generation,” Proceedings of the 31st Annual Symposium on Foundations of Computer Science (IEEE, 1990), pp. 231–241.
E. Bänsch, “Local Mesh Refinement in 2 and 3 Dimensions,” IMPACT Comput. Sci. Eng. 3, 181–191 (1991).
L. P. Chew, “Guaranteed-Quality Mesh Generator for Curved Surfaces,” Proceedings of Ninth Annual Symposium on Computational Geometry (ACM, 1993), pp. 274–280.
J. Ruppert, “A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generator,” J. Algorithms 18, 548–585 (1995).
G. Buscaglia and E. Dari, “Anisotropic Mesh Optimization and Its Application in Adaptivity,” Int. J. Numer. Methods Eng. 40, 4119–4136 (1997).
G. Carey, Computational Grids: Generation, Adaptation, and Solution Strategies (Taylor and Francis, London, 1997).
P. Frey and P.-L. George, Maillages: applications aux élément finis (Hermés, Paris, 1999).
V. Liseikin, Grid Generation Methods (Springer-Verlag, Berlin, 1999).
Yu. Vassilevski and K. Lipnikov, “Adaptive Algorithm for Generation of Quasi-Optimal Meshes,” Comput. Math. Math. Phys. 39, 1532–1551 (1999).
J. Shewshuk, “Delaunay Refinement Algorithms for Triangular Mesh Generation,” Comput. Geom. Theory Appl. 22(1–3) 21–74 (2002) (see also http://www-2.cs.cmu.edu/~jrs/jrspapers.html#cdt).
V. N. Chugunov, “On Conformal Grid that Weakly δ-Approximates Polygonal Lines,” in Numerical Methods, Parallel Computations, and Information Technologies (Inst. Vychisl. Mat. Ross. Akad. Nauk, Moscow, 2008), pp. 291–317 [in Russian].
http://www-users.informatic.rwth-aachen.de/~roberts/meshgeneration.html
http://www.engr.usask.ca/~macphed/finite/fe_resources/mesh.html
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © V.N. Chugunov, 2009, published in Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 2009, Vol. 49, No. 5, pp. 874–878.
Rights and permissions
About this article
Cite this article
Chugunov, V.N. Algorithm for generating a conformal quasi-hierarchical triangular mesh that weakly δ-approximates given polygonal lines. Comput. Math. and Math. Phys. 49, 842–845 (2009). https://doi.org/10.1134/S0965542509050091
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0965542509050091