Fig. 1.8 -- Schéma heuristique décrivant les
problèmes de visibilité dans le plan et indiquant les sujets
traités dans ce mémoire.
Plus précisément, nous cherchons dans ce travail de thèse à utiliser la cohérence spatiale et temporelle pour résoudre des problèmes de visibilité. Pour cela nous voulons utiliser des structures de données purement géométriques qui ne requièrent pas l'utilisation supplémentaire de structures combinatoires de recherche compliquées (pas plus compliquées qu'un arbre de recherche équilibré par exemple) pour obtenir de bonnes performances.
Le reste de ce chapitre 1 est consacré à l'étude des structures de données que nous allons utiliser : le graphe et le complexe de visibilité. Cette étude nous permettra aussi d'introduire deux outils de géométrie algorithme que nous utilisons presque constamment dans les algorithmes que nous étudions : le calcul par balayage et la dualité.
Dans le chapitre 2 nous décrivons un algorithme optimal pour construire ces structures de données.
Dans le chapitre 3 nous montrons comment utiliser le complexe de visibilité pour calculer des polygones de visibilité :
Tous les algorithmes que nous présentons sont développés dans le cadre de scènes d'objets en position générale, c'est-à-dire où les sommets des polygones ne sont pas alignés. Nous supposons donc que les scènes ne contiennent pas de configurations dégénérées telles que celles données en exemple dans la figure 1.9
Fig. 1.9 -- Configurations dégénérées où
des sommets de polygones sont alignés.
Nous supposons aussi que tous les calculs effectués dans ces algorithmes sont faits de façon exacte. Les problèmes de dégénérescence et d'imprécision des calculs numériques ne sont pas oubliés pour autant : ces problèmes sont importants en pratique et font l'objet du chapitre 5 de ce mémoire.
Enfin, nous faisons dans le dernier chapitre un bilan des travaux présentés et indiquons des directions de recherches permettant de poursuivre et compléter ces travaux.