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

[kwariz]

Bonjour,

Quand tu déclares un pointeur :

Code :

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

ssize_t *ptr;

tu ne déclares qu'un pointeur sans pour autant allouer la mémoire où sera stocké la valeur. Ton pointeur pointe n'importe où. Pour l'allouer un malloc suffit :

Code :

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

ptr=malloc(sizeof(*ptr));

maintenant ptr pointe vers un endroit qui sera réservé et utilisable (évidemment, il ne faudra pas oublier d'utilsier free pour libérer cet espace).
Ton premier jet fonctionne : c'est un coup de bol (il est tombé en marche), bien que tu utilises un espace mémoire non réservé ... Tu en rajoutes un, et hop, il tombe en panne car tu accèdes illégalement à un espace mémoire que tu n'as pas réservé. Ce genre de bug est facile à débusquer avec des outils comme valgrind.

Dans ton second jet, tu déclares directement des variables de type ssize_t, de l'espace leur est automatiquement alloué sur la pile, donc leur adresse est valide : plus de bug.

[Don_Q]

L'énigme est résolue !

Mon premier code marchait très bien sans allocation aucune. Comme j'ai "copier-coller" la forme du code original, je n'ai pas alloué mon nouveau pointeur. Il semblerait donc que :

ssize_t *out_lower;
ssize_t *out_lower = (ssize_t*) malloc(sizeof(ssize_t));

Peut-être qu'un jour quelqu'un trouvera une quelconque utilité à ce problème