Discussion :

[Butterfly83]

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.

[koala01]

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

[Butterfly83]

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...

[koala01]

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 ", 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

[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:

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
 
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 :

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

HeapSort(tre,Th.nt*3 );

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


Voilà, thanks.

[Médinoc]

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?