Constrained Delaunay Triangulation Using Delaunay Visibility

Yi-Jun Yang 1 Hui Zhang 1 Jun-Hai Yong 1 Wei Zeng Jean-Claude Paul 1 Jiaguang Sun
1 CAD - Computer Aided Design
LIAMA - Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées, Inria Paris-Rocquencourt
Abstract : An algorithm for constructing constrained Delaunay triangulation (CDT) of a planar straight-line graph (PSLG) is presented. Although the uniform grid method can reduce the time cost of visibility determinations, the time needed to construct the CDT is still long. The algorithm proposed in this paper decreases the number of edges involved in the computation of visibility by replacing traditional visibility with Delaunay visibility. With Delaunay visibility introduced, all strongly Delaunay edges are excluded from the computation of visibility. Furthermore, a sufficient condition for DT (CDT whose triangles are all Delaunay) existence is presented to decrease the times of visibility determinations. The mesh generator is robust and exhibits a linear time complexity for randomly generated PSLGs.
Type de document :
Communication dans un congrès
Advances in Visual Computing, Second International Symposium, ISVC 2006, Proceedings part I, Nov 2006, Lake Tahoe / USA, 4291, 2006, Lecture Notes in Computer Science. 〈10.1007/11919476〉
Liste complète des métadonnées
https://hal.inria.fr/inria-00139015
Contributeur : Chine Publications Liama <>
Soumis le : mercredi 28 mars 2007 - 17:21:18
Dernière modification le : vendredi 25 mai 2018 - 12:02:04

Identifiants

Collections

INRIA | CIRAD | INRA | LIAMA

Citation

Yi-Jun Yang, Hui Zhang, Jun-Hai Yong, Wei Zeng, Jean-Claude Paul, et al.. Constrained Delaunay Triangulation Using Delaunay Visibility. Advances in Visual Computing, Second International Symposium, ISVC 2006, Proceedings part I, Nov 2006, Lake Tahoe / USA, 4291, 2006, Lecture Notes in Computer Science. 〈10.1007/11919476〉. 〈inria-00139015〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

160

Contact


archive-ouverte@inria.fr