Discussion :

[Don_Q]

Bonjour à tous et à toutes !

Je suis en train d'adapter un code récupéré sur wikibooks : c'est un code qui permet de récupérer l'enveloppe convexe d'un nuage de points. J'ai fait quelques tests sur un tableau de mon cru (10 points faciles dans ce tableau). Voici le code :

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
 
void convex_hull(point_t* points, ssize_t npoints, point_ptr_t** out_hull, ssize_t *out_hullsize)
{
	point_ptr_t* hull;
	ssize_t i, t, k = 0;
 
	hull = *out_hull;
 
	/* lower hull */
	for (i = 0; i < npoints; ++i) {
		while (k >= 2 && ccw(hull[k-2], hull[k-1], &points[i]) <= 0) --k;
		hull[k++] = &points[i];
	}
 
	/* upper hull */
	for (i = npoints-2, t = k+1; i >= 0; --i) {
		while (k >= t && ccw(hull[k-2], hull[k-1], &points[i]) <= 0) --k ;
		hull[k++] = &points[i];
	}
 
	*out_hull = hull;
	*out_hullsize = k ;

Je récupère la taille du tableau "hull" grâce au pointeur "out_hullsize". Dans le main, j'appelle cette fonction de la manière suivante :

Code :

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

1
2
 
convex_hull(points, npoints, &out_hull, out_hullsize) ;

Je mets mon main en entier pour si jamais :

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
int main(int argc, char* argv[])
{
	ssize_t i,j ;
	point_t* points = NULL ;
	ssize_t npoints ;
	point_ptr_t* out_hull = NULL ;
	ssize_t *out_hullsize ;
 
	srand((unsigned int) time(NULL));
	/* définir le nombre de points, par exemple 10 */
	npoints = 10;
 
	/* allouer et remplir tableau */
	points = (point_t*)malloc(sizeof(point_t)*npoints);
 
	points[0].x = 1 ;
	points[0].y = 1 ;
	points[1].x = 2 ;
	points[1].y = 1 ;
	points[2].x = 2 ;
	points[2].y = 5 ;
	points[3].x = 3 ;
	points[3].y = 2 ;
	points[4].x = 4 ;
	points[4].y = 4 ;
	points[5].x = 4 ;
	points[5].y = 7 ;
	points[6].x = 5 ;
	points[6].y = 5 ;
	points[7].x = 6 ;
	points[7].y = 2 ;
	points[8].x = 6 ;
	points[8].y = 3 ;
	points[9].x = 8 ;
	points[9].y = 5 ;
 
	out_hull = malloc( sizeof(point_ptr_t) * (npoints) ) ;
 
	convex_hull(points, npoints, &out_hull, out_hullsize) ;
 
        //J'affiche le résultat : les points formant le contour de mon nuage de points
	for(i = 0 ; i < *out_hullsize ; i++)
	{
		printf("Point contour %d : %f\t%f\n*************************\n",i+1, out_hull[i]->x,out_hull[i]->y) ;
	}
 
	free(points) ;
	free(out_hull) ;
 
	return 0 ;
}

Ce code marche très bien.
Cependant, je veux modifier un peu le code pour ne récupérer que la partie supérieure de mon enveloppe. Mon idée était donc d'ajouter un pointeur lowerhull qui compterait le nombre de point dans la partie inférieure de l'enveloppe dans la fonction "convex_hull", de la maniere suivante :

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
void convex_hull(point_t* points, ssize_t npoints, point_ptr_t** out_hull, ssize_t *out_lower, ssize_t *out_hullsize)
{
	point_ptr_t* hull;
	ssize_t i, t, k = 0;
 
	hull = *out_hull;
 
	/* lower hull */
	for (i = 0; i < npoints; ++i) {
		while (k >= 2 && ccw(hull[k-2], hull[k-1], &points[i]) <= 0) --k;
		hull[k++] = &points[i];
	}
	
	*out_lower = k-1 ;
	
	/* upper hull */
	for (i = npoints-2, t = k+1; i >= 0; --i) {
		while (k >= t && ccw(hull[k-2], hull[k-1], &points[i]) <= 0) --k ;
		hull[k++] = &points[i];
	}
	
	*out_hull = hull;
	*out_hullsize = k ;

Et ensuite le récupérer dans le main exactement comme on l'a fait pour le pointeur "out_hullsize" :

Code :

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

1
2
 
convex_hull(points, npoints, &out_hull, out_lower, out_hullsize) ;

(Je n'ai pas oublié de le déclarer non plus). Et je n'ai droit qu'à un très déprimant <gras>Memory fault (core dumped)</gras> dans le terminal. Je ne sais pas du tout pourquoi, c'est donc pour ça que j'implore votre aide !

J'ai contourné le problème en déclarant un entier normal et non pas un pointeur dans le main, et en envoyant

Code :

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

1
2
 
convex_hull(points, npoints, &out_hull, &out_lower, out_hullsize) ;

mais ca ne m'explique toujours pas pourquoi j'ai mal fait ce que j'ai essayé de faire avant.

Merci pour votre aide !

DQ