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

Mathieu Brévilliers

Sujets

• Brevilliers
• Triangulation de Delaunay
• Soutenance de thèse
• Théorème de Rice
• Convector
• Changement climatique

Informations

• Publié par: Anji
• Nombre de lectures: 433
• Langue: Breton
• Poids de l'ouvrage: 1 Mo

Extrait

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