Calcul d'enveloppe convexe + triangulation
Bonjour,
Encore et toujours en TD d'info, jeudi dernier la prof m'a donné rien que pour moi un exercice parceque j'avais fini en avance.
Celui-ci était : À partir d'un nuage de point déterminer l'enveloppe convexe. Puis trianguler ce nuage de point.
En fait je n'ai pas réellement de problème pour trouver un algo, je voudrais juste vous le soumettre pour savoir si il est optimisable.
J'écris cet algo en langage presque naturel pour être peut-être plus compréhensible.
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
// Cette fonction prend en paramètre deux points et une direction (diagonale) de normale approximative et renvoi une direction de normale
fonction direction_normale(p1, p2, dir)
début
si p1.X = p2.X alors
si dir = "HG" ou dir = "BG" alors renvoyer "G";
sinon renvoyer "D";
fin si;
sinon si p1.Y = P2.Y alors
si dir = "HG" ou dir = "HD" alors renvoyer "H";
sinon renvoyer "B";
sinon renvoyer dir;
fin si;
fin direction_normale; |
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| Soit L un tableau (pré-remplis) dont chaque élément est un point.
Chaque point contient ses coordonnées X et Y.
Soit S un tableau de segment.
Chaque segment contient deux point p1 et p2 et une "normale" (qui n'en est pas réellement une). Cette normale ne sert qu'à donner le sens vers lequel on sort du polygône ; elle peut être "H", "B", "D", "G", "HD", "HG", "BG", "BD". (abréviations pour "haut", "bas" etc...)
Éliminer les doublons du tableau L.
Si il n'existe pas dans L au moins trois points non alignés, alors il n'existe pas de surface.
Déterminer les points min_x, max_x, min_y, max_y qui ont respectivement l'abscice la plus petite, la plus grande, et l'ordonnée la plus petite et la plus grande.
Si min_x et max_y ne sont pas confondus, alors on ajoute un segment dans S dont la normale est déterminée par direction_normale(min_x, max_y, "HG").
Si max_y et max_x ne sont pas confondus, alors on ajoute un segment dont la normale est déterminée par direction_normale(max_y, max_x, "HD").
Idem pour max_x/min_y et pour min_y/min_x.
// À ce point là on a un polygône de base qui n'est pas forcément l'enveloppe convexe du nuage de point.
faire
Pour chaque segment seg de S
Pour chaque point p de L
Si la normale du segment est "G" et que p.X = seg.p1.X alors
on rajoute deux segment dans S tel qu'ils soient le résultat du découpage de seg par le point p.
On enlève seg de S.
sinon si la normale est "HG" alors
si p.X = seg.p1.X alors
on découpe seg par p et la deuxième partie du segment aura une normale "H".
sinon si p.Y = seg.p2.Y alors
on découpe seg par p et la première partie du segment aura une normale "G".
sinon si (seg.p2.Y-seg.p1.Y)/(seg.p2.X-seg.p1.X) <= (p.Y-seg.p1.Y)/(p.X-seg.p1.X) alors
on coupe seg par p et les deux morceaux de segment auront une normale "HG"
fin si;
sinon si la normale est "H" alors
[...]
// Pareil pour les 8 valeurs possibles de la normale.
fin si;
fin pour chaque; // pour chaque point de L
fin pour chaque; // pour chaque segment de S
recommencer tant qu'on a découpé au moins un segment; |
Je sais qu'on doit pouvoir faire plus optimisé en ne retestant pas à chaque fois les segment qu'on a pas réussi à couper au précédent passage.
Et puis je ne sais pas si c'est une bonne idée de modifier S à l'interieur de la boucle Pour chaque segment seg de S.
Par contre pour la triangulation, j'ai pas vraiment d'algorithme qui donne une triangulation même non optimale.
