Stage de DEA
Fig. 1 -- Graphe de tangence.
Dans ce stage de DEA, le graphe de tangence est construit par l'algorithme de Pocchiola et Vegter [PV93] qui effectue un balayage droit du complexe de visibilité. Ce balayge est effectué grâce à un graphe auxiliaire.
Étant donnée une direction t, les tangentes aux objets de direction t sont représentées par un sommet. Ces tangentes découpent l'espace en régions, et deux tangentes bordant une même région sont reliées par une arête (figure 2).
Fig. 2 -- Découpage selon une direction et graphe associé.
Ce graphe est modifié quand on fait varier t lorsque t passe par la pente t0 d'une bitangente. L'algorithme de calcul du graphe de tangence consiste à maintenir ce graphe quand t varie (de 0 à 2Pi par exemple). La mise à jour du graphe se fait en temps constant à chaque passage d'une bitangente (exemple figure 3).
Fig. 3 -- Mise à jour du graphe lors du passage d'une bitangente.
Une queue de priorité sert à passer les bitangentes dans l'ordre de leur pente, et l'algorithme s'exécute en temps O(k log n) où n est le nombre d'objets et k le nombre d'arêtes du graphe de tangence.
Pocchiola et Vegter ont depuis élaboré un algorithme optimal de balayage (en temps O(n log n + k)) grâce au concept de pseudo-triangulation.
,
Variations sur un haricot et une spirale :
,
,
,
Une scène abstraite et une pieuvre jongleuse.
,
