Discussion :

[alexis0788]

Bonjour je n'arrive pas à trouver une methode pour savoir si à partir d'un polygone non croisé et convexe, le polygone est circonscriptible c'est à dire que tous ses cotés sont tangents à un même cercle: lorsque le cercle est inscrit dans le polygone.
Je dois implémenter cette algo en C à partir d'une structure qui prends en arguments la liste des sommets du polygone.
Merci de me donner des idées...

[souviron34]

euh...

Faut pas charrier quand même...

On va pas faire tous tes exercices à ta place....

[Zavonen]

Voici une méthode:
1) Prendre 3 côtés du polygone, définissant trois droites.
A partir de là, définir l'ensemble des points équidistants de ces trois droites.
Rappel: Les points équidistants de deux droites forment une paire de droites perpendiculaires si les deux droites sont sécantes, ou bien une seule droite si les deux droites sont parallèles.
Résultat des courses on trouve:
4 points si aucune paire de droites parmi les 3 n'est constituée de droites parallèles.
2 points sinon.
Partant de là chacun des 4 points (ou des 2 points) est candidat pour être le centre d'un cercle inscrit pour le polygone, il suffit donc de mesurer ses distances aux côtés du polygone AUTRES que les 3 premiers et de comparer les nombres trouvés avec la distance commune aux trois côtés initiaux.
Suggestion: faire un dessin

[20051438]

Bonjour
Voila je fais le projet avec Alexis0788 et j'ai programmé une fonction qui calcule le point d'intersection de deux droites; Je l'ai testé et elle n'est pas super precise dans le resultat obtenue mais elle pourra peut être faire l'affaire, voici le prototype puis le code source (en C)

Code :

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

1
2
3
4
//determine si les deux côtés s'intersectent et renvoie l'adresse du point d'intersection si c'est le cas sinon renvoie NULL;
//côtéun=points un et deux; côtédeux=points trois et quatre
//La fonction n'est pas tres precise
point *pointintersection(point *un,point *deux,point *trois,point *quatre);

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
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
point *pointintersection(point *un,point *deux,point *trois,point *quatre)
{
    point *pinter;//Le point d'intersection
    assert(pinter=(point *)malloc(sizeof(point)));
    assert(pinter->nom=(char *)malloc(sizeof(char)));
    float pente1, pente2, p1, p2;//y=(pente1 * x)+p1  et  y=(pente2 * x)+p2
    //vecteur1 correspond au premier côté défini par les points un et deux
    //vecteur2 correspond au deuxième côté défini par les points trois et quatre
    float vecteur1abscisse=(deux->abscisse)-(un->abscisse);
    float vecteur1ordonnee=(deux->ordonnee)-(un->ordonnee);
    float vecteur2abscisse=(quatre->abscisse)-(trois->abscisse);
    float vecteur2ordonnee=(quatre->ordonnee)-(trois->ordonnee);
    float determinant=(vecteur1abscisse*vecteur2ordonnee)-(vecteur2abscisse*vecteur1ordonnee);
    if(determinant==0) //les deux côtés sont parallèles
    {
        printf("\nPasse dans la 1 condition\n");
 
        pinter=NULL;//il n'y a pas de point d'intersection
    }
    else if(un->abscisse==deux->abscisse) //le côté un est une droite verticale
    {
        pinter->abscisse=un->abscisse;
        pinter->nom="point intersection";
        if(trois->ordonnee==quatre->ordonnee) //le côté deux est une droite horizontale
        {
            printf("\nPasse dans la 2 condition\n");
 
            pinter->ordonnee=trois->ordonnee;
        }
        else //le côté deux est une droite quelconque, donc d'équation y=mx+p
        {
            printf("\nPasse dans la 3 condition\n");
 
            pente2=((quatre->ordonnee)-(trois->ordonnee))/((quatre->abscisse)-(trois->abscisse));//pente du côté deux
            p2=(trois->ordonnee)-((pente2)*(trois->abscisse));//y=(pente2 * x)+p2
            pinter->ordonnee=((pente2)*(pinter->abscisse))+p2;
        }
    }
    else if(un->ordonnee==deux->ordonnee) //le côté un est une droite horizontale
    {
        pinter->ordonnee=un->ordonnee;
        pinter->nom="point intersection";
        if(trois->abscisse==quatre->abscisse) //le côté deux est une droite verticale
        {
            printf("\nPasse dans la 4 condition\n");
 
            pinter->abscisse=trois->abscisse;
        }
        else //le côté deux est une droite quelconque, donc d'équation y=mx+p
        {
            printf("\nPasse dans la 5 condition\n");
 
            pente2=((quatre->ordonnee)-(trois->ordonnee))/((quatre->abscisse)-(trois->abscisse));//pente du côté deux
            p2=(trois->ordonnee)-((pente2)*(trois->abscisse));//y=(pente2 * x)+p2
            pinter->abscisse=((pinter->ordonnee)-(p2))/pente2;
        }
    }
    else if((un->abscisse != deux->abscisse) && (un->ordonnee != deux->ordonnee)) //le côté un est une droite quelconque, donc d'équation y=mx+p
    {
        pinter->nom="point intersection";
        if(trois->abscisse==quatre->abscisse) //le côté deux est une droite verticale
        {
            printf("\nPasse dans la 6 condition\n");
 
            pinter->abscisse=trois->abscisse;
            pente1=((deux->ordonnee)-(un->ordonnee))/((deux->abscisse)-(un->abscisse));//pente du côté un
            p1=(un->ordonnee)-((pente1)*(un->abscisse));//y=(pente1 * x)+p1
            pinter->ordonnee=((pente1)*(pinter->abscisse))+p1;
        }
        else if(trois->ordonnee==quatre->ordonnee) //le côté deux est une droite horizontale
        {
            printf("\nPasse dans la 7 condition\n");
 
            pinter->ordonnee=trois->ordonnee;
            pente1=((deux->ordonnee)-(un->ordonnee))/((deux->abscisse)-(un->abscisse));//pente du côté un
            p1=(un->ordonnee)-((pente1)*(un->abscisse));//y=(pente1 * x)+p1
            pinter->abscisse=((pinter->ordonnee)-(p1))/pente1;
 
            printf("\npente1 vaut: %f\n",pente1);
            printf("\np1 vaut: %f\n",p1);
        }
        else //les deux côtés sont des droites quelconques, donc d'équation y=mx+p
        {
            printf("\nPasse dans la 8 condition\n");
 
            pente1=((deux->ordonnee)-(un->ordonnee))/((deux->abscisse)-(un->abscisse));//pente du côté un
            p1=(un->ordonnee)-((pente1)*(un->abscisse));//y=(pente1 * x)+p1
            pente2=((quatre->ordonnee)-(trois->ordonnee))/((quatre->abscisse)-(trois->abscisse));//pente du côté deux
            p2=(trois->ordonnee)-((pente2)*(trois->abscisse));//y=(pente2 * x)+p2
            pinter->abscisse=(p2-p1)/(pente1-pente2);
            pinter->ordonnee=((pente1)*(pinter->abscisse))+p1;
            pinter->nom="point intersection";
        }
    }
 
    return pinter;
}

