Discussion :

[Celelibi]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[xxiemeciel]

Salut,

Pour ton algorithme je ne saurais trop te dire si il est optimal ou non, par contre pour la triangulation tu peut chercher les choses suivantes sur le net.

- Triangulation de Delaunay
- Diagramme de Voronoi

Tu trouveras des algorithmes performants.

XXiemeciel

[Celelibi]

En effet j'ai un peu cherché sur google pour la triangulation et j'ai trouvé assez souvent la triangulation de Delaunay, mais j'aurais aimé d'abbord trouver un algorithme moi même puis voir si il diffère beaucoup de ceux qui existe déjà et qui sont très optimaux.

[FrancisSourd]

Le calcul d'une enveloppe convexe se fait en O(n log n), plusieurs méthodes existent d'ailleurs. As-tu calculé la complexité de ton algorithme (je n'ai pas pris le temps de l'analyser)?

[Celelibi]

Brièvement, mon algorithme récupère les points qui ont l'abscice la plus grande, la plus faible, et l'ordonnée la plus grande et la plus faible.
Puis pour chaque segment on parcourt la liste de point si un point est à l'exterieur du polygône alors on rajoute ce point dans le polygône. On recommence tant qu'on a modifié le polygône.

Le calcul de la complexité de cet algo m'a l'air un peu difficile.
Le pire des cas doit être quand tous les points se trouvent sur l'enveloppe convexe.
À mon avis la boucle faire ... tant que doit s'excuter log2(n) fois car à chaque itération le nombre de segment est multiplié par deux.
Comme le nombre de segments double à chaque itération, je dirais que la boucle qui parcours tous les segment s'exécute 2^n fois.
Puis la boucle qui parcours tous les points s'exécute n fois.
Ça fait donc une complexité O(log2(n)*2^n*n) = O(log(n)*2^(n+1)) = O(2^n*log(n))

Bon pas terrible.
En même temps je ne suis pas du tout sûr de moi pour la complexité de mon algo.

[FrancisSourd]

Brièvement, mon algorithme récupère les points qui ont l'abscice la plus grande, la plus faible, et l'ordonnée la plus grande et la plus faible.
Puis pour chaque segment on parcourt la liste de point si un point est à l'exterieur du polygône alors on rajoute ce point dans le polygône. On recommence tant qu'on a modifié le polygône.

Il faut faire attention, quand on rajoute le point à ce que le polygône reste bien convexe (je n'ai pas bien compris ton pseudo-code): il faut pour cela insérer le point "au bon endroit" et il faut aussi parfois enlever certains points qui étaient dans l'enveloppe convexe et qui deviennent intérieurs en raison de l'ajout du point. Mais sinon, l'idée générale est correcte.

Ainsi ton polygône courant est un polygône dont les sommets sont des points du nuage: il a donc au plus n sommets et n segments. L'insertion d'un nouveau point extérieur peut se faire facilement en O(n), ce qui conduit à un algo en O(n²).

Les algos en O(n log n) sont très jolis, tu en verras sans doute en cours (ou sinon, j'en ai vu sur internet avec des animations en applet).

[Celelibi]

Oui je viens de me rendre compte que mon polygône ne reste pas forcément convexe.
Les algos en O(n log n) je pense pas que j'en verrais ce semestre étant donné que j'ai fini les cours et td d'info.


J'hésite entre résolu et délestage, mais je crois que ça va être délestage car mon algo est faux, et n'intérresse personne. D'autant plus que des algos tout faits existent sur le net.