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

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

-

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

Description

Construction de la triangulation de Delaunay de
segments par un algorithme de flip
Mathieu Brévilliers
Laboratoire LMIA
Université de Haute-Alsace
Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 1 / 42 Triangulation de points
Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 2 / 42 Triangulation de points
Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 3 / 42 Triangulation 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 / 42 Triangulation de Delaunay
Triangulation quelconque
Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 5 / 42 Triangulation de Delaunay
Triangulation quelconque Triangulation de Delaunay
Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 5 / 42 Triangulation 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 / 42 Algorithme de flip
Une triangulation quelconque de S

Modifications locales

Triangulation de Delaunay de S
Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 6 / 42 Algorithme de flip
Une triangulation ...

Sujets

Informations

Publié par
Nombre de visites sur la page 294
Langue Breton
Signaler un problème
Construction de la triangulation de Delaunay de segments par un algorithme de flip Mathieu Brévilliers Laboratoire LMIA Université de Haute-Alsace Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 1 / 42 Triangulation de points Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 2 / 42 Triangulation de points Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 3 / 42 Triangulation 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 / 42 Triangulation de Delaunay Triangulation quelconque Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 5 / 42 Triangulation de Delaunay Triangulation quelconque Triangulation de Delaunay Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 5 / 42 Triangulation 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 / 42 Algorithme de flip Une triangulation quelconque de S ⇓ Modifications locales ⇓ Triangulation de Delaunay de S Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 6 / 42 Algorithme de flip Une triangulation quelconque de S ⇓ Modifications locales ⇓ Triangulation de Delaunay de S 1 Comment savoir si la triangulation courante est de Delaunay ? 2 Quelles sont les modifications 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 / 42 Légalité d’une arête Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 7 / 42