Utilisation de la fonction HeapSort (algorithme de tri)

Bonjour à tous,
Alors là je suis en train de me prendre la tête pour trier des arrêtes d'un maillage.
En fait, le but du jeu c'est que, sur un maillage triangulaire, je récupère toutes les arrêtes du maillage. Mon idée est de récupérer les trois arrêtes de chaque triangle et ensuite d'enlever les doublons (le maillage est évidemment conforme).
Chacune des arrêtes est définie par deux points A et B par exemple numérotés par le couple (a, b)

Pour enlever les doublons mon idée était de trier les a par exemple (avec la fonction HeapSort) et après il est facile par comparaison des lignes successives du tableau d'enlever les doublons.

Problème je peux trier les a mais comment garder le b qui forme un couple avec a?

Si quelqu'un a une idée...
Merci.

Salut,

Rend a et b dépendants l'un de l'autre...

Soit en créant une structure particulière qui représente une arrête (mais dont la comparaison pour le tri ne s'intéresse qu'à a), soit, pourquoi pas, en utilisant tout simplement une std::pair, dont le premier élément serait a et le second serait b ;)

[EDIT]l'avantage d'une "spécialisation" de la std::pair, c'est que, si tu te sert de cette spécialisation comme clé d'un conteneur associatif (set ou map), il ne pourra plus y avoir que une seule fois [point1, point2] dans l'ensemble (mais [point2,point1] reste possible :p)

Dés lors, le simple fait d'ajouter les différentes arrêtes dans le conteneur supprimera les doublons ;)

Mais sous-entend que tu as un predicat "less" pour ton point ;)

Tout d abord merci pour tes réponses. Ensuite, pourquoi il n y aurait plus de doublons en utilisant ta méthode?? Et qu est ce qu un prédicat "less"?

Merci...

Parce que le propre des conteneurs associatifs est que leur clé est unique...

Pour te permettre de savoir ce qu'est un prédicat, je préfère te réorienter vers l'entrée de la FAQ correspondante, ainsi que vers l'entrée précédente.

Si je te parle de "less", c'est parce que les différents algorithmes de tri de la STL utilisent ce prédicat particulier, qui signifie "plus petit", pour travailler.

Il faut noter que c'est le seul prédicat réellement utilisé, ainsi, la STL considère que:

• Si a n'est pas plus petit que b et que
• b n'est pas plus petit que a alors
• a est égal à b

Dés lors, si tu permet à ton point de répondre à la question "es tu plus petit que l'autre point :question:", ton point pourra servir comme clé dans un conteneur associatif ;)

Il faut cependant prendre en compte le fait que, si tu a deux points a et b, l'arrete [a,b] et l'arrete [b,a] seront être considérées comme étant différentes si elles servent de clé dans une std::pair.

Selon que tu considère que deux arrêtes sont identiques si elle ont seulement la même orientation ou qu'elles sont identiques si elles ont la même orientation et la même direction, il n'est pas impossible que tu doive mettre en place une vérification de l'existence d'une permutation entre a et b ;)

Merci encore.

Mais le fait que deux arretes identiques sont "différentes" selon leurs orientations me dérange un peu... Alors j ai écrit une nouvelle version de HeapSort:

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

template<class T> void HeapSort(T *c,long n) // on a un tableau sur lequel on travaille par adresse memoire { long l,j,r,i; T crit; c--; // on decale de 1 pour que le tableau commence a 1 if( n <= 1) return; l = n/2 + 1; r = n; while (1) { // label 2 if(l <= 1 ) { // label 20 crit[0] = c[r][0]; c[r--][0] = c[1][0]; crit[1] = c[r][1]; c[r--][1] = c[1][1]; if ( r == 1 ) { c[1][0]=crit[0]; c[1][1]=crit[1]; return;} } else {crit[0] = c[--l][0]; crit[1] = c[--l][1]; } j=l; while (1) {// label 4 i=j; j=2*j; if (j>r) {c[i][0]=crit[0]; c[i][1]=crit[1]; break;} if ((j<r) && (c[j][0] < c[j+1][0])) j++; // L5 if (crit[0] < c[j][0]) { c[i][0]=c[j][0]; c[i][1]=c[j][1]; } else {c[i][0]=crit[0];c[i][1]=crit[1]; break;} }

---

Mais ça ne marche pas, mon tableau est modifié mais ça n a ni queue ni tête!

Peut être que l ereur vient aussi de l appel à HeapSort qui est bancal aussi:

Code:

---

HeapSort(tre,Th.nt*3 );

---

tre: triangle edge
Th.nt : nombre de triangles du maillage


