Projet de Fondamentaux pour l'Informatique Graphique

Sujets

Deux sujets sont proposés. Pour chaque sujet il y a un fichier en format JSON avec les données du problème. Chaque sujet doit être choisi par au moins deux binômes.

Sujet 1 : remaillage d'un polygone

Étant donné un polygone avec \(n\) segments, vous devez calculer un nouveau polygone tel que :

1. Le nouveau polygone a au plus \( 10 n\) segments.
2. Aucun segment du polygone est plus de deux fois plus long qu'un autre.
3. L'angle entre deux segments adjacents doit être supérieur à \( 3 \pi / 4\) radians.

Avec ces contraintes il faut construire le polygone le plus proche du polygone donné. Quelques précisions :

• On mesure la distance entre deux polygones avec la distance de Hausdorff.
  La distance entre un sommet \( s \) d'un polygone \(P_1\) et un polygone \(P_2\), \( d(s, P_2)\), est la plus petite distance vers tous les segments de \( P_2 \). Attention, ce n'est pas la distance vers ses sommets uniquement.
  La distance du polygone \(P_1\) au polygone \(P_2\) est \(d(P_1 \rightarrow P_2) = \max \{ d(s, P_2), s \in P_1\}\).
  La distance de Hausdorff entre les deux polygones est \( d_H(P_1, P_2) = \max(d(P_1 \rightarrow P_2), d(P_2 \rightarrow P_1)) \).
• Données d'entrée : sujet1.instance.zip
• Données de sortie : distance entre les polygones ; liste des sommets du polygone. Exemple :

  {
    "distance": 0.0124,
    "sommets": [
      {"x": 0.2, "y": 0.3},
      {"x": 0.2, "y": 0.4},
      {"x": 0.3, "y": 0.4}
    ]
  }

Sujet 2 : recouvrement de points par de tétraèdres

Étant donnée une liste de \(n\) points dans l'espace, trouvez \(n\) tétraèdres tels que :

1. Chaque tétraèdre contient exactement un point dans son intérieur.
2. Chaque point se trouve à l’intérieur d'un tétraèdre (c'est une conséquence de la contrainte précédente).
3. Deux tétraèdres ne peuvent pas s'intersecter.
4. Les tétraèdres sont contenus dans la boîte englobante \( [0, 10]^3 \).

Avec ces trois contraintes il faut construire la liste de tétraèdres avec le plus grand volume. Quelques précisions :

• Un tétraèdre contient un point si le point se trouve dans son intérieur. Le tétraèdres ne contient pas donc ses propres sommets ni les points sur ses arêtes ou faces.
• Les sommets d'un tétraèdre peuvent être sur la frontière du sous-espace \( [0, 10]^3 \).
• Données d'entrée : sujet2.instance.zip
• Données de sortie : volume total ; liste des tétraèdres. Chaque tétraèdre est défini par les coordonnées de ses quatre points. Exemple :

  {
    "volume": 84.32,
    "tetraedres": [
      [
        {"x": 0.2, "y": 0.3},
        {"x": 0.2, "y": 0.4},
        {"x": 0.2, "y": 0.4},
        {"x": 0.5, "y": 0.8}
      ],
      [
        {"x": 1.2, "y": 1.3},
        {"x": 1.2, "y": 1.4},
        {"x": 0.1, "y": 0.8},
        {"x": 0.4, "y": 1.1}
      ]
    ]
  }

Modalités de rendu

Le projet est à réaliser en binôme.

Pour le rendu, un des membres du binôme déposera une archive appelée fig-projet.zip ou fig-projet.rar sur AMeTICE.

L'archive doit contenir :

• Le fichier JSON donné en entrée.
• Un fichier appelé solution.json avec votre meilleure solution. Respectez le format donné dans le sujet.
• Un fichier appelé checker.py ou checker.cpp qui, une fois exécuté, vérifie que votre solution est correcte et calcule sa ponctuation.
• Un fichier appelé rapport.pdf ou rapport.md en format libre qui explique les algorithmes que vous avez codés pour vérifier votre solution.

La date limite de rendu est le mercredi 2 novembre 2022 à 23h00.

De plus, je vous encourage à faire votre projet sur le serveur Gitlab de l'université Etulab et de m'inviter sur votre projet.

Évaluation

Votre travail sera évalué sur la qualité des algorithmes, du code et de vos explications. De plus, le meilleur binôme sur chaque sujet aura un bonus.

La note du projet sera calculée avec ce barème :

Résultats

Aucune solution était valide.

F.A.Q.

Peut-on utiliser de librairies externes ?

Non, vous devez vous-même implanter les fonctions du programme qui vérifie votre solution. C'est ainsi que vous démontrerez que vous avez compris les contenus de ce cours.

Faut-il rendre le code qui calcule la solution ?

Non. Vous avez donc droit à utiliser des librairies externes pour calculer votre solution.

Comment lire et écrire un fichier JSON ?

En Python vous avez le module json dans la bibliothèque standard. En C++ vous pouvez utiliser la librairie rapidjson.

Peut-on rendre plus de fichiers ?

Vous pouvez séparer le code de votre vérificateur de solutions en plusieurs fichiers si ça améliore sa lisibilité, mais l'’'exécutable doit s’appeler checker.*.