Construction de la triangulation de Delaunay de segments par ...

107

pages

Breton

Documents

Écrit par
Mathieu Brévilliers

Publié par
Anji

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

107

pages

Breton

Documents

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

Publié par

Anji

Nombre de lectures

434

Langue

Breton

Poids de l'ouvrage

1 Mo

Construction de la triangulation de Delaunay de
segments par un algorithme de ﬂip
Mathieu Brévilliers
Laboratoire LMIA
Université de Haute-Alsace
Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 1 / 42Triangulation de points
Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 2 / 42Triangulation de points
Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 3 / 42Triangulation de points
Théorème
′Pour tout ensemble S de n sites, soit n le nombre de sites sur la
frontière de l’enveloppe convexe de S.
Toute triangulation de S admet :
′2n− n − 2 faces et
′3n− n − 3 arêtes.
′Exemples où n= 8 et n = 6 : 8 faces et 15 arêtes
Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 4 / 42Triangulation de Delaunay
Triangulation quelconque
Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 5 / 42Triangulation de Delaunay
Triangulation quelconque Triangulation de Delaunay
Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 5 / 42Triangulation de Delaunay
Triangulation quelconque Triangulation de Delaunay
Régularité
La triangulation de Delaunay maximise le minimum des
angles des triangles.
Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 5 / 42Algorithme de ﬂip
Une triangulation quelconque de S
⇓
Modiﬁcations locales
⇓
Triangulation de Delaunay de S
Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 6 / 42Algorithme de ﬂip
Une triangulation ...

Voir

Publié par

Anji

Nombre de lectures

434

Langue

Breton

Poids de l'ouvrage

1 Mo

Construction de la triangulation de Delaunay de segments par un algorithme de ﬂip Mathieu Brévilliers Laboratoire LMIA Université de Haute-Alsace Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 1 / 42Triangulation de points Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 2 / 42Triangulation de points Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 3 / 42Triangulation de points Théorème ′Pour tout ensemble S de n sites, soit n le nombre de sites sur la frontière de l’enveloppe convexe de S. Toute triangulation de S admet : ′2n− n − 2 faces et ′3n− n − 3 arêtes. ′Exemples où n= 8 et n = 6 : 8 faces et 15 arêtes Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 4 / 42Triangulation de Delaunay Triangulation quelconque Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 5 / 42Triangulation de Delaunay Triangulation quelconque Triangulation de Delaunay Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 5 / 42Triangulation de Delaunay Triangulation quelconque Triangulation de Delaunay Régularité La triangulation de Delaunay maximise le minimum des angles des triangles. Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 5 / 42Algorithme de ﬂip Une triangulation quelconque de S ⇓ Modiﬁcations locales ⇓ Triangulation de Delaunay de S Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 6 / 42Algorithme de ﬂip Une triangulation quelconque de S ⇓ Modiﬁcations locales ⇓ Triangulation de Delaunay de S 1 Comment savoir si la triangulation courante est de Delaunay ? 2 Quelles sont les modiﬁcations locales à effectuer ? 3 L’algorithme converge-t-il vers la triangulation de Delaunay? Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 6 / 42Légalité d’une arête Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 7 / 42

Voir