Discussion :

[hugoenseirb]

Bonsoir à tous et à toutes ! Voilà ce que devrait faire le programme :
-Générer un certain nombre de points appartenant au plan ( de manière aléatoire ) ce nombre est en paramètre de l'exécutable.
-Parcourir ces points et remplir un tableau contenant seulement les points qui forment l'enveloppe convexe des points aléatoirement générés.
Sauf que le résultat est assez ... aléatoire

Voici la fonction qui permet d'obtenir l'enveloppe convexe :

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
 
 
void convex(struct Point S[],int points_number){
  struct Point final_point;
  struct Point point_env={absc,ord};
  int i=1;
 
  while ((P[0].x!=final_point.x) || (P[0].y != final_point.y)) {
    P[i].x=point_env.x;
    P[i].y=point_env.y;
 
    final_point.x=S[0].x;
    final_point.y=S[0].y;
    for(int j=0;j<=points_number-1;j++){
      if ((S[j].x != P[i].x) || (S[j].y != P[i].y )){
 
	if ( ToLeftLine(P[i],final_point,S[j])==1 ){  
	  final_point.x=S[j].x;
	  final_point.y=S[j].y;
	}
      }
       }
    i++;
    PCounter++;
    point_env=final_point;
  }
 
}

Voici la fonction qui vérifie qu'un point est à gauche d'une ligne orientée ( générée par 2 points ) :

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
 
 
 
int ToLeftLine(struct Point A, struct Point B, struct Point C){
  double deltaX=B.x-A.x;
 
  double deltaY=B.y-A.y;
 
  double angle;
  double quotient=deltaY/deltaX;
  double quotient_abs=absoluteValue( quotient );
 
  if(A.x==B.x){
    if((B.y-A.y)>0)
      if(C.x<=A.x) return 1;
      else return 0;
    if ((B.y-A.y)<0)
      if(C.x>=A.x) return 1;
      else return 0;
  }
  if(A.y==B.y){
    if((B.x-A.x)>0)
      if(C.y>=A.y) return 1;
      else return 0;
    if ((B.x-A.x)<0)
      if(C.y<=A.y) return 1;
      else return 0;
  }
  if((B.x-A.x)>0){
    angle= atan( quotient );
 
  }
  if((B.x-A.x)<0){
    if((B.y-A.y)<0){
      angle= atan(quotient_abs)-PI;
 
    }
    if((B.y-A.y)>0){
      angle= -atan(quotient_abs)+PI;
 
    }
  }
  double Y= -(C.x-A.x)*sin(angle) + (C.y-A.y)*cos(angle);
  if (Y>=0) return Y>=0;
  else return 0;
}

Faites moi confiance les fonctions absoluteValue et mostLeft fonctionnent bien mostLeft prends le dernier points le plus à gauche ( dans leur ordre de rangement au sein du tableau de points S ).

Enfin la fonction main qui permet de tester tout ça :

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 
 
 
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<time.h>
 
#define PI 3.141592
#define SIZE_MAX 10
 
 
 
struct Point{
  int x;
  int y;
};
 
int ToLeftLine(struct Point A, struct Point B, struct Point C);
double absoluteValue(double x);
void convex(struct Point S[], int points_number);
int mostLeft(struct Point matrice[], int points_number);
 
struct Point P[SIZE_MAX];
int absc, ord, PCounter;
 
 
 
int main(int argc, char ** argv){
  int points_number;
  points_number= atoi(argv[1]);
  srand(time(NULL));
  struct Point S[points_number-1];     
  printf("\n");
  for (int i=0;i<points_number;i++){   
 
    S[i].x= (int) rand()%50;
    S[i].y= (int) rand()%50;         
    }
for(int k=0;k<points_number;k++){
    printf("S[%d]=(%d;%d)   |   ",k,S[k].x,S[k].y);
  }
  mostLeft(S, points_number);
  P[0].x=absc;
  P[0].y=ord;
    printf("P[%d]=(%d;%d)  \n",0,P[0].x,P[0].y);
  convex(S,points_number);
for(int i=0; i<=PCounter-1; i++){
 printf("P[%d]=(%d;%d)   |   ",i,P[i].x,P[i].y);
 printf("\n");
 }
return 0;
}
 
 
double absoluteValue(double x){
  if (x>=0) return x;
  else return -x;
}
 
 
int mostLeft(struct Point matrice[], int points_number){
  int i=0;
  int compteur;
  absc=matrice[0].x;
  for(i=0;i<=points_number-1;i++){  
    compteur=matrice[i].x;
    if (absc>=compteur){
      absc=compteur;
      ord=matrice[i].y; 
    }
  }
  return 1;
}

Merci infiniment pour ceux qui essaieront de m'aider ! C'est dans le cadre d'un projet et il ne me reste que 2 semaines. On doit encore faire un diagramme de Voronoï et qlques trucs comme ça :S

[ternel]

Nous ne pourrons t'aider que si tu nous donnes aussi les symptômes: qu'attends-tu comme résultat, qu'obtiens-tu?

[diogene]

Déjà, il faut corriger les erreurs manifestes:
*le programme va planter ici :

Code :

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

1
2
3
4
5
6
7
  struct Point S[points_number-1]; 
  printf("\n");
  for (int i=0;i<points_number;i++){   
 
    S[i].x= (int) rand()%50;
    S[i].y= (int) rand()%50;         
    }

Erreur : Le tableau S est sous dimensionné. on devrait avoir struct Point S[points_number];.
Accessoirement, pourquoi ces cast en int ? Ce sont déjà des int. Ne pas utiliser de cast sauf absolue nécessité (et même le cas d'un warning ou d'une erreur n'en est pas une), cela empêche le compilateur de vérifier la cohérence des expressions.

* il peut planter ici dans ToLeftLine() sur une division par 0 : double quotient=deltaY/deltaX;.

* Erreur :

Code :

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

1
2
3
4
void convex(struct Point S[],int points_number){
  struct Point final_point;
.... 
  while ((P[0].x!=final_point.x) || (P[0].y != final_point.y))

final_point non initialisé

Autre remarques :

* Il existe une fonction standard pour calculer la valeur absolue d'un double, fabs(), qui remplacera avantageusement absoluteValue()

* Supprime les variables globales, ce sont des pestes. A n'utiliser qu'en cas d'absolue nécessité. Ce n'est pas le cas de absc, ord, PCounter et P.
PCounter peut être local à main et obtenu par la valeur de retour de convex()
absc et ord peuvent être obtenu en retour de mostLeft() soit par la valeur de l'indice dans matrice[], soit même par retour d'une structure struct Point. Exemple :

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
struct Point mostLeft(struct Point matrice[], int points_number)
{
  int i=0;
  struct Point p = matrice[0];
  for(i=0;i<points_number;i++)  
    if (p.x >= matrice[i].x) p = matrice[i];
  return p;
} 
// dans main()
int main(int argc, char ** argv){
struct Point P[SIZE_MAX];
int PCounter;
...
  P[0] = mostLeft(S, points_number);
  PCounter = convex(S, points_number, P);
...
}
// dans convex()
int convex(struct Point S[],int points_number, struct Point P[])
{
  struct Point point_env=P[0];
  int PCounter = 0;
...
  return PCounter;
}

[hugoenseirb]

Merci à vous pour votre aide ! J'ai apporté quelques modifications et le programme fonctionne. Bonne journée !