Flocon de Koch et liste chainée

Version imprimable

Bonjour,

J'essaie de créer un algo afin de générer un flocon de Koch avec une liste chainée de points, mais j'ai un souci au niveau des pointeurs je pense.

Tout d'abord, voici la structure de point:

Code:

1
2
3
4
5
6
7
8
9
10
 
typedef struct EPOINT EPOINT; 
 
struct EPOINT {
  double x;
  double y;
  struct EPOINT *next;
};
 
typedef EPOINT *PLISTE;

Et celle de Koch :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
/**
 * \brief Structure représentant le flocon de Koch
 * \details Le flocon de Koch est constitué :
 * */
typedef struct Koch Koch; 
 
struct Koch {
	PLISTE points;
	int ordreIteration;
	int echelle;
	int couleurFond;
	int couleurContour;
 
};

La fonction d'ajout, après un point :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
/*
 * Insere un point apres element elt 
 * INPUT: ptr sur element avant insertion, coordonnees du nouveau point
 * OUTPUT: ptr sur element ajoute
 */
EPOINT *insert_after(EPOINT * elt, double xx, double yy){
	//Déclarations
	EPOINT *point, *pTmp;
 
	//MàJ de la liste
	if(elt->next != NULL){
		pTmp = create_point(elt->next->x, elt->next->y, elt->next->next);
		point = create_point(xx, yy, pTmp);
		point->next = pTmp;
		elt->next = point;
	}else{
		point = create_point(xx, yy, elt->next);
		elt->next = point;
	}
 
	return point;
}

et l'algo qui génère le flocon de koch (une iteration) :

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
49
50
51
 
Koch* developperKoch(Koch* this){
	//variables
	EPOINT *pointCourant, *pointSuivant, *pointMilieu, *pointTier1, *pointTier2, *pointEquilateral;
	int continuer;
 
	//declarations
	pointCourant = this->points;
	pointSuivant = pointCourant->next;
	continuer = 1;
 
	//parcourt des points du flocon
	while(continuer == 1){
		//mise en place point premier tier
		pointMilieu = milieu(pointCourant->x, pointCourant->y, pointSuivant->x, pointSuivant->y);
		pointTier1 = milieu(pointCourant->x, pointCourant->y, pointMilieu->x, pointMilieu->y);
		pointTier1 = insert_after(pointCourant, pointTier1->x, pointTier1->y);
 
 
		//mise en place point second tier
		pointTier2 = milieu(pointMilieu->x, pointMilieu->y, pointSuivant->x, pointSuivant->y);
		pointTier2 = insert_after(pointTier1, pointTier2->x, pointTier2->y);
 
		//mise en place point formation equilateral
		pointEquilateral = equilateral(pointTier1->x, pointTier1->y, pointTier2->x, pointTier2->y);
		pointEquilateral = insert_after(pointTier1, pointEquilateral->x, pointEquilateral->y);
		printf("pointCourant : %lf ; %f \n", pointCourant->x, pointCourant->y);
		printf("pointTier1 : %lf ; %f \n", pointTier1->x, pointTier1->y);
		printf("pointEQUILATERAL : %lf ; %f \n", pointEquilateral->x, pointEquilateral->y);
		printf("pointTier2 : %lf ; %f \n", pointTier2->x, pointTier2->y);
		printf("pointSuivant : %lf ; %f \n", pointSuivant->x, pointSuivant->y);
 
		//repositionnement sur le segment suivant
		if(pointSuivant->next == NULL){
			pointCourant = pointSuivant;
			pointSuivant = this->points;
			continuer=0;
		}else{
			printf("tttttggggggg\n");
			pointCourant = pointSuivant;
			pointSuivant = pointSuivant->next;
		}	
 
	}	
		printf("pointCourant : %lf ; %f \n", pointCourant->x, pointCourant->y);
		printf("pointTier1 : %lf ; %f \n", pointTier1->x, pointTier1->y);
		printf("pointEQUILATERAL : %lf ; %f \n", pointEquilateral->x, pointEquilateral->y);
		printf("pointTier2 : %lf ; %f \n", pointTier2->x, pointTier2->y);
		printf("pointSuivant : %lf ; %f \n", pointSuivant->x, pointSuivant->y);
	return this;
}

En fait, ça m'ajoute les bon points mais que sur le premier segment. Quand il passe au segment suivant, j'ai les bonnes coordonnées (avec printf()) mais ils ne s'insèrent pas dans la liste.
On dirait qu'il saute le "insert_after()" après le premier segment.

Merci d'avance

Plop !

