Enveloppe convexe morphologie mathématique

**comrad85** · 13/03/2008, 21h32

Salut a tous! Je dois programmer l'algorithme de l'enveloppe convexe. J'ai cherché sur le net et j'ai trouvé que c'est une série d'epaississement qu'on doit itérer jusqu'à idempotence. J'utilise le masque suivant:
0 0 0
* 0 *
1 1 1
mais je crois que l'algorithme boucle infiniment!!
Si quelqu'un a une petite idée ca serait sympa de m'aider
Merci à vous

**ToTo13** · 14/03/2008, 10h08

Bonjour,

je n'ai jamais fait d'épaississement

Mais ce masque est un de ceux utilisé pour faire des amincissements :s J'ai un doute sur le fait que ce soit les mêmes. D'où tiens tu ce masque ? Peux tu nous montrer le lien ?

Pour ce qui est de faire le calcul de l'enveloppe convexe, il y a deux algorithmes très simples à programmer et très rapide au niveau complexité O(N Log N) : Marche de Graham ou Jarvis.
Il y en a un troisième qui consiste à utiliser le principe "Diviser pour régner", mais j'aime beaucoup moins. En gros tu sépares ton nuage de points en sous groupe jusqu'à obtenir des groupes de deux ou trois points que tu fusionnes lors de ta remonté dans l'arbre.
Voilà un lien intéressant contenant la liste de différents algorithmes.
Sur Wikipédia, tu as également trois liens intéressants dont celui d'une heuristique non négligeable.

**comrad85** · 14/03/2008, 11h28

Salut!!merci pour la réponse.
En fait le masque c'est un enseignant qui m'a dit d'essayer celui ci mais il n'est pas sur!!!
C'est le même que celui utilisé pour le squelette en remplaçant seulement l'origine par un 0. Je ne sais pas est ce que c'est le même principe que le calcul du squelette i.e utiliser les 8 rotations a 45°......... C'est ca???
Merci

**ToTo13** · 14/03/2008, 11h33

Bonjour,

oui, il faut aussi utiliser les huit rotations.

**souviron34** · 14/03/2008, 13h44

mais si c'est vraiment l'enveloppe convexe, Graham est le plus rapide et facile à implanter (il y a même les sources un peu partout, y compris dans Sedgewick et Numerical Recipes)

**comrad85** · 14/03/2008, 16h36

Salut je crois que c'est l'enveloppe fortement convexe . J'ai trouvé que c'est une succession d'epaississement jusqu'à idempotence, et ca preserve l'homotopie!!
Je vais voir l'algorithme de Graham.
Merci

**comrad85** · 14/03/2008, 21h55

Salut!! J'ai un petit problème.

Je ne sais pas comment utiliser l'algorithme de Graham dans le main. J'utilise comment l'entier retourné par la fonction chainHull_2D???
Merci

désolé! Je voulais dire l'enveloppe quasi convexe

Merci

**ToTo13** · 17/03/2008, 12h49

Bonjour,

je ne sais pas qu'elle implémentation d'algo tu as adopté, mais si tu veux une réponse, il serait sans doute bien que tu nous donnes un lien ou un peu de code

**comrad85** · 17/03/2008, 18h35

Salut!!ben j'ai utilisé le lien que tu m'as donné :
lien
c'est la dernière partie : implémentation en c++
Merci

**ToTo13** · 18/03/2008, 10h52

Bonjour,

j'aurais tendance à dire que c'est le nombre de point constituant l'enveloppe convexe.

**souviron34** · 18/03/2008, 13h19

tu as raison, je n'ai pas regardé le code pointé, mais d'après la question et les autres algos, c'est en général bien le nombre de points présents dans l'enveloppe (souvent les algos trient et modifient le tableau d'entrée).

**pseudocode** · 18/03/2008, 15h58

Y a que sur mon navigateur que le commentaire du code est affiché ?!?

Code C :

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

1
2
3
4
5
6
7
8
9
10
// chainHull_2D(): Andrew's monotone chain 2D convex hull algorithm
//     Input:  P[] = an array of 2D points 
//                   presorted by increasing x- and y-coordinates
//             n = the number of points in P[]
//     Output: H[] = an array of the convex hull vertices (max is n)
//     Return: the number of points in H[]
int chainHull_2D( Point* P, int n, Point* H ) {
 /* ... */
}