A droite ou à gauche ?

[Didier-AD]

Rassurez vous, il ne s'agit pas de politique mais d'un petit challenge

 

Il s'agit d'écrire une fonction qui permettra de savoir si un point P est à droite ou à gauche d'une direction donnée par deux points A et B

 

(droiteougauche P A B) doit retourner

1 si P est à droite de AB,

-1 si P est à gauche de AB

0 si P est aligné avec A et B

 

 

[(gile)]

Si je comprends bien et qu'on pourrait dire, en d'autres termes sens trigo ou sens horaire, j'ai ça dans mes tiroirs (et je sais que Bonuscad aussi, en plus élégant).

Si c'est bien ça je laisse jouer les autres.

 

Bonne nuit

[Didier-AD]

on peut l'exprimer comme çà

je précise qu'on travaille dans le plan XY car sinon çà n'a pas de sens

 

je décroche pendant 2 jours, je verrai en rentrant.

 

 

[Edité le 20/5/2007 par Didier-AD]

[bonuscad]

Ce que j'utilise pour ce genre problème

 

((lambda ( / e_sel ename pt ob param deriv alpha v1 v2 det_or)
(setq
	e_sel (entsel)
	ename (car e_sel)
	pt (trans (cadr e_sel) 1 0)
	ob (vlax-ename->vla-object ename)
	pt (vlax-curve-getClosestPointTo ob pt)
	param (vlax-curve-getparamatpoint ob pt)
	deriv (vlax-curve-getfirstderiv ob param)
	alpha (atan (cadr deriv) (car deriv))
	v1 (mapcar '- (polar pt alpha 1.0) pt)
	v2 (mapcar '- (trans (getpoint "\nDonnez un point: ") 1 0) pt)
	det_or (apply '(lambda (x1 y1 z1 x2 y2 z2) (- (* x1 y2) (* y1 x2))) (append v1 v2))
)
(cond
	((> det_or 0.0) (princ "\nVous avez cliquez à GAUCHE"))
	((< det_or 0.0) (princ "\nVous avez cliquez à DROITE"))
)
(prin1)
))

[tiboulen]

j'avais il y a tres longtemps le meme probleme savoir si un point était a droite ou a gauche d'une ligne, le seul moyen que j'avais trouve etait de passer par l'equation de la droite y=ax+b et de tester les differents cas, le prog etait tres maladroitement celuici:

la variable sens etait egale a - 1 ou a 1 selon si le pt etait a droite ou a gauche

desole je n'ai pas la temps de la remettre au propre

(defun c:sensdrt ()

(setq alpha 90)

(prompt "\n\norientation du symbole dans le sens aval amont")

(setq pt1 (getpoint "\npremier point")

pt2 (getpoint "\ndeuxieme point")

a0 (angle pt1 pt2)

)

(setq pt0 (getpoint "\nPoint a relier...:")

a (/ (sin a0) (cos a0));;a tangente a0

b (- (cadr pt1) (* a (car pt1)));;b=y-ax

)

(cond

((= (car pt2) (car pt1));;x constant

(progn

(if (> a0 (angle pt1 pt0))

(progn (setq a1 (- a0 (* alpha (/ pi 180)))

sens -1)

)

(progn (setq a1 (+ a0 (* alpha (/ pi 180)))

sens 1))

);;fin du if

);;fin du progn

)

((> (car pt2) (car pt1))

(progn

(if (> (cadr pt0) (+ (* a (car pt0)) b))

(progn (setq a1 (+ a0 (* alpha (/ pi 180)))

sens 1))

(progn (setq a1 (- a0 (* alpha (/ pi 180)))

sens -1))

);;fin du if

);;fin du progn

)

((< (car pt2) (car pt1))

(progn

(if (< (cadr pt0) (+ (* a (car pt0)) b))

(progn (setq a1 (+ a0 (* alpha (/ pi 180)))

sens 1))

(progn (setq a1 (- a0 (* alpha (/ pi 180)))

sens -1))

);;fin du if

);;fin du progn

)

);;fin du cond

(command "_line" pt1 pt2 "")

(command "_line" pt1 pt0 "")

(if (= sens 1) (prompt "a gauche"));pas segolene!!!!!!

(if (= sens -1) (prompt "a droite"));; pas sarko!!!!!

)

[tiboulen]

ps je vois que le massage a été écris le 20 mai a 00h20 bravo

pour ces cogitations nocturnes

[(gile)]

Ma façon est plus "prosaïque" que celle de Bonuscad.

 

Il s'agit d'une bête comparaison d'angles : si l'angle que fait AP par rapport à l'angle fait par AB est compris entre 0 et pi radians (180°) le point P est à gauche. Il est à droite si l'angle est compris entre pi et 2 pi radians (180° et 360°), aligné si l'angle est égal à 0 ou pi.

 

Pour pouvoir faire la comparaison il faut que l'angle soit exprimé par une valeur positive comprise entre 0 et 2 pi, il est donc nécessaire de convertir le résultat de la soustraction s'il est négatif.

 

La routine :

(defun droiteougauche (A B P / x)
 (and (minusp (setq x (- (angle a p) (angle a b))))
      (setq x (+ x (* 2 pi)))
 )
 (cond
   ((    ((    (T 0) ; aligné
 )
) 

 

Pour tester la routine

 

(defun c:test (/ dg)
 ((lambda (dg)
    (alert (cond
      ((minusp dg) "Gauche")
      ((zerop dg) "Aligné")
      (T "Droite")
    )
    )
  )
   (DROITEOUGAUCHE
     (getpoint "\nPoint A: ")
     (getpoint "\nPoint B: ")
     (getpoint "\nPoint P: ")
   )
 )
 (princ)
) 

 

[Edité le 21/5/2007 par (gile)]

[zebulon_]

j'ai aussi fait dans le "prosaïque", sauf qu'avec l'angle, j'ai fait un sinus, cela évite le 2*k*pi.

 

(setq x (sin (- (angle a p) (angle a b))))

 

Si on trouve 0, c'est aligné. > 0 c'est à droite. < 0 c'est à gauche (ou le contraire ;) je n'ai pas testé)

 

Amicalement

Zebulon_

 

 

[(gile)]

Bon sang, mais c'est bien sûr !!!

Que n'y avais-je pensé, dire qu'il y a peu je donnais des cours de trigo :red:

 

Ce que je trouve formidable dans ces "challenges", outre les solutions que je ne connaissais pas, c'est de voir toutes celles auxquelles je n'avais pas pensé alors qu'elles étaient juste devant mes yeux.

Bonne leçon d'humilité.

[Bred]

Salut,

tiens, je l'avais pas vu ce challenge...

J'utilise exactement ce que décris zebulon_ au détail près que je n'utilise pas le sinus, mais je test la valeur de l'angle (ce qui n'est pas plus simple ...)

 

(if (and (> (- (angle p1 pt)(angle p1 p2)) 0)
   (< (- (angle p1 pt)(angle p1 p2)) pi))    
   (alert "gauche")
   (alert "droite")
   )

[Didier-AD]

Là encore, le produit vectoriel vient à la rescousse

en effet, le produit vectoriel de deux vecteurs coplanaires mais non parallèles donne un vecteur qui est perpendiculaire au plan de ces deux vecteurs

(pvectoriel '(1 0 0) '(0 1 0)) donne le vecteur '(0 0 1)

Dans le challenge, j'ai précisé que les 3 points étaient dans le plan XY donc le produit vectoriel sera un vecteur orienté selon Z

 

et les lois du produit vectoriel sont telles que

(pvectoriel '(1 0 0) '(0 1 0)) donne le vecteur '(0 0 1)

mais

(pvectoriel '(0 1 0) '(1 0 0)) donne le vecteur '(0 0 -1)

En examinant le signe de cette coordonnée en Z, on peut donc connaitre la position relative de ces deux vecteurs

 

(defun pvectoriel (V1 V2)
; ajouter si nécessaire la coordonnée Z à V1
(if (not (caddr V1)) (setq V1 (append V1 (list 0))))
; ajouter si nécessaire la coordonnée Z à V2
(if (not (caddr V2)) (setq V2 (append V2 (list 0))))
(list
(- (* (cadr V1)(caddr V2)) (* (caddr V1) (cadr V2)))
(- (* (car V1)(caddr V2)) (* (caddr V1) (car V2)))
(- (* (car V1)(cadr V2)) (* (cadr V1) (car V2)))
)
)
(defun estadroite (A B P / v)
 (setq v (pvectoriel (mapcar '- B A) (mapcar '- P A)))
(cond
   ((minusp (caddr v)) -1)
  ((equal (caddr v) 0.0 1e-9) 0)
 (t 1)
)
)

 

En plus, et ce n'est pas à négliger, la valeur absolue de la coordonnée en Z donne la surface du triangle ABP

 

[(gile)]

Mais oui, la "règle de la main droite" ...

 

Moi qui n'utilisais le produit vectoriel que pour trouver la "normale" d'un plan, j'en ai appris ces derniers jours :D

 

En plus, et ce n'est pas à négliger, la valeur absolue de la coordonnée en Z donne la surface du triangle ABP

il semblerais que ce soit plutôt la moitié de la valeur absolue de la coordonnée Z.

 

[Edité le 22/5/2007 par (gile)]

[Didier-AD]

il semblerais que ce soit plutôt la moitié de la valeur absolue de la coordonnée Z

 

Didier si tu continues à dire des trucs sans faire la moindre vérif, tu vas finir par passer pour un rigolo !

 

Pour revenir à ces trucs de géométrie vectorielle, je trouvais çà "ennuyeux" (pour être poli) quand j'étais au lycée et puis un jour j'ai demandé une idée pour un algorythme à un prof de math et je me suis trouvé tout penaud

On devrait toujours croire, quand on est à l'école qu'un jour çà pourait servir....

[(gile)]

Petite précision à propos de la méthode de _Zebulon que j'utilise désormais sans compter. ;)

 

(setq x (sin (- (angle a p) (angle a b))))

 

Si on trouve 0, c'est aligné. > 0 c'est à droite.

 

Je viens de remarquer que la perte de précision (normale) dans les calculs trigonométrique fait que le sinus de pi n'est pas exactement 0.

(sin pi) -> 1.22465e-016

(sin (- pi)) -> -1.22465e-016

Si ceci est négligeable dans la plupart des calculs, cela fausse la comparaison quand le point à évaluer est situé entre les deux autres.

 

Donc, il faudrait plutôt faire :

(cond
   ((    ((    (T (alert "Aligné"))
 ) 

[Bred]

Salut (gile),

Ma réponse n°9 ne réponds pas à ça ?

[(gile)]

Si, en comparant directement les angles on évite cette imprécision, mais la méthode de _Zebulon évite d'avoir à faire un "2*k*pi" :

Pour comparer les angles, ils faut que leurs valeurs soient comprise entre 0 ét 2*pi, donc, si le résultat de la soustraction (- (angle a p) (angle a b)) est négatif, il faut lui ajouter 2*pi (c'est ce que je fais réponse 6.

L'utilisation du sinus qui fonctionne avec les angles négatif permet d'éviter cela.

[(gile)]

J'avais fait une routine pour convertir un angle quelconque en son équivalent compris entre 0 et 2*pi :

 

;;; Ang
(defun ang  (if (and (    ang
   (ang  )
) 

 

et d'autres pour évaluer si 3 points p1 p2 p3 "tournent" dans le sens horaire (ce qui revient à dire que p3 est à droite de la ligne p1 p2)

 

en comparant les angles :

 

(defun Clockwisep (p1 p2 p3)
 () 

ou

(defun Clockwisep (p1 p2 p3 / ang)
 (and (minusp (setq ang (- (angle p2 p3) (angle p1 p2))))
      (setq ang (+ (* 2 pi) ang))
 )
 () 

 

ou encore, avec la méthode du sinus (corrigée) :

 

(defun clockwise-p (p1 p2 p3)
 () 

 

[Edité le 5/8/2007 par (gile)]

[tiboulen]

je reviens sur un vieux sujet mais je suis admiratif sur la méthode de gile qui résout le problème

en 4 lignes alors que j'uitilais 30 lignes en passant par l'equation d'une droite etc... (voit + haut) . mais cette méthode provenait de cours que j'avais pris a l'essiee (école supérieure d'ingénieur en électricte et electronique) à paris comme quoi.........

[(gile)]

Salut,

 

La méthode que je préfère (et que j'utilise désormais) est celle de Zebulon_

 

Je donne la version que j'en ai fait en intégrant l'imprécision notée plus haut.

 

;;; Clockwise-p 
;;; Retourne T si les points p1 p2 et p3 tournent dans le sens horaire

(defun clockwise-p (p1 p2 p3)
 () 

[zebulon_]

Bonjour,

c'est sûr qu'avec mon BEPC+2, 30 lignes c'est trop pour suivre. Les trucs plus compliqués, on laisse ça aux ingénieurs. C'est pour ça qu'ils sont payés plus cher : ils trouvent des solutions compliquées a des problèmes simples.

 

Amicalement

Zebulon_