Discussion :

[anis007]

je travaille sur un projet en c++ qui permet de vectoriser des images
dans un 1er temps j'obtient un ensemble de polygone(ca represente les surfaces constituant l'image bitmap d'origine)
dans le second je cree un arbre generale representant la hierarchie des polygones deja obtenu.
cette hierarchie traduit les relations d'inclusion entre polygones
exemple:
P:noeud
F1,F2,F3,....Fn:les noeuds fils de P
la relation entre P et Fi signifie pour tous les i=1..n Fi est inclu dans P


Mon probleme c'est d'optimiser la creation de cette hierarchie puisque à partir d'un certains nombre de polygones obtenu à partir de la phase 1 . la creation de hierarchie prend un temps fou

est ce que quelqu'un à une ideeeeeeeeeeeeeeee?

Merci

[Médinoc]

Déjà, comment la crées-tu, ta hiérarchie ?
Et ton arbre, comment est-il au niveau objet ? Chaînage simple ? Double ? Chaînage entre fils ? Cousu ?

Et qu'appelles-tu exactement un polygone inclut dans un autre ? C'est un polygone dont tous les sommets sont dans l'autre ? Es-tu sûr que ce n'est pas ce calcul-là qui prend le plus de temps ?
Les polygones, sont-ils convexes ou ont-ils le droit d'être convaves ? (oui, je suis sûr que cela compte dans un algorithme).

Pour commencer, tu devrais prendre un logiciel profiler et y faire tourner ton code, pour repérer les traitements les plus lents...

[anis007]

Déjà, comment la crées-tu, ta hiérarchie ?
Rep:
pour creer la hierarchie :
je parcours la liste des polygons
soit N le noued courant et P le nouveau poly à insere

si P est inclu dans N alors N->fils->Inserer(P) fin
si N est inclu dans P alors reparenter(P,N) ;//phase de reparentage fin
sinon P->frere->inserer(N); fin

Et ton arbre, comment est-il au niveau objet ? Chaînage simple ? Double ? Chaînage entre fils ? Cousu ?
Rep:
c'est un arbre generale
struct Arbre{
Polygon *PolyCourant
Fils *Arbre
Fils *Arbre
}

Et qu'appelles-tu exactement un polygone inclut dans un autre ? C'est un polygone dont tous les sommets sont dans l'autre ? Es-tu sûr que ce n'est pas ce calcul-là qui prend le plus de temps ?
Rep:

P et Q Polygons
P est inclu dans Q si tous les sommet de P sont inclu dans la surface representer par le polygone Q (La surface de P est Inclu dans la surface de Q)

Les polygones, sont-ils convexes ou ont-ils le droit d'être convaves ? (oui, je suis sûr que cela compte dans un algorithme).

les polygones sont quelconques

le traitement qui prend le plus de temps est celui du test d'inclusion entre polygones
une autre variable qui entre en jeu c'est le nombre trés important de polygones à hierarchiser (à partir d'un nobre >2000 polygons la hierarchisation devient hyper lente) il faut savoir que je travail sur des images trés grandes (pas moins de 4000*4000 pixels)

[Médinoc]

pour creer la hierarchie :
je parcours la liste des polygons
soit N le noued courant et P le nouveau poly à insere

si P est inclu dans N alors P->fils->Inserer(N);

Es-tu sûr de ton "alors", là ?
Et si P est inclus dans un polygone inclus dans N ?

[anis007]

Déjà, comment la crées-tu, ta hiérarchie ?
Rep:
pour creer la hierarchie :
je parcours la liste des polygons
soit N le noued courant et P le nouveau poly à insere

si P est inclu dans N alors N->fils->Inserer(P) fin
si N est inclu dans P alors reparenter(P,N) ;//phase de reparentage fin
sinon P->frere->inserer(N); fin

c'est un traitement recursive , c'est un parcours en profondeur jusqu'a ce que il soit le derniers frere ou le derniers fils d'un noeud de l'arbre

le chainage est simple