Ce projet consiste à appliquer les méthodes vues en cours pour résoudre des problèmes géométriques dans le plan et l'espace affine.
Par binômes, vous devez rendre un fichier avec votre solution et du code Python ou C++ pour vérifier votre solution.
Cinq 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.
Étant donnée une liste de triangles sur le plan, trouvez dix droites qui intersectent ensemble un grand nombre de triangles. On cherche à maximiser ce nombre de triangles intersectés.
{
"droites": [
{"a": 1.2, "b": 0.5, "c": -1.5 },
{"a": 0.2, "b": 0.9, "c": -1.7 }
],
"triangles" : [0, 3, 8, 9]
}Étant donnée une liste de points sur le plan, trouvez un triangle pour chaque point qui ne contient que ce point dans son intérieur. De plus, les triangles doivent être contenus dans le sous-espace \( [0, 10]^2 \). On cherche à maximiser la somme des aires de tous ces triangles.
{
"aire": 123.8,
"triangles": [
[
{"x": 0.2, "y": 0.3},
{"x": 0.2, "y": 0.4},
{"x": 0.3, "y": 0.4}
],
[
{"x": 1.2, "y": 1.3},
{"x": 1.2, "y": 1.4},
{"x": 1.3, "y": 1.4}
]
]
}Étant donnée une liste de triangles dans le plan, trouvez un sous-ensemble de 10 triangles qui maximise la plus petite distance entre toutes les paires de triangles dans ce sous-ensemble.
Formellement, soit \( \mathcal{T} = \{ T_1, \ldots, T_n \} \) l'ensemble de triangles et \( d(T_i, T_j) \) la distance entre deux triangles, nous cherchons un sous-ensemble \( \mathcal{T'} \subset \mathcal{T} , |\mathcal{T'}| = 10 \) qui maximise \( f(\mathcal{T'}) = \min \{d(T, T') : T, T' \in \mathcal{T'} \} \). Il s'agit donc de trouver 10 triangles tous éloignés entre eux.
{
"distance": 12.8,
"triangles": [0, 6, 8, 15]
}Étant donnée une liste de points dans l'espace, trouvez 10 triangles qui minimisent la distance vers les points. De plus, l'aire de chaque triangle doit être plus petite que ou égale à 10.
Formellement, soit \( \mathcal{P} = \{ P_1, \ldots, P_n \} \subset \mathbb{R}^3 \) l'ensemble de points et \( \mathcal{T} = \{ T_1, \ldots, T_{10} \} \) l'ensemble de triangles, alors \(d(P_i, T_j)\) est la distance entre un point et un triangle. La distance d'un point vers l'ensemble de triangles est \( d(P, \mathcal{T}) = \min \{ d(P, T) : T \in \mathcal{T} \} \), c'est-à-dire la distance vers le triangle le plus proche. Nous cherchons à minimiser \( f(\mathcal{T}) = \max \{ d(P_i, \mathcal{T}) : P_i \in \mathcal{P} \} \).
{
"distance": 12.8,
"triangles": [
[
{"x": 0.2, "y": 0.3, "z": 0.8},
{"x": 0.2, "y": 0.4, "z": 0.8},
{"x": 0.3, "y": 0.4, "z": 0.9},
],
[
{"x": 1.2, "y": 1.3, "z": -0.2},
{"x": 1.2, "y": 1.4, "z": -0.2},
{"x": 1.3, "y": 1.4, "z": 0.4},
]
]
}Étant donnée une liste de droites dans l'espace, trouvez un sous-ensemble de 10 droites qui minimise la distance vers toutes les autres.
Formellement, soit \( \mathcal{D} = \{ D_1, \ldots, D_n \} \) l'ensemble de droites et \( \mathcal{D}' \subset \mathcal{D}, |\mathcal{D}'| = 10 \) le sous-ensemble. La distance entre deux droites est \(d(D_i, D_j) \). La distance d'une droite \( D_i \) vers le sous-ensemble de triangles est \( d(D_i, \mathcal{D'}) = \min \{ d(D_i, D_j) : D_j \in \mathcal{D'}, D_j \neq D_i \} \), c'est-à-dire la distance vers la droite la plus proche. Nous cherchons a minimiser \( f(\mathcal{D'}) = \max \{ d(D_i, \mathcal{D'}) : D_i \in \mathcal{D} \} \). Il s'agit donc de trouver 10 droites qui soient proches de toutes les autres.
{
"distance": 12.8,
"droites": [1, 4, 6, 13]
}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 le devoir dédié.
L'archive doit contenir :
La date limite de rendu est le mardi .
De plus, je vous encourage à faire votre projet sur le serveur Gitlab de l'université Etulab et de m'inviter sur votre projet.
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 :
| Partie | Barème |
|---|---|
| Algorithmes. Les calculs sont correctement implantés en exploitant bien les informations fournies. | 7 |
| Code. Le code est bien commenté et factorisé. | 7 |
| Rapport. Explications claires et bien rédigées. | 6 |
| Sujet | Binôme | Score |
|---|---|---|
| #1 | Tarek L / Louis E | 21990 |
| Théo P | 2408 | |
| Islam L / Guillaume TC | 0 (!) | |
| #2 | Charly F / Corentin L | 41.42 |
| François J / Marie LG | 104.73 | |
| #3 | Kevin M / Matthieu E | 3.01 |
| Billy C / Christine C | 0.0 (!) | |
| #4 | Alexandre P / Alexandre W | 4.08 |
| Cyril C / Jérémy A | 2.35 | |
| #5 | Gabriel P / Samantha T | 0.08 |
| Nathanaël S / William T | 2.20 |