Voilà, thanks.:aie:

Citation:

---

Envoyé par Butterfly83

Merci encore.

Mais le fait que deux arretes identiques sont "différentes" selon leurs orientations me dérange un peu... Alors j ai écrit une nouvelle version de HeapSort:

---

Réécrire la fonction de comparaison ne suffirait-il pas?

En plus, si tu part sur le principe d'une classe qui va se charger de gérer les différentes arrêtes sur base de ce que je te propose, cela peut très bien tourner sur quelque chose de relativement simple... meme si on en vient à oublier le heapsort :p

Je m'explique:

Tu part sur une classe (ou une structure) Point "classique", avec un foncteur permettant de déterminer si un point est plus petit qu'un autre (le fameux predicat "less" ;))

Tu crée, pour la facilité, un alias

Code:

---

typedef std::pair<Point,Point> Arrete;

---

qui te permet de représenter une arrête avec son point "de départ" et son point "d'arrivée".

la création d'une arrête sous cette forme se fait sous la forme de

Code:

---

Arrete obj=std::make_pair(point1, point2);

---

Tu crées ensuite une classe "GestionnaireArrete" (par exemple) qui se structure sous une forme proche de

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

class GestionnaireArrete { public: /* les alias qui permettent d'utiliser notre gestionnaire comme les   * coneteneurs classiques ;)   */ typedef std::set<Arrete>::iterator iterator; typedef std::set<Arrete>::const_iterator const_iterator; GestionnaireArrete(){}//rien à faire ~GestionnaireArrete(){}//sympa, tout se fait automatiquement ;) void insertArrete(const Arrete&); // pourrait renvoyer l'arrete ;) iterator& begin(); //pour obtenir la première arrete iterator& end(); //quand on arrive à end, on a vu toutes les arretes ;) iterator& operator++();//permet de passer à l'élément suivant private: std::set<Arrete> allar;//va contenir toutes les arretes ;) iterator ite; };

---

La méthode intéressante est insertArrete car pour begin(), il suffit d'initialiser ite à allar.begin() et de renvoyer it, pour end(), il suffit de renvoyer allar.end(), et, pour operator++, il suffit d'incrémenter ite et de le renvoyer (rien de particulier, en somme ;))

Toi, tu voudrais qu'avec deux points (p1 et p2, pour l'exemple), les arrêtes créées sous la forme de

Code:

---

1 2	Arrete ar1=std::make_pair(p1,p2); Arrete ar2=std::make_pair(p2,p1);

---

soient considérées comme étant identiques :P

La solution est relativement simple: dans la méthode insertArrete, il *suffit* de vérifier la présence de la permutation (autrement dit d'une arrête [p2,p1] pour ar1 ou d'une arrete [p1,p2] pour ar2 ;)

Cela peut se faire très facilement en implémentant la méthode sous la forme de

Code:

---

1 2 3 4 5

void GestionnaireArrete:: insertArrete(const Arrete& toadd) { if(allar.find(std::make_pair(toadd.second,toadd.first))==allar.end()) allar.insert(toadd); }

---

ou, si tu préfères un code un peu plus verbeux sous la forme de

Code:

---

1 2 3 4 5 6 7 8

void GestionnaireArrete:: insertArrete(const Arrete& toadd) { /* création de l'arrête "permutée" */ Arrete temp=std::make_pair(toadd.second, toadd.first); /* on insere l'orginal si on ne trouve pas la permutation */ if(allar.find(temp)==allar.end()) allar.insert(toadd); }

---

En quelques lignes à peine, tu obtiens quelque chose qui sera sans doute bien plus efficace que ton HeapSort ;)

Dépêche-toi de corriger cette faute d'orthographe affreuse : arrête -> arête ! :aie:

Citation:

---

Envoyé par HanLee

Dépêche-toi de corriger cette faute d'orthographe affreuse : arrête -> arête ! :aie:

---

Hé bien non, tiens... j'ai décidé d'arrêter mes arêtes :D

Merci pour vos réponses.

Sinon, en quoi la complexité de ton algorithme serait moins grande? HeapSort étant en O(nlog(n)) opérations?

Merci.

Je n'ai pas dit que la complexité serait moins grande, étant donné que la recherche se fait également en O=log(n).

Ce que je sous-entend, c'est que, du point de vue de l'écriture, tu t'évites une série de problèmes grâce à la gestion dynamique automatique de la mémoire des conteneurs de la STL, que tu obtiens un code plus compact, plus sécurisé, et, au final, plus facilement compréhensible que si tu dois écrire ta fonction HeapSort à la main...