Discussion :

[jlf]

bonjour

soient A,B,C,D 4 points quelconques d'un plan

je voudrais trouver un ordre pour lequel ces 4 points forment les sommets consécutifs d'un quadrilatère

j'ai pensé à ça :
je fixe 3 points arbitrairement, par ex A, B et D comme 1, 2 et 4ème point

si C est bien le 3ème alors il n'y a pas d'intersection AB-CD ni AD-BC

s'il y a une intersection AB-CD je permute B et C et s'il y a une intersection AD-CD je permute C et D

ça doit marcher mais ça ne me semble pas très efficace comme algo, il y a peut-être mieux ?

merci de votre aide

[pseudocode]

Je vais peut-etre dire une betise, mais ne suffit-il pas que les angles orientés (AB,AC) et (AC,AD) soient de meme signe ?

[souviron34]

algorithme du "gift-wrapping" :

1) calculer le point de X maximum, Y minimum
2) trier les points par angle croissant à partir de ce point
3) c'est fini....

est ton ami

[pseudocode]

C'est pas un algo de caclul d'enveloppe convexe le "gift-wrapping" ? Parceque dans ce cas, ca marche pas si le point D est a l'interieur du triangle ABC.

Et puis ca me semble un peu "enorme" comme methode, juste pour savoir si on doit inverser C et D parceque le polygone est croisé. Alors qu'un bete calcul de determinant... et encore, seul le signe nous interesse.

[Zavonen]

Vous voulez sans doute dire quadrilatère convexe, car 4 points sont toujours les sommets consécutifs d'un quadrilatère (éventuellement croisé).
Je propose cela :
Ecrire les equations des 6 droites: (AB) (AC) (AD) (BC) (BD) (CD)
Testez, dans l'ordre, pour quelle droite les deux points restant sont du même côté. Il suffit de remplacer les coordonnées des points dans l'équation et de considérer le signe.
Mettons que vous trouvez (AC) ce qui veut dire que B et D sont du même côté de (AC).
Regardez alors si A et D sont du même côté de (BC) alors c'est ACBD, sinon c'est ACDB

[jlf]

>Vous voulez sans doute dire quadrilatère convexe, car 4 points
> sont toujours les sommets consécutifs d'un quadrilatère
> (éventuellement croisé

convexe ou non, je veux seulement que le dessin à main levée en suivant l'ordre des 4 sommets ne donne pas un quadri croisé

[Zavonen]

>Vous voulez sans doute dire quadrilatère convexe, car 4 points
> sont toujours les sommets consécutifs d'un quadrilatère
> (éventuellement croisé

convexe ou non, je veux seulement que le dessin à main levée en suivant l'ordre des 4 sommets ne donne pas un quadri croisé

Autant pour moi ! un quadrilatère peut être ni convexe ni croisé.
Mais la méthode que je donne fonctionne. On peut même la simplifier.
On n'a pas besoin des 6 droites.
On teste les points B et C par rapport à (AB)
S'ils sont du même côté on teste A et D par rapport à (BC)
si du même côté
ABCD est OK
Sinon ABDC
En cas d'échec cest encore plus simple !
On peut prendre ACBD ou ADBC les deux sont bons, cela revient à inverser le sens de rotation

[pseudocode]

idem Zavonen. Mais je prefere comparer les signes des determinants.

si je ne me trompe pas ca doit faire:

Code :

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

1
2
3
4
5
6
7
8
s1 = sgn( det(AB,AC) )
s2 = sgn( det(AC,AD) )
si s1=s2 alors quadrilatere=ABCD
sinon {
  s3 = sgn( det(AB,AD) )
  si  s2=s3 alors quadrilatere=ACBD
  sinon quadrilatere=ABDC
}

a verifier quand meme...

[souviron34]

C'est pas un algo de caclul d'enveloppe convexe le "gift-wrapping" ? Parceque dans ce cas, ca marche pas si le point D est a l'interieur du triangle ABC.

Et puis ca me semble un peu "enorme" comme methode, juste pour savoir si on doit inverser C et D parceque le polygone est croisé. Alors qu'un bete calcul de determinant... et encore, seul le signe nous interesse.

autant pour moi j'avais compris convexe dans post d'origine...

Désolé c'était la digestion

[Zavonen]

Code :

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

1
2
3
4
5
6
7
8
s1 = sgn( det(AB,AC) )
s2 = sgn( det(AC,AD) )
si s1=s2 alors quadrilatere=ABCD
sinon {
  s3 = sgn( det(AB,AD) )
  si  s2=s3 alors quadrilatere=ACBD
  sinon quadrilatere=ABDC
}

a verifier quand meme...

Entièrement d'accord avec pseudocode. Nos méthodes sont foncièrement les mêmes mais c'est plus simple d'utiliser le signe du déterminant que les équations de droite. Le signe du dét donne le sinus de l'angle orienté des deux vecteurs, nous dit donc si cet angle est entre 0 et pi ou bien entre -pi et 0, cela donne bien la position relative des points par rapport à AC

[Nemerle]

autrement, pour varier: prendre 2 points, et chercher la position des 2 autres par rapport à cette droite (via les surdroites en x et y)