Discussion :

[alexis0788]

Bonjour à tous, je suis actuellement en fin de projet informatique en C sur les polygones.
Je touche au but mais la dernière question est, je trouve, vraiment difficile...
Voila, je cherche à détecter dans un polygone non croisé et convexe la présence éventuelle d'un axe de symétrie.
S'il en existe plusieurs, je dois donner au minimum l'équation d'un axe.
Je travaille avec deux structure:

Code C :

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

1
2
3
4
5
6
7
 
typedef struct POINT {char *nom;
                               float abscisse;
                               float ordonnee;
                               struct POINT *succ;} point;
 
typedef struct DROITE {float a;float b;float c;} droite;

Voici les fonctions que j'ai déjà réalisé:

Code C :

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
 
//création d un point
point *newp();
 
//affiche les points
void affichep(point *p);
 
//creer une chaine de points
point *chainep();
 
//calcul du perimetre
void perimetre(point *p);
 
//calcul de l'aire à partir de la formule d'Héron
void aire(point *p);
 
//determine si les deux côtés s'intersectent et renvoie 1 si c'est le cas sinon renvoie 0;
//côtéun=points un et deux; côtédeux=points trois et quatre
int intersection(point *un,point *deux,point *trois,point *quatre);
 
//si le polygone est croisé alors renvoie 1 sinon renvoie 0;
int croise(point *p);
 
//calcule l'angle entre p2p1 et p2p3
float angle(point *p1,point *p2,point *p3);
 
//determine si un angle est saillant (appartient a ]0;90[)
float saillant(point *p1,point *p2,point *p3);
 
//determine si un polygone est convexe:concave(1) si un seul angle est saillant, convexe(0) si tous les angles sont non saillants
int convexite(point *p);
 
//calcule le nombre de points du polygone
int comptepoint(point *p);
 
//resoud un systeme a deux inconnues
point * equasolve(droite d1,droite d2);
 
//donne le point d'intersection de deux mediatrices
point * media_inter(point *p1,point *p2,point *p3);
 
//determine si un point appartient a une droite
int p_appartient(point *centre,point *p1,point *p2);
 
//determine s'il existe le cercle circonscrit
droite cercle_cir(point *p);
 
//determine l'intersection de deux bissectrices
point * bis_inter(point *un,point *deux,point *trois,point *quatre);
 
//determine s'il existe le point de symetrie
point * point_sym(point *p);

Merci de votre aide...

[Zavonen]

Supposons d'abord que le polygones comporte un nombre pair de sommets.
P1 P2 P3 ...... P2k
On commence par faire une partition des sommets en 2
P1 P2 ....Pk
Pk+1 Pk+2 ...P2k
On cherche si la médiatrice de P1Pk+1 est égale à la médiatrice de P2Pk+2, ...,
est égale à la médiatrice de PkP2k
Si oui, c'est gagné l'axe est la médiatrice commune.
Sinon on 'avance d'un cran' par permutation circulaire
On prend la partition
P2 P3 Pk+1
Pk+2 ....P2k P1
et on recommence
et ainsi de suite jusqu'à faire un tour complet (retomber sur la partition d'origine).
Si le nombre de sommets est impair, l'axe passe forcément par un sommet.
Commencer par exclure P1
et voir si:
P2 P3 Pk
Pk+1 P2k-1
s'échangent dans une symétrie d'axe passant par P1
Puis ensuite exclure P2 etc...
PS: Tu auras toujours des problèmes d'arrondis. Il faut donc au départ définir la 'tolérance' un epsilon en dessous duquel on estime que deux réels sont confondus. Sans cela il y aura TOUJOURS échec.

[alexis0788]

Merci de ta réponse je vois a peu près la ou tu veux en venir mais pour coder cet algorithme c'est vraiment trés délicat....
Et j'ai du mal a suivre tout ton raisonnement alors de la à la mettre en pratique....lol
Je ne sais pas trop comment faire car cette fonction est assez énorme à programmer pour moi qui n'en suis qu'à mon premier projet de c.

