Discussion :

[Nico28]

Bonjour.

Je dispose d'un cercle 'C' repérer par son centre [Xc,Yc].
J'ai le rayon R de ce cercle.
Sur le périmètre de ce cercle, 3 points p1, p2, p3, chacun repéré par ses coordonnées [Xp1,Yp1], [Xp2,Yp2] et [Xp3,Yp3].

Comment classer ces 3 points dans le sens horaire ?
On sait également que le résultat du classement ne peut être que :
p1, p2, p3 ou p3, p2, p1


Merci

[PierroElMito]

pour ordonner deux points, par exemple P1 et P3, tu dois tester le signe du produit vectoriel entre les vecteurs CP1 et CP3 ou C est le centre du cercle.

[oiffrig]

Ou bien sans produit vectoriel, tu calcules l'angle qu'aurait le point dans un repère polaire centré sur le cercle en question (à l'aide d'Arccos et en ajustant le signe par exemple), après il ne te reste qu'à classer ces angles du plus grand au plus petit

Petit algorithme:

Code :

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

1
2
3
4
5
6
7
8
9
10
Angles := []
Pour chaque point (xp, yp):
    angle := Arccos((xp - xc)/R)
    Si yp < yc alors:
        angle := -angle
    Fin Si
    Ajouter angle à Angles
Fin Pour
 
Classer les angles dans l'ordre décroissant

[Zavonen]

Calculez les coordonnées des vecteurs
RP1 RP2 RP3
Normez ces vecteurs en U1 U2 U3
I désigne le vecteur unitaire de l'axe des abscisses
Les coordonnées de U1 sont le cosinus et le sinus de l'angle I,RP1, on peut donc trouver cet angle dans l'intervalle [0,2pi]
Idem pour U2 et U3.
Il n'y a plus ensuite qu'à comparer les 3 angles.
Mais on peut raisonner plus rapidement avec la localisation dans les 'quadrants' du repère.
Il suffit de savoir classer deux vecteurs unitaires dans le même quadrant, ce qui peut se faire avec une seule coordonnée.
Comme le truc est cyclique on peut commencer par n'importe lequel des 3 vecteurs en décidant que c'est le premier.

[souviron34]

Autre solution :

trouver le point le plus "à droite".
calculer l'angle formé par les 2 autres points et celui-là.
Le signe donnera lequel est dans le sens horaire par rapport au point trouvé.
D'où le troisème.

[pseudocode]

Idem souviron34, sauf que je ne vois pas bien l'interet de checher le point le plus a droite.

si le produit vectoriel (P2P1)^(P2P3) a un Z positif, alors (P1,P2,P3) sont dans le sens horaire.

C'est a dire si : (P1.x-P2.x)*(P3.y-P2y) > (P1.y-P2y)*(P3.x-P2x)

[souviron34]

Idem souviron34, sauf que je ne vois pas bien l'interet de checher le point le plus a droite.

L'intérêt est que c'est généralisable à N points (en fait une dérivation de l'algo. du "gift-wrapping" pour trouver l'enveloppe convexe (convex hull) d'un ensemble de points).

[rodymary]

si le produit vectoriel (P2P1)^(P2P3) a un Z positif, alors (P1,P2,P3) sont dans le sens horaire.

C'est a dire si : (P1.x-P2.x)*(P3.y-P2y) > (P1.y-P2y)*(P3.x-P2x)

salut,
j'ai esseyé ta formule :
(P1.x-P2.x)*(P3.y-P2y) > (P1.y-P2y)*(P3.x-P2x)
mais ça ne fonctionne pas chez moi, celà me donne toujours un sens horaire
p1,p2,p3 sont 3 points inscrits dans un cercle, et traçés dans l'ordre p1 p2 p3
??

[Nico28]

Voilà où j'ai terminé au bout de la discussion :


3 points P1, P2, P3 et 1 centre.
Dans mon cas, L'ordre des points est [P1, P2, P3] ou [P3, P2, P1].
En partant de la 1ère réponse de la discussion et en ajoutant quelques IF, voilà ce que cela donne.
C'est peut pas optimun, mais pour moi c'est béton !!



double Angle1 = Math.Acos((P1.X - Centre.X) / Rayon);
if (P1.Y < Centre.Y) Angle1 = Angle1 * -1;
//--
double Angle2 = Math.Acos((P2.X - Centre.X) / Rayon);
if (P2.Y < Centre.Y) Angle2 = Angle2 * -1;
//--
double Angle3 = Math.Acos((P3.X - Centre.X) / Rayon);
if (P3.Y < Centre.Y) Angle3 = Angle3 * -1;


//--- Inversion P1 & P3 en fonction ds valeurs
if ((Angle1 < Angle2) && (Angle3 < Angle2) && (Angle1 < Angle3) )
{
// Dans l'ordre, on a P3 , P2 et P1
}
else if ((Angle1 > Angle2) && (Angle3 < Angle2))
{
// Dans l'ordre, on a P3 , P2 et P1
}
else if ((Angle1 > Angle2) && (Angle3 > Angle2) && (Angle1 < Angle3))
{
// Dans l'ordre, on a P3 , P2 et P1
}
else
{
// Dans l'ordre, on a P1 , P2 et P3
}

[rodymary]

merci Nico28 de ta réponse

je viens de trouver plus simple, en calculant la surface du triangle formé par les 3 points :

surface=0.5*(x1*y2-x2*y1)+0.5*(x2*y3-x3*y2)+0.5*(x3*y1-x1*y3)
si surface > 0 : sens horaire ( P1 P2 P3 )

a+