Keywords
Polygon offsetting
Computational cost
Two-dimensional delaunay triangulation
How to Cite
Abstract
The triangulation of planar domains is a relevant and largely studied problem in many applied sciences. This paper analyzes the computational time of a triangulation algorithm for plane domains with holes, introduced in a previous paper. This algorithm is based on the normal offsetting technique starting from a polygonal approximation of the domain boundary. It is shown that the computational time is linear with respect to the number of vertices of the triangulation. Experimental results confirm the theoretical upper bound obtained for the computational time.
References
Wang Q, Ye J, Wu H, Gao B, Shepherd P. A triangular grid generation and optimization framework for the design of free-form gridshells. Comput Aid Des. 2019; 113: 96–113. https://doi.org/10.1016/j.cad.2019.04.005
Liu F, Feng R. Automatic triangular grid generation on a free-form surface using a particle self-organizing system. Eng Comput. 2020; 36: 377–89. https://doi.org/10.1007/s00366-019-00705-4
Liu F, Feng R, Tsavdaridis KD. A novel progressive grid generation method for free-form grid structure design and case studies. J Build Eng. 2021; 34: 101866. https://doi.org/10.1016/j.jobe.2020.101866
Liseikin V. Grid generation methods. vol. 1, Springer; 1999, p. 1–29. https://doi.org/10.1007/978-3-662-03949-6_1
Thompson JF. Handbook of grid generation. 1st Edition. Boca Raton: CRC Press; 1999. https://doi.org/10.1201/9781420050349
George P-L, Houman Borouchaki. Delaunay triangulation and meshing. vol. 1. Paris: 1998.
Parthasarathy VN, Graichen CM, Hathaway AF. A comparison of tetrahedron quality measures. Finite Elem Anal Des. 1994; 15: 255–61. https://doi.org/10.1016/0168-874X(94)90033-7
Mandad M, Campen M. Guaranteed-quality higher-order triangular meshing of 2D domains. ACM Trans Graph. 2021; 40: 1–14. https://doi.org/10.1145/3476576.3476736
Egidi N, Misici L, Piergallini R. PolyFront: an algorithm for fast generation of the high-quality triangular mesh. Eng Comput. 2011; 27: 357–72. https://doi.org/10.1007/s00366-010-0206-6
Blacker TD, Stephenson MB. Paving: A new approach to automated quadrilateral mesh generation. Int J Numer Methods Eng. 1991; 32: 811–47. https://doi.org/10.1002/nme.1620320410
van Rens BJE, Brokken D, Brekelmans WAM, Baaijens FPT. A two-dimensional paving mesh generator for triangles with controllable aspect ratio and quadrilaterals with high quality. Eng Comput. 1998; 14: 248–59. https://doi.org/10.1007/BF01215978
George JA. Computer implementation of the finite element method. Stanford University; 1971.
Lo SH. A new mesh generation scheme for arbitrary planar domains. Int J Numer Methods Eng. 1985; 21: 1403–26. https://doi.org/10.1002/nme.1620210805
Löhner R. Progress in grid generation via the advancing front technique. Eng Comput. 1996; 12: 186–210. https://doi.org/10.1007/BF01198734
Peraire J, Vahdati M, Morgan K, Zienkiewicz OC. Adaptive remeshing for compressible flow computations. J Comput Phys. 1987; 72: 449–66. https://doi.org/10.1016/0021-9991(87)90093-3
Egidi N, Misici L, Pennesi R. An algorithm for planar triangulations. A graphical user interface. Proceedings of MASCOT03-3rd Meeting on Applied Scientific Computing and Tools, Grid Generation, Approximation and Visualization, Roma: IMACS Series in Computational and Applied Mathematics; 2004, p. 71–80.
Watson DF. Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes. Comput J. 1981; 24: 167–72. https://doi.org/10.1093/comjnl/24.2.167
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Copyright (c) 2023 Nadaniela Egidi, Josephin Giacomini, Luciano Misici, Alessia Perticarini, Riccardo Piergallini