[Zavonen]

OK !
Je te mâche un peu le boulot:
Traitons seulement le cas d'un nombre pair de sommets.
Commencer par écrire une fonction qui calcule l'équation de la médiatrice d'un segment. Tu prends par exemple I milieu des deux A,B points et tu écris que M est sur cette médiatrice si et seulement si le produit scalaire MI.AB est nul.
Ecrire ensuite une fonction qui teste si deux points sont symétriques par rapport à une droite d'équation donnée. C'est simple si les deux points sont M1(x1,y1) et M2(x2,y2) et si l'équation est ax+by+c les deux nombres ax1+by1+c et ax2+by2+c doivent être opposés.
Avec ça tu écris une fonction qui teste si le polygone A1 A2 A3 ....A2k
est symétrique par rapport à la médiatrice de A1A2. Il suffit donc de calculer la médiatrice de A1A2 puis de vérifier successivement:
A3 symétrique de A2k-1
A4 symérique de A2k-2
.........
Ak+1 sym de Ak+2
Appelons cette fonction sym12( [A1,A2,....An]) qui retourne donc un booléen.
Après tu écris une fonction qui fait tourner d'un cran le tableau [A1,A2,..An]
Puis tu appelles la fonction précédente sur le tableau modifié et ainsi de suite en boucle 2k-1 fois.
En résumé ton programme C aura
4 petites fonctions
Simplement il faut que tu introduise d'entrée une 'tolérance' epsilon à cause des problèmes d'arrondis c'est à dire convenir que M1 et M2 sont symétriques par rapport à la droite D:ax+by+c=0 ssi
ax1+by1+c et ax2+by2+c opposés à epsilon près

[Zavonen]

Pour te mettre le pied à l'étrier voilà un peu de code C qui correspond à mon laïus:

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <stdio.h>
#include <stdlib.h>
 
// la tolerance
const double epsilon=0.001; // par exemple
 
// Pour représenter les points
typedef struct
{
    double x;
    double y;
}
Point;
 
// initialisation d'un point avec ses coordonnées
void InitPoint (double x0, double y0, Point * pP)
{
    pP->x=x0;
    pP->y=y0;
}
// Représentation des droites
typedef struct
{
    double a;
    double b;
    double c;
} Droite;
 
// initialisation des droites par les coefficients
void InitDroite(double u, double v, double w, Droite * pD)
{
    pD->a=u;
    pD->b=v;
    pD->c=w;
}
 
// représentation des polygones
typedef struct
{
    int n ; // nombre de sommets
    Point * Sommets; // tableau des sommets
} Polygone;
 
// initialisation d'un polygone
// à partir d'un tableau de points
void InitPolygone ( int m, Point S[], Polygone * pP)
{
    int i;
    pP->n=m;
    pP->Sommets=malloc(m*sizeof(Point));
    for (i=0;i<m;i++)
        InitPoint(S[i].x,S[i].y,pP->Sommets+i);
}
 
// Calcule la médiatrice d'un segment
Droite Mediatrice (Point A, Point B)
{
    Droite MD;
    double u= 2*(B.x-A.x);
    double v= 2*(B.y-A.y);
    double w= A.x*A.x+A.y*A.y-B.x*B.x-B.y*B.y;
    InitDroite(u,v,w,&MD);
    return MD;
}
 
// détermine si deux points A et B sont symétriques
// par rapport à une droite D
// à la tolérance près
int Symetriques (Point A, Point B, Droite D)
{
    double PAD= D.a*A.x+D.b*A.y+D.c;
    double PBD=D.a*B.x+D.b*B.y+D.c;
    double delta=PAD+PBD;
    return (delta> - epsilon)&&(delta<epsilon);
}
 
