Problème de structure de données

Version imprimable

05/07/2010, 14h09
regliss76

Problème de structure de données

Bonjour,
j'ai un problème de C++ qui est en fait un problème d'algorithmique, enfin je le crois.
Dans mon programme, pour un mur donné, je crée un tableau contenant le nom de chacune des zones auxquelles il est lié (j'appelle cela des connexions).
Un mur peut être lié plusieurs fois à une zone.
Par exemple pour un mur X, j'ai le tableau : 1 | 1 | 1 | 3 | 3 | 4 |
(Donc mon mur X est lié 3 fois à la zone 1, 2 fois à la zone 3 et une fois à la zone 4.)
A chaque connexion est associée une liste de points représentant le polygone de la connexion (j'ai créé la fonction me retournant la liste de points associée à la connexion en position n° i dans le tableau ci-dessus).
Mon but est de fusionner les polygones relatifs à une même zone (la zone 1 et la zone 3 dans mon exemple). Il y a donc une histoire de comparaison de chaînes de caractères.
J'ai mon algorithme d'union de deux polygones (donc pour N polygones il va falloir faire ça récursivement je pense).
Mon problème : je ne sais pas comment m'y retrouver dans tout cela, i.e. comment organiser mon code et utiliser les structures de données appropriées.
Merci de votre aide !
05/07/2010, 14h27
Invité

Bonjour,

C'est pas très clair, "un mur est lié à une zone". Par exemple, si un mur est posé par terre, il est lié au sol avec la zone de contact entre le mur et le sol ?

Et ça n'a aucun sens qu'un mur puisse être lié plusieurs fois avec la même surface.
05/07/2010, 14h52
regliss76

La notion de zone n'est pas assez explicite, désolé. Une zone = une pièce. Donc si mon mur sépare le hall d'entrée de la cuisine et de la chambre, j'ai 3 connexions. Le fait que je puisse avoir plusieurs connexions avec la même pièce vient du fait que la connexion est géométrique, et que la façon dont le logiciel d'architecture exporte le modèle au format IFC (format sur lequel je travaille) n'est pas simple.
05/07/2010, 15h53
Invité

Ok, c'est déjà un peu plus clair.

Dans ton exemple (pour un mur X, j'ai le tableau : 1 | 1 | 1 | 3 | 3 | 4 |), si tu as déjà l'algo pour fusionner deux polygones, il suffit d'appliquer cet algo sur les deux premières connexions, puis sur les deux premières connexions fusionnées et la troisième, et enfin sur la quatrième et la cinquième.

Il y a une phrase de ton premier post qui reste floue :

Citation:

Il y a donc une histoire de comparaison de chaînes de caractères.

Tu peux détailler un peu plus ?

J'ai avancé sur mon problème. Au lieu de construire un tableau comme précédemment, j'ai fait un vector de string (plus facile). Puis j'ai réussi à partir de ce dernier à construire un vecteur de Connex, où Connex est une structure contenant :
- un string s (genre "1" pour zone 1)
- un vecteur d'entiers tab contenant la liste des positions des connexions associées à cette zone (en partant de 0).
En reprenant mon exemple j'ai donc :
1 -> 0-1-2
3 -> 3-4
4 -> 4
Il me faut maintenant, pour chaque Connex de mon vecteur, calculer l'union des polygones formés par les listes de points associées à chaque indice du tab correspondant.

Citation:

Il y a une phrase de ton premier post qui reste floue :
Citation:
Il y a donc une histoire de comparaison de chaînes de caractères.
Tu peux détailler un peu plus ?

Bien sûr. Pour construire le vecteur de Connex j'ai dû comparer les chaînes contenues dans mon vecteur de string.
Voici mon code pour ceux que ça intéresse :
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 32 33 vector<Connex> fusion(Step::RefPtr<ifc2x3::IfcWallStandardCase> mur,vector<string> tab_connexions) { vector<Connex> v_connex; string temp,temp2; int i=0,j; vector<string>::iterator iter_tab_conn,iter_tab_conn2; for(iter_tab_conn = tab_connexions.begin();iter_tab_conn!=tab_connexions.end();++iter_tab_conn) { temp = *iter_tab_conn; if(strcmp(temp.c_str(),"done")!=0) { Connex connex_temp; connex_temp.s = temp; connex_temp.tab.push_back(i); j=0; for(iter_tab_conn2 = tab_connexions.begin();iter_tab_conn2!=tab_connexions.end();++iter_tab_conn2) { temp2 = *iter_tab_conn2; if(j!=i && strcmp(temp2.c_str(),temp.c_str())==0) { connex_temp.tab.push_back(j); tab_connexions[j]="done"; } j++; } tab_connexions[i]="done"; v_connex.push_back(connex_temp); } i++; } return v_connex; }

06/07/2010, 12h24
Invité

Bonjour,

Je crois avoir compris ce que tu veux : de l'aide pour implémenter ton algorithme d'union de deux polygones. Si c'est ça, ça pourrait aider d'avoir des renseignements sur l'algo à implémenter (son nom s'il en a un, le document sur lequel tu as vu sa description, ou d'autres ressources).
07/07/2010, 13h58
regliss76

Je vais essayer d'expliquer mon problème qui a évolué et dont je cerne mieux les futures complications.
Pour moi, une liste de points = un polygone quelconque, puisque les points de la liste définissent le contour du polygone. Donc quand j'écris polygone comprenez liste de points.

Ma structure Connex :
- une string s = nom de la zone connectée
- un vecteur d'entier contenant les positions des connexions polygonales associées à cette zone (j'ai la méthode pour obtenir le polygone relatif à tel entier).
Pour un mur X j'ai donc un vecteur de Connex. Je reprends mon exemple :
nom---positions
1 --- 0-1-2
3 --- 3-4
4 --- 4

Mon but : pour ce mur écrire le vecteur de PolyFus associé.
Ma structure PolyFus contient :
- une string s = nom de la zone connectée (identique à celle de Connex donc)
- un vecteur de polygones (ou vecteurs de listes de points).
Il se peut que pour une zone donnée, des polygones soient "isolés" et d'autres "s'unissent". J'entends par "isolé" qui ne s'intersecte ni n'est tangent avec personne. Par exemple, pour la connexion du mur X avec la zone "1", le polygone 0 peut s'unir avec personne et les polygones 1 et 2 peuvent s'unir. Donc dans ce cas je veux obtenir dans mon vecteur de polygones de PolyFus :
- polygone 0
- union(polygone 1, polygone 2)

J'ai écrit une fonction qui à partir de deux polygones, me retourne un vecteur de polygones qui est de taille 1 ou 2. Je m'explique : si les 2 polygones sont disjoints, la solution retournée par l'algo d'Angus Johnson est le vecteur contenant les 2 polygones inchangés (taille 2), s'ils s'intersectent ou sont tangents, la solution est le polygone union (taille 1).

Problème : je dois faire ça par récurrence je pense mais je ne vois pas comment l'écrire...

J'ai fait un algo simple en O(n²) qui utilise les listes chainées.

Exécutons cet algorithme sur une liste de 5 polygones :

Code:

[ p1, p2, p3, p4, p5 ]

p1 et p4 peuvent s'unir.
p2 et p4 peuvent s'unir.

Début de l'exécution.

p1 peut s'unir avec p2 ? non
p1 peut s'unir avec p3 ? non
p1 peut s'unir avec p4 ? oui
suppression de p1 et union de p1 et p4 pour donner p41
la liste est maintenant

Code:

[ p2, p3, p41, p5 ]

p2 peut s'unir avec p3 ? non
p2 peut s'unir avec p41 ? oui
suppression de p2 et union de p2 et p41 pour donner p412
la liste est maintenant

Code:

[ p3, p412, p5 ]

p3 peut s'unir avec p412 ? non
p3 peut s'unir avec p5 ? non

p412 peut s'unir avec p5 ? non

Fin de l'exécution.

S'il y a quelque chose que tu ne comprend pas dans le code, demandes moi :
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 32 #include <iostream> #include <list> using namespace std; void union_globale(list<Polygone> polygones) { list<Polygone>::iterator polygone_teste = polygones.begin(); list<Polygone>::iterator dernier_polygone = polygones.end(); for (; polygone_teste <= dernier_polygone; ++polygone_teste) { union_simple(polygone_teste, polygones); } } void union_simple(list<Polygone>::iterator polygone_teste, list<Polygone> polygones) { list<Polygone>::iterator polygone_courant = polygone_teste; ++polygone_courant; list<Polygone>::iterator dernier_polygone = polygones.end(); Polygone nouveau_polygone; for (; polygone_courant <= dernier_polygone; ++polygone_courant) { if (polygone_courant == polygone_teste) continue; if (peuvent_s_unir(polygone_courant, polygone_teste) { nouveau_polygone = UNIR(polygone_courant, polygone_teste); polygones.erase(polygone_teste); polygone_courant = polygones.erase(polygone_courant); polygones.insert(polygone_courant, nouveau_polygone); break; } } }

Merci pour ton aide.
Je ne comprends pas le bout de code suivant :

Code:

1
2
3
4
 
polygones.erase(polygone_teste);
polygone_courant = polygones.erase(polygone_courant);
polygones.insert(polygone_courant, nouveau_polygone);

D'autre part je n'ai pas de fonction de comparaison de polygones pour

Code:

1
2
 if (polygone_courant == polygone_teste)
      continue;

Mon algo à moi est en O(n^3) mais bon :

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
vector<ifc2x3::List_IfcCartesianPoint_2_n> calculv_lp(Step::RefPtr<ifc2x3::IfcWallStandardCase> mur, vector<int> tab)
	{
	vector <ifc2x3::List_IfcCartesianPoint_2_n> resultat;
	vector <Liste_de_points> travail;
	vector <int>::iterator iter_int;
	vector <Liste_de_points>::iterator iter_pol,iter_pol2;
 
	travail.reserve(tab.size());
	resultat.reserve(tab.size());
 
	//inclusion des polygones dans le vecteur de travail
	for(iter_int=tab.begin();iter_int!=tab.end();++iter_int)
		{
		Liste_de_points liste;
		liste.points = getPoints(mur,*iter_int);
		liste.marque = false;
		travail.push_back(liste);
		}
 
 
	//agrégation par paquets
	iter_pol=travail.begin();
	while(iter_pol!=travail.end())
		{
		if(iter_pol->marque == false)
			{
			ifc2x3::List_IfcCartesianPoint_2_n temp = iter_pol->points;
			for(int j = 0; j < static_cast<int>(travail.size());j++)
				{
				iter_pol2=iter_pol+1;
				while(iter_pol2!=travail.end())
					{
					if(intersectionPoly(temp,iter_pol2->points) && iter_pol2->marque==false)
						{
						temp = unionPoly(temp,iter_pol2->points);
						iter_pol2->marque = true;
						}
					++iter_pol2;
					}
				}
			resultat.push_back(temp);
			iter_pol->marque = true;
			}
		++iter_pol;
		}
 
	return resultat;
	}

Code:

1 2 3 4 nouveau_polygone = UNIR(polygone_courant, polygone_teste); polygones.erase(polygone_teste); polygone_courant = polygones.erase(polygone_courant); polygones.insert(polygone_courant, nouveau_polygone);
Ce code supprime les deux polygones initiaux de la liste des polygones, et insère le nouveau à la place du polygone qui était le plus à droite. Dans le détail :

- La 1ère ligne enregistre l'union de deux polygones.

- La 2ème ligne enlève l'un des deux polygones initiaux (le plus à gauche) de la liste des polygones.

- La 3ème ligne enlève l'autre polygone initial (le plus à droite) de la liste, mais cette fois ci on garde en mémoire la position dans la liste ou l'on se trouve (on stocke cette position dans "polygone_courant").

- La 4ème ligne insère le nouveau polygone à la place du polygone de droite que l'on vient de supprimer. Je me suis aidé de cette page : c++ list insert pour apprendre à remplacer un élément par un autre dans une liste.
Code:

1 2 if (polygone_courant == polygone_teste) continue;
Ça c'est juste une comparaison basique entre deux pointeurs, pour que les deux polygones soient égaux, ils faut qu'ils aient la même adresse mémoire.
:oops: :oops: :oops: D'ailleurs il faut supprimer ce morceau de code, il ne sert à rien (le polygone testé est le plus à gauche donc le polygone courant ne passera jamais par dessus). Désolé j'ai oublié de l'enlever.

--------------------------------------------------------------------

Ce qu'il faut voir dans l'algo que j'ai proposé, c'est qu'à tout instant, ce qui est à gauche du polygone courant est déjà traité, on ne regardera plus jamais de ce côté là. Ce qui est à droite sont les polygones qui peuvent peut-être s'unir avec le polygone courant.

Au milieu de l'algo, on regarde si le polygone courant peut s'unir avec un autre à sa droite.
- Si c'est non, alors on ne s'occupe plus de lui, il passe à gauche, et c'est le polygone juste à sa droite qui devient le polygone courant.
- Si c'est oui, alors il reste à droite car on l'envoie fusionner avec le polygone de droite. Et c'est le polygone qui était juste à sa droite qui devient le polygone courant.

La complexité est de (n²)/2. Par rapport à du n³ ça fait quand même une différence.

12/07/2010, 09h07
regliss76

Merci pour ces explications, malheureusement lors de l'exécution (ça compile sans problème), j'ai un message d'erreur lié à l'utilisation de vector (oui j'ai des vector et non des list, j'ai modifié). Cela est lié à l'effacement d'un polygone dans une boucle for, et c'est ce qui m'avait poussé dans ma méthode à utiliser des marquages avec des booléens plutôt que d'effacer directement pendant l'itération.

J'ai un peu modifié le code mais j'ai encore des problèmes à l'exécution...:(

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
32
33
/*
méthode qui réalise l'union globale de la liste
*/
void union_globale(vector <ifc2x3::List_IfcCartesianPoint_2_n> polygones) 
	{
	vector <ifc2x3::List_IfcCartesianPoint_2_n>::iterator polygone_teste;
	for (polygone_teste = polygones.begin(); polygone_teste != polygones.end(); ++polygone_teste) 
		{
		union_simple(polygone_teste, polygones);
		}
	}
/*
méthode qui réalise l'union simple d'un élément avec la liste
*/ 
void union_simple(vector <ifc2x3::List_IfcCartesianPoint_2_n>::iterator polygone_teste, vector <ifc2x3::List_IfcCartesianPoint_2_n> polygones) 
	{
	vector <ifc2x3::List_IfcCartesianPoint_2_n>::iterator polygone_courant = polygone_teste;
	++polygone_courant;
 
	ifc2x3::List_IfcCartesianPoint_2_n nouveau_polygone;
 
	for (;polygone_courant != polygones.end();) 
		{
		if (testUnion(*polygone_courant, *polygone_teste)) 
			{
			nouveau_polygone = unionPoly(*polygone_courant, *polygone_teste);
			polygones.erase(polygone_teste);
			polygone_courant = polygones.erase(polygone_courant);
			polygones.insert(polygone_courant, nouveau_polygone);
			}
		else ++polygone_courant;	
		}
	}