Je vais détailler pas à pas une démarche pour créer le flocon de Koch
(en essayant de faire le moins de faute possible :( )

Je vais garder l'idée d'une liste chaînée.
On pourrait utiliser une liste chaînées simple non circulaire.
et que deux point successifs d'une liste définisse un segment.

déjà je définis mes structure (pour pas que je sorte des trucs du nul-part )

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
struct Point Point;
struct Point
{
 double x,y;
};
 
typedef struct ElemListePoint ElemListePoint;
struct ElemListePoint
{
 Point data;
 ElemListePoint* next;
};
 
typedef struct ListePoint ListePoint;
struct ListePoint
{
 int nbpoint;
 ElemListePoint* debut;
};

ensuite quelques fonctions pour la gestion des points

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
//précalcul
#define COS_60= (0.5)
#define SIN_60= (0.866025403784438646764)
 
void rotationPoint_60(const Point* centre,const Point* p,Point* result)//p=rotation de 60° dans le sens trigo par rapport au centre
{
 Point tmp={p->x-centre->x,p->y-centre->y};//on ramène le centre à 0
 c*x+s*y -s*x+c*y
 tmp.x=COS_60*p->x+SIN_60*p->y;
 tmp.y=COS_60*p->y-SIN_60*p->x;
 tmp.x+=centre->x;
 tmp.y+=centre->y;
 *result=tmp;
}
 
//scale=1 rien,scale=0.5 au milieu scale=0.333 à un tiers etc ...
void homothetiePoint(const Point* a, const Point* b,double scale,Point *p)
{
 p->x=a->x+scale*(b->x-a->x);
 p->y=a->y+scale*(b->y-a->y);
}

code pour la gestion de la liste

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
 
//aucune vérification des paramètre !
void insertDebut_ElemListePoint(ElemListePoint** e)
{
 ElemListePoint* debut=malloc(sizeof(ElemListePoint));
 debut->next=*e;
 *e=debut;
}
//insertion de base
void insertApres_ElemListePoint(ElemListePoint* e,const Point* data)
{
 ElemListePoint* tmp=malloc(sizeof(ElemListePoint));
 tmp->data=data;
 tmp->next=e->next;
 e->next=tmp;
}
 
//initialisation de la liste
void initDefault_ListePoint(ListePoint* liste,double scale,double translation)
{
 Point tmp;
 tmp.x=translation;
 tmp.y=translation;
//je définis un triangle equilatéral
 liste->debut=malloc(sizeof(ElemListePoint));
 liste->debut->next=NULL;
 liste->debut->data=tmp;//recopie
 
 insertDebut_ElemListePoint(&liste->debut,&tmp);//pour le segment final
 tmp.x+=scale;
 insertApres_ElemListePoint(liste->debut,&tmp);//segment final
 
 tmp.x=scale/2+translation;
 tmp.y=translation+*SIN_60*scale;
 insertApres_ElemListePoint(liste->debut,&tmp);//segment final
 
 liste->nbPoint=4;//soit 3 segments
}

et maintenant (enfin ! :p ) une fonction pour calculer un niveau de la fractale !
j'ai un segment A-B il deviendra A-C,C-D,D-E,E-B
J'aurai juste à faire cette opération pour tout segment !

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
 
//un appel = 1 niveau de plus dans la fractale
//il faut que la liste ait au moins 2 points !
void kochGen(ListePoint* liste)
{
 ElemListePoint *cur1,*cur2;//cur1->data et cur2->data définissent un segment
 Point tmp1,tmp2,tmp3;
 for(cur1=liste->debut,cur2=liste->debut->next;cur2;cur1=cur2,cur2=cur1->next)
//ou bien init;while(cur2){...;cur1=cur2;cur2=cur1->next)
 {
  //pour chaque segment
  homothetiePoint(&cur1->data,&cur2->data,2.0/3,&tmp3); 
  homothetiePoint(&cur1->data,&cur2->data,1.0/3,&tmp1);
  tmp2=tmp3;
  rotationPoint_60(&tmp1,&tmp3,&tmp2);
 
  insertApres_ElemListePoint(cur1,&tmp3);
  insertApres_ElemListePoint(cur1,&tmp2);
  insertApres_ElemListePoint(cur1,&tmp1);
  liste->nbpoint+=3;
 //on a maintenant cur1->data ==> tmp1 ==>tmp2 ==> tmp3 ==>cur2->data
 }
}
 
void developperKoch(ListePoint *p,int level)
{
 while(level--)
  koch_gen(p);
}
 
//...
 
int main()
{
 ListePoint koch;
 initDefault_ListePoint(&koch,10,0);
 developperKoch(&koch,5);
}

(j'ai craqué :D )
en esperant pas avoir fait trop de fautes.

en passant pas des fonctions plus simple il sera plus facile après pour débugger (mes fonction d'insertion sont plus facile et je réutilise un maximum mon code)

12/04/2016, 16h52
dalfab
Bonjour,
La fonction effectue bizarrement deux créations dans certains cas, il faut supprimer le if et ne garder que le else. Il ne reste plus que
Code:

1 2 3 4 EPOINT *insert_after( EPOINT *elt , double xx , double yy ) { EPOINT *point = create_point( xx , yy , elt->next ); return elt->next = point; }
21/04/2016, 07h33
sben42
Bonjour,

+1 pour daflab

De plus dans ce if il y a une fuite mémoire sur le elt->next d'origine.
Code:

1 2 3 4 5 6 if(elt->next != NULL){ pTmp = create_point(elt->next->x, elt->next->y, elt->next->next); point = create_point(xx, yy, pTmp); point->next = pTmp; elt->next = point; }
Il faudrait la fonction create_point, pour être sur qu'une erreur ne se glisse pas à cet endroit.

Bon courage!