// Faire tourner le polygone d'un cran
Polygone Tourne (Polygone Pol)
{
    Polygone T;
    int i;
    T.n = Pol.n;
    T.Sommets=malloc(T.n*sizeof(Point));
    for (i=0;i<T.n-1;i++)
        T.Sommets[i]=Pol.Sommets[i+1];
    T.Sommets[T.n-1]=Pol.Sommets[0];
    return T;
}
 
// test d'un axe de symétrie médiatrice des deux premiers sommets
int Sym01(Polygone Pol)
{
    Droite D=Mediatrice(Pol.Sommets[0],Pol.Sommets[1]);
    int k=Pol.n/2;
    int i;
    for (i=2;i<=k;i++)
        if (Symetriques(Pol.Sommets[i],Pol.Sommets[Pol.n-i],D)==0)
            return 0; // échec
    return 1; // succès
}
 
// test d'un axe de symétrie pour un polygone pair
int SymPair(Polygone Pol)
{
    int i;
    for (i=1;i<=Pol.n;i++)
    {
        Pol=Tourne(Pol);
        if (Sym01(Pol)) return 1; //succès
    }
    return 0; // échec
}
 
int main()
{
 
    return 0;
}

Il te reste à vérifier le programme et à le déboguer au besoin
L'adapter au cas des polygones ayant un nombre impair de sommets.
Dans ce cas tu élimines un à un les sommets, et tu dois tester l'existence d'un axe de symétrie pour le polygone pair restant conjointement avec le fait que le sommet éliminé se trouve sur l'axe. Donc il y a encore du boulot.

[20051438]

Bonjour!
Tout d'abord, merci pour tes réponses Zavonen.
En ce qui concerne ta méthode ça m'a l'air bien compliqué tout ça, il n'y aurait pas une méthode plus simple...

[pseudocode]

Plus simple en terme d'implémentation, ca va être dur.

NB: Intuitivement, je pense q'un axe de symetrie du polygone passe par son barycentre . On doit donc pouvoir limiter le nombre d'axes à tester.

[20051438]

Bonjour
Nous devons seulement trouver un axe de symétrie, ce qui réduit beaucoup la complexité de l'algorithme à écrire...

Je pense qu'en mettant en place un algo de ce type, je dois pouvoir trouvé de façon "assez simple" l'équation d'un axe de symétrie:

if(le nombre de sommets du polygone est pair)
{
l'axe de symétrie passe par une médiatrice donc je trouve l'équation de la médiatrice du premier sommet de mon polygone, puis je regarde si les autres points sont symétriques par rapport à cette droite, etc....
}
else //le nombre de sommets du polygone est impair
{
l'axe de symétrie passe par une bissectrice donc je trouve l'équation de la bissectrice du premier sommet de mon polygone, puis je regarde si les autres points sont symétriques par rapport à cette droite, etc....
}

Qu'en pensez vous??

[pseudocode]

Qu'en pensez vous??

J'en pense que c'est l'algo de Zavonen.

[20051438]

