On discute de l'existence d'un maillage simplicial pour un polyèdre arbitraire. Étant donné un maillage (en triangles) conforme de la surface du domaine, décider s'il existe une triangulation (sans point interne autre que de Steiner) de ce domaine est un problème NP-complet. Ce papier décrit une méthode qui construit une telle triangulation, assurant ainsi son existence. La méthode proposée comprend trois étapes. En premier, un algorithme de triangulation de Delaunay est appliqué aux points donnés, ensuite une étape de regénération des éléments de la surface est faite qui conduit à la partition des faces initiales. Enfin, une dernière étape permet de supprimer les points (sauf ceux de Steiner) ajoutés lors de cette partition.
Issues related to the existence of a triangulation of an arbitrary polyhedron are addressed. Given a boundary surface mesh (a set of triangular facets), the problem to decide whether or not a triangulation (with no internal points apart from the Steiner points) exists is reported to be NP-hard. In this paper, an algorithm to triangulate a general polyhedron is used which makes use of a classical Delaunay triangulation algorithm, a phase for recovering the missing boundary facets by means of facet partitioning and a final phase that makes it possible to remove the additional (non-Steiner) points previously defined so as to recover the initial boundary mesh thus resulting in a mesh of the given polyhedron.
Accepté le :
Publié le :
@article{CRMATH_2004__338_9_735_0,
author = {George, Paul-Louis and Borouchaki, Houman},
title = {Maillage simplicial d'un poly\`edre arbitraire},
journal = {Comptes Rendus. Math\'ematique},
pages = {735--740},
publisher = {Elsevier},
volume = {338},
number = {9},
year = {2004},
doi = {10.1016/j.crma.2003.12.033},
language = {fr},
url = {http://www.numdam.org/articles/10.1016/j.crma.2003.12.033/}
}
TY - JOUR AU - George, Paul-Louis AU - Borouchaki, Houman TI - Maillage simplicial d'un polyèdre arbitraire JO - Comptes Rendus. Mathématique PY - 2004 SP - 735 EP - 740 VL - 338 IS - 9 PB - Elsevier UR - http://www.numdam.org/articles/10.1016/j.crma.2003.12.033/ DO - 10.1016/j.crma.2003.12.033 LA - fr ID - CRMATH_2004__338_9_735_0 ER -
%0 Journal Article %A George, Paul-Louis %A Borouchaki, Houman %T Maillage simplicial d'un polyèdre arbitraire %J Comptes Rendus. Mathématique %D 2004 %P 735-740 %V 338 %N 9 %I Elsevier %U http://www.numdam.org/articles/10.1016/j.crma.2003.12.033/ %R 10.1016/j.crma.2003.12.033 %G fr %F CRMATH_2004__338_9_735_0
George, Paul-Louis; Borouchaki, Houman. Maillage simplicial d'un polyèdre arbitraire. Comptes Rendus. Mathématique, Tome 338 (2004) no. 9, pp. 735-740. doi : 10.1016/j.crma.2003.12.033. http://www.numdam.org/articles/10.1016/j.crma.2003.12.033/
[1] Géométrie Algorithmique, Ediscience, Paris, 1995
[2] Boundary enforcement by facet splits in Delaunay based mesh generation, 7th Inter. Conf. on Numerical Grid Generation in Computational Field Simulations, Whistler, BC, Canada, September 2000, pp. 203-221
[3] Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm, SIAM J. Comput., Volume 13 (1984) no. 3, pp. 488-507
[4] Triangulating a simple polygon in linear time, Discrete Comput. Geom., Volume 6 (1991), pp. 485-524
[5] Triangulating a nonconvex polytope, Discrete Comput. Geom., Volume 5 (1990), pp. 505-526
[6] Approximating constrained tetrahedrizations, Computer Aided Geometric Design, vol. 10, Academic Press, 1993, pp. 67-87
[7] P.L. George, H. Borouchaki, E. Saltel, Maillage simplicial d'un polyèdre arbitraire. Partie II : Construction et exemples, Rapport de recherche INRIA, RR-4398, 2002
[8] Automatic mesh generator with specified boundary, Comput. Methods Appl. Mech. Engrg., Volume 92 (1991), pp. 269-288
[9] A point-placement strategy for conforming Delaunay tetrahedralization, Proc. 11th ACM-SIAM Symposium on Discrete Algorithms, 2000, pp. 67-74
[10] Ph.P. Pebay, Delaunay-admissibilié a priori en dimensions 2 et 3, Thèse de l'Université Pierre et Marie Curie, Paris, 2000
[11] Computational Geometry, an Introduction, Springer-Verlag, 1985
[12] On the difficulty of triangulating three-dimensional nonconvex polyhedra, Discrete Comput. Geom., Volume 7 (1992), pp. 227-253
[13] Über die Zerlegung von Dreieckspolyedern, Math. Ann., Volume 98 (1928), pp. 309-312
[14] Efficient three-dimensionnal Delaunay triangulation with automatic point creation and imposed boundary constraints, Int. J. Numer. Methods Engrg., Volume 37 (1994), pp. 2005-2039
Cité par Sources :
