Analysis of the Computational Cost of PolyFront: an Algorithm for Planar Triangulation
DOI:
https://doi.org/10.15377/2409-5761.2023.10.5Keywords:
Mesh generation, Polygon offsetting, Computational cost, Two-dimensional delaunay triangulationAbstract
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.
Downloads
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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: https://doi.org/10.1145/3450626.3459673
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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: https://doi.org/10.1093/comjnl/24.2.167
Downloads
Published
Issue
Section
License
Copyright (c) 2023 Nadaniela Egidi, Josephin Giacomini, Luciano Misici, Alessia Perticarini, Riccardo Piergallini
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
All the published articles are licensed under the terms of the Creative Commons Attribution Non-Commercial License (CC BY-NC 4.0) which permits unrestricted, non-commercial use, distribution and reproduction in any medium, provided the work is properly cited.