Bonjour!
En fin de compte j'ai un doute lorsque le nombre de sommets du polygone est pair puisque dans le cas d'un carre (qui je le sais est un cas particulier de polygone) les bissectrices et les mediatrices sont axes de symetrie(je ne sais pas si l'orthographe est correcte!!), alors que dans un losange (pas carre), seules les bissectrices sont axes de symetrie; et dans un rectangle, il n'y a que les mediatrices qui sont axes de symetrie...

[Zavonen]

Bien vu !
Cela ne remet pas en cause ma méthode sauf pour la partie 'rotation' qui vise à chercher un axe de symétrie comme médiatrice de deux sommets CONSECUTIFS. L'exemple du losange prouve que l'axe peut être médiatrice de deux sommets non consécutifs.
Il suffit dnc de modifier ainsi l'algo.
Prendre toutes les paires de sommets n(n+1)/2 calculer la médiatrice et tester si l'image de tout autre sommet (non dans la paire) est un sommet (non dans la paire également et pouvant être lui-même). dans ce cas on peut négliger le cas pair-impair (un sommet apparaitra simplement comme sa propre image).
En outre il est INUTILE d'introduire les bissectrices. Si un axe de symétrie est bissectrice pour un sommet il est médiatrice pour une (autre) paire de sommets.

[Zavonen]

Ca devrait le faire mais je n'ai pas vérifié

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <stdio.h>
#include <stdlib.h>
#include <math.h> // juste pour abs
 
// la tolerance
const double epsilon=0.001; // par exemple
 
// Pour représenter les points
typedef struct
{
    double x;
    double y;
}
Point;
 
// initialisation d'un point avec ses coordonnées
void InitPoint (double x0, double y0, Point * pP)
{
    pP->x=x0;
    pP->y=y0;
}
// Représentation des droites
typedef struct
{
    double a;
    double b;
    double c;
} Droite;
 
// initialisation des droites par les coefficients
void InitDroite(double u, double v, double w, Droite * pD)
{
    pD->a=u;
    pD->b=v;
    pD->c=w;
}
 
// représentation des polygones
typedef struct
{
    int n ; // nombre de sommets
    Point * Sommets; // tableau des sommets
} Polygone;
 
// initialisation d'un polygone
// à partir d'un tableau de points
void InitPolygone ( int m, Point S[], Polygone * pP)
{
    int i;
    pP->n=m;
    pP->Sommets=malloc(m*sizeof(Point));
    for (i=0;i<m;i++)
        InitPoint(S[i].x,S[i].y,pP->Sommets+i);
}
 
// teste si un Point A est egal à un point B a epsilon près
int Egal(Point A, Point B)
{
    double deltax=abs(A.x-B.x);
    double deltay=abs(A.y-B.y);
    return (deltax<epsilon)&&(deltay<epsilon);
}
 
// teste si un point M appartient à un polygone P
int EstSommet(Point M, Polygone P)
{
    int i;
    for (i=0;i<P.n;i++)
        if (Egal (M, P.Sommets[i])) return 1;
    return 0;
}
 
 
// Calcule la médiatrice d'un segment
Droite Mediatrice (Point A, Point B)
{
    Droite MD;
    double u= 2*(B.x-A.x);
    double v= 2*(B.y-A.y);
    double w= A.x*A.x+A.y*A.y-B.x*B.x-B.y*B.y;
    InitDroite(u,v,w,&MD);
    return MD;
}
 
// symétrique du point A par rapport à la droite D
Point Symetrique (Point A, Droite D)
{
    double k= (D.a*A.x+D.b*A.y+D.c)/(D.a*D.a+D.b*D.b);
    double X=A.x-D.a*k;
    double Y=A.y-D.b*k;
    Point * S=malloc(sizeof(Point));
    InitPoint(X,Y,S);
    return *S;
}
 
// teste si la droite D est axe de symétrie du polygone P
int Axe (Droite D, Polygone P)
{
    int i;
    Point S;
    // vérifie si tous les symétriques des sommets sont des sommets
    for (i=0;i<P.n;i++)
    {
        S=Symetrique(P.Sommets[i],D);
        if (!EstSommet(S,P))
            return 0;
    }
    return  1;
}
 
// Teste si le polygone P admet un axe de symétrie
int Test(Polygone P)
{
    int i,j;
    Droite D;
    for (i=0;i<P.n;i++)
        for (j=i+1;j<P.n;j++)
        {
            D=Mediatrice(P.Sommets[i],P.Sommets[j]);
            if (Axe(D,P)) return 1; // Gagné
        }
    return 0; // perdu
}
 
int main()
{
 
    return 0;
}

[alexis0788]

Bonjour merci beaucoup pour ce code mais en vérifiant les calculs des fonctions à la main je me suis apperçu que la fonction
Point Symetrique (Point A, Droite D)
ne calcule pas le symétrique de A par rapport a D, mais un point tel que la droite passant par A et ce point soit perpendiculaire a D.
Voila merci de m'aider