Discussion :

[Tokapi]

En fait le circuit électronique qu'on veut représenter planairement est exactement le problème de base en effet, mais en l'occurrence ce n'est pas vraiment le sujet qui me préoccupe.

Mais la forme de problème est le même : on ne connait pas les positions des sommets du graphe.

Pour l'instant j'en suis là : Apparemment pour créer un graphe maximalement planaire (triangulé) il faut commencer par définir ses faces, ce qui revient à trouver une représentation planaire du graphe. Du coup, ça se mord un peu la queue, vu que j'essaie justement de le trianguler pour en déduire une représentation planaire.

Donc pour l'instant la seule chose que je vois est l'algorithme de Pigale que j'ai donné plus haut : ajouter des arrêtes au hasard et tester si le graphe est planaire à chaque fois, mais il doit bien y avoir un moyen de faire ça de manière moins bourrine sans en passer par un algorithme de planarisation...

[anapurna]

salut

petite question peut tu mettre ta liste d’éléments et de contact dans une matrice
si oui le reste est simple a mettre en place

[Tokapi]

Salut,

Effectivement je le peux, mon graphe d'origine est codé dans une matrice d'incidence, mais je ne vois pas du tout comment le reste peut être simple à mettre en place pour autant !

[anapurna]

Salut

pour l'affichage a partir d'une matrice tu as plusieurs possibilités
soit tu défini arbitrairement un pas en largeur et en hauteur
tu parcours ta matrice et à chaque incrément tu calcul la position

Code x :

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

1
2
3
4
5
6
7
8
9
10
 
 Pour i:= 0 to nbLigne Faire 
 debut 
    H = i*PasHaut; 
    Pour j:= 0 to nbcol Faire 
        C = j*PasLarg;
        // ici C,H te donne une position géographique arbitraire
    debut 
    Fin
 Fin

soit tu connais la largeur de tes éléments et tu adjoin un Gap entre chaque
le principe est presque le même c'est a dire que tu parcours ta matrice

Code x :

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
 H =0;  
 Pour i:= 0 to nbLigne Faire 
 debut 
    Htmp =MAT[i,0].HAUTEUR+gap 
    H = H+Htmp;
    C = 0;
    Pour j:= 0 to nbcol Faire 
       SI MAT[i,j].HAUTEUR+gap> Htmp alors  // là on reajuste la hauteur le cas echeant si un element est plus grand
       DEBUT
          dif =  MAT[i,j].HAUTEUR+gap - Htmp
          Htmp = Htmp+dif
          H = H+dif;
       FIN 
        C =C+MAT[i,J].Largeur+gap ;
        // ici C,H te donne une position géographique arbitraire
    debut 
    Fin
 Fin

parcontre la matrice d'incidence n'est pas la matrice a laquelle je pense
effectivement là, il va falloir trouver une solution intermédiaire
car la matrice d'incidence est une matrice représentant les arcs et non les elements
je pense que l'algorithme de tremeaux-tarjan devrais pouvoir te fournir ta matrice d’élément
c'est à approfondir
en espérant t'avoir eclairé