• Résumé
• Composition du jury
• Téléchargement

Dans cette thèse, nous proposons une méthode de résolution des problèmes de la géométrie algorithmique posés pour des objets courbes (par opposition aux objets "linéaires" : ensembles de points, segments, polygones ...). Les objets que nous étudions sont des courbes de Bézier composites, choisies, d'une part, pour le réalisme qu'elles assurent dans la modélisation géométrique, et d'autre part, pour la facilité du traitement algorithmique que leurs propriétés offrent.

Notre approche met l'accent sur les aspects topologiques des problèmes abordés, en évitant les incohérences que la résolution en arithmétique flottante d'équations algébriques de degré élevé (générées par le traitement direct des courbes) peut le plus souvent introduire. Cet objectif est atteint par l'utilisation d'approximations polygonales convergentes, qui dans le cas des courbes de Bézier sont naturellement fournies par les polygones de contrôle par l'intermédiaire de la subdivision de de Casteljau.

Deux des problèmes fondamentaux de la géométrie algorithmique sont traités ici, l'enveloppe convexe et les arrangements, les deux en dimension 2. Dans le cas des arrangements, la notion de topologie (combinatoire) est bien connue ; dans celui de l'enveloppe convexe, nous la définissons rigoureusement. Pour les deux problèmes, nous montrons qu'il est possible d'obtenir toute l'information topologique définissant (de manière, il est vrai, implicite, mais correcte et complète) la solution exacte en travaillant exclusivement sur les approximations polygonales des objets donnés.

Les résultats théoriques obtenus sont concrétisés par des algorithmes dont la convergence et la correction sont démontrées et pour lesquels des études de coût sont réalisées. Des exemples illustrent le fonctionnement de ces algorithmes, validant la méthode proposée.

Mots-clef : géométrie algorithmique, CAGD, cohérence topologique, enveloppe convexe, arrangement, courbe de Bézier, approximation, subdivision, convergence

• Page de titre
• Table des matières
• Introduction
• Notations
• Les chapitres :
  1. La polycourbe
  2. Enveloppe convexe d'une polycourbe : résultats théoriques
  3. Algorithmes de calcul de l'enveloppe convexe d'une polycourbe de Bézier
  4. Arrangements de polycourbes : résultats théoriques
  5. Algorithme de calcul d'un arrangement de lignes polygonales équivalent à un arrangement de polycourbes
• Conclusion
• Bibliographie

Dernière mise à jour : 6.03.2000