Programme de création d'une enveloppe convexe
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 :D
Voici la fonction qui permet d'obtenir l'enveloppe convexe :
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
|
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:
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 :D 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:
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