...maintenant comment determiner le centre et le rayon du cercle inscrit dans le polygone en rappelant que le polygone est non croisé et convexe .
Auriez-vous une idée sur l'algorithme à mettre en oeuvre (je ne vous demande en aucun cas le code tout fait mais des explications si vous en avez bien entendu )
Merci d'avance !!

[20051438]

Re-bonjour!
J'ai trouvé une manière d'avoir l'équation de la bissectrice d'un angle à l'aide du produit scalaire sur ce forum:
http://forums.futura-sciences.com/thread39936.html
...mais je ne sais pas comment récuperer les coordonnées du vecteur AM dans le produit scalaire!
Si vous pouviez m'expliquer...
Merci.

[pseudocode]

Merci de me donner des idées...

centre = intersection concourante des bissectrices (si elle existe)
rayon = distance du centre à l'un des cotés (cf. distance d'un point a une droite)

[Zavonen]

centre = intersection concourante des bissectrices (si elle existe)

Pourquoi un singulier ?
Prend le cas du triangle. Il y a pour chaque angle 2 bissectrices (intérieure et extérieure).
Les trois bissectrices intérieures sont concourantes certes, mais chaque bissectrice intérieure est également concourante avec les deux autres bissectrices extérieures donnant trois centres de cercles dits 'ex-inscrits'. Il y a donc 4 cercles tangents aux 3 côtés d'un triangle.

[pseudocode]

Il y a donc 4 cercles tangents aux 3 côtés d'un triangle.

Certe, certe... c'est tout à fait exact.

Je me demande juste si le PO voulait aussi les cercles exinscrits.

[20051438]

Bonjour!
Seul le centre et le rayon du cercle inscrit sont cherchés pour notre projet...

[pseudocode]

Bonjour!
Seul le centre et le rayon du cercle inscrit sont cherchés pour notre projet...

Dans ce cas, la méthode du post #6 devrait suffire.

[alexis0788]

Bonjour juste pour vous dire que j'ai résolu mon problème.
J'ai réalisé l'algo pour un cercle inscrit et circonscrit.
Il faut prendre deux bissectrices(cercle inscrit) ou médiatrices(cercle circonscrit) du polygone voir leur point d'intersection, le stocker puis faire une boucle sur le polygone pour tester si ce point appartient aux autres bissectrices(/médiatrices).

[Zavonen]

Bonjour juste pour vous dire que j'ai résolu mon problème.
J'ai réalisé l'algo pour un cercle inscrit et circonscrit.
Il faut prendre deux bissectrices(cercle inscrit)

Peux tu m'expliquer comment tu distingues les bissectrices intérieures des bissectrices extérieures (en toute généralité)?
PS: Je connais une réponse c'est juste pour voir comment tu t'y prends.

[20051438]

Bonjour!
Les bissectrices sont vues dans notre algorithme comme des droites, donc deux bissectrices différentes auront un seul point d'intersection, ensuite on compare ce point d'intersection avec celui des autres bissectrices pour voir si il est identique;
En fait on ne se preoccupe pas des bissectrices exterieures...