Reconstruction de courbes et surfaces par le compexe de temoins

Reconstruction de courbes et surfaces par le complexe de temoins

L'objectif principal de ce projet est d'implanter l'algorithme multi-echelles de reconstruction de courbes a partir de nuages de points presente dans le cours INF562 (Geometrie Algorithmique) et decrit dans le chapitre 4 du poly. Une extension naturelle sera d'adapter la methode au cas des surfaces. Vous serez donc amenes a utiliser les packages Jcg.triangulations2D et Jcg.triangulations3D.

1. La premiere etape consiste a implanter une structure de donnees representant le complexe de temoins en 2D. Comme ce dernier est inclus dans la triangulation de Delanay (par le theoreme des temoins), votre classe pourra heriter de Jcg.triangulations2D.Delaunay_2 et vous aurez simplement a marquer les aretes appartenant au complexe (il ne sera pas necessaire de construire les triangles du complexe puisqu'on veut reconstruire des courbes). Les methodes d'output de la triangulation devront etre modifiees pour ne renvoyer que le complexe de temoins.

2. La deuxieme etape consiste a implanter l'algorithme de reconstruction proprement dit. Ce dernier prend en entree un nuage de points W et construit iterativement un sous-nuage P, en partant d'un point arbitraire de W puis en inserant a chaque etape le point de W le plus eloigne des points de P. En paralle de ces insertions il maintient le complexe de temoins, ou plutot l'ensemble de ses aretes, comme illustre dans la figure 1 ci-dessous. Votre objectif sera de ne pas reconstruire tout le complexe a chaque iteration de l'algorithme, mais plutot de ne modifier que la partie du complexe qui est affectee par chaque insertion de point dans P. Pour cela vous pourrez maintenir, pour tout point w de W, des pointeurs vers les deux points de P les plus proches de w, et mettre a jour ces pointeurs a chaque insertion. Une remarque qui pourra vous etre utile : les nouvelles aretes entrant dans le complexe de temoins lors de l'insertion d'un point p dans P sont toutes incidentes a p.

Fig. 1 - De gauche a droite, deroulement de l'algorithme en 2D : un point arbitraire de W est choisi (en bleu), puis a chaque iteration on insere dans P le point de W le plus eloigne de P. En parallele, on maintient le complexe de temoins (aretes en bleu).

3. A ce stade du projet il faudra tester votre programme sur des jeux de donnees. Pour cela vous pouvez utiliser les jeux de donnees suivants, au format xy (la premiere ligne du fichier indique la dimension ambiante, chaque ligne suivante donne les deux coordonnees d'un point du nuage): patate.xy, os.xy, star.xy, ptitbiscuit.xy. Ces jeux de donnees sont illustres dans l'ordre dans la figure 2 ci-dessous.

Fig. 2 - Illustration des jeux de donnees 2D fournis ci-dessus.

L'objectif sera d'evaluer experimentalement deux choses :

la correction de l'algorithme, i.e. le fait que dans la famille de complexes construite il y a bien une sous-famille dont les elements sont topologiquement equivalents a la courbe sous-jacente aux donnees.
la complexite de l'algorithme : on s'attachera a montrer experimentalement que la complexite est sous-quadratique, ce qui implique en particulier qu'on evite bien de reconstruire tout le complexe a chaque etape de l'algorithme.

4. En guise d'extension, on pourra considerer le cas des surfaces en 3D. Pour cela il faudra adapter votre implementation du complexe de temoins pour qu'elle construise egalement les triangles du complexe (pas besoin de contruire les tetraedres puisqu'on s'interesse a la reconstruction de surface). Vous pourrez cette fois faire heriter votre classe de Jcg.triangulations3D.Delaunay_3, et marquer dans la triangulation les aretes et les triangles appartenant au complexe de temoins. Pour tester votre code, vous pourrez utiliser les jeux de donnees suivants, au format xyz (la premiere ligne donne la dimension, chaque ligne suivante donne les 3 coordonnees d'un point du nuage): chair.xyz, tanglecube.xyz, bunny.xyz, asklepios.xyz. Ces jeux de donnees sont illustres dans la figure 3 ci-dessous.

Fig. 3 - Illustration des jeux de donnees fournis ci-dessus (le bunny est courtesy of the Stanford Graphics Laboratory, et la statue d'Asklepios provient du Aim@Shape repository).

Normalement, vos reconstructions sur les jeux de donnees ci-dessus devraient avoir des trous. L'explication de ces trous se trouve dans la reference [1] ci-dessous. Si vous avez le temps et l'envie, vous pouvez essayer d'implementer la methode presentee dans cet article et la tester sur les memes jeux de donnees.

Mot clés: complexe de temoins, Delaunay restreint, reconstruction.

Références:
[1] L. J. Guibas and S. Y. Oudot. Reconstruction using Witness Complexes. Proceedings og the 18th ACM-SIAM Symposium on Discrete Algorithms, pages 1076-1085, 2007 (online version).