Comparaison de nombres, de points

[(gile)]

Salut,

 

Je vais essayer de répondre aux questions récurentes à propos de la comapraison de nombres réels ou de points (encore dernièrement sur le forum LISP d'Autodesk), par exemple :

 

pourquoi

(polar '(0.0 0.0 0.0) pi 1.0)

retourne : (-1.0 1.22465e-016 0.0)

et pas : (-1.0 0.0 0.0)

 

pourquoi

(equal (polar '(0.0 0.0 0.0) (/ pi 4.0) 1.0) (list (sqrt 0.5) (sqrt 0.5) 0.0))

retoune nil

 

Ceci est dû à la manière d'encoder les nombres réels en base 2. AutoCAD, comme la plupart des calculateurs utilise les nombres à virgule flottante en double précision (pour plus de détails voir ici) dont on a coutume de dire qu'ils ont 15 (ou 16) chiffres significatifs.

Ceci revient à dire que, quand on teste l'égalité de deux nombres réels, on doit utiliser une tolérance qui prend en compte ce nombre de chiffres significatifs (au delà, les résultats ne sont plus fiables comme dans les exemples ci-dessus).

 

Attention, il ne faut confondre le nombre de chiffres significatifs et le nombre de décimales.

Le nombre de chiffres signicatifs d'un nombres est le nombre de chiffres du nombre sans compter les 0 placés à gauche quelle que soit la position de la virgule (c'est pour ça qu'on parle de virgule flottante).

Par exemple, tous les nombres suivants ont 15 chiffres significatifs mais des nombres de décimales différents :

123456789012345 (0 décimales)

1234567890.12345 (5 décimales)

12345.6789012345 (10 décimales)

0.123456789012345 (15 décimales)

0.00000123456789012345 (20 décimales)

 

En LISP, pour comparer les nombres réels et les points (listes de nombres réels) on utilise la fonction equal qui permet de fixer une tolérance dans la compariaison (la valeur de la différence maximale tolérée).

 

Pour reprendre les exemples ci-dessus :

(equal (polar '(0.0 0.0 0.0) pi 1.0) '(-1.0 0.0 0.0) 1e-15)

retorune T

 

(equal (polar '(0.0 0.0 0.0) (/ pi 4.0) 1.0) (list (sqrt 0.5) (sqrt 0.5) 0.0) 1e-15)

retourne T

 

mais au fur et à mesure qu'on s'éloigne de l'origine (par exemple à 1000 unités), il faut être plus tolérant

 

(equal (polar '(0.0 0.0 0.0) pi 1000.0) '(-1000.0 0.0 0.0) 1e-15)

retourne nil

 

(equal (polar '(0.0 0.0 0.0) (/ pi 4.0) 1000.0) (list (* 1000.0 (sqrt 0.5)) (* 1000.0 (sqrt 0.5)) 0.0) 1e-15)

retorune nil

 

Il faut, dans ce cas, utiliser 1e-12 (0.000000000001) pour avoir un résutat positif. Mais dans certains domaines, on travaille beaucoup plus loin de l'origine, il faut donc encore augmenter la tolérance.

 

L'idée est donc de déterminer automatiquement quelle tolérance utiliser en fonction de la nature des nombres à comparer.

Ceci nécessite un peu de mathématiques.

 

;; gc:Log10
;; Retourne le logarithme décimal du nombre
;;
;; Argument
;; x : un nombre strictement positif
(defun gc:Log10 (x)
 (/ (log x) (log 10))
)

;; gc:Fuzz
;; Retourne la tolérance utilisable pour comparaison en fonction
;; du nombre de chiffres significatifs de x
;;
;; Argument
;; x : le nombre
(defun gc:Fuzz (x)
 (if (zerop x)
   1e-15
   (expt 10.0 (fix (- (gc:Log10 (abs x)) 15)))
 )
)

 

avec les nombres à 15 chiffres significatifs donnés plus haut, on voit que fuzz retourne bien la décimale correspondant au 15ème chiffre significatif :

 

(gc:Fuzz 123456789012345) => 1.0

(gc:Fuzz 1234567890.12345) => 1.0e-005

(gc:Fuzz 12345.6789012345) => 1.0e-010

(gc:Fuzz 0.123456789012345) => 1.0e-015

(gc:Fuzz 0.00000123456789012345) => 1.0e-020

 

On peut donc définir des fonctions de comparison pour les nombres et les points qui utilisent automatiquement la tolérance optimale en fonction des nombres comparés :

 

 

;; gc:EqualNumbers
;; Evalue si deux nombres sont égaux en utilisant une tolérance calculée
;; en fonction du nombre de chiffres significatifs de x et y
;;
;; Argument
;; x et y : les nombres à comparer
(defun gc:EqualNumbers (x y)
 (or (= x y) (equal x y (max (gc:Fuzz x) (gc:Fuzz y))))
)

;; gc:EqualPoints
;; Evalue si deux points sont égaux en utilisant une tolérance calculée
;; en fonction du nombre de chiffres significatifs des coordonnées
;;
;; Argument
;; p1 et p2 : les points à comparer
(defun gc:EqualPoints (p1 p2)
 (equal p1 p2 (gc:fuzz (apply 'max (mapcar 'abs (append p1 p2)))))
)

 

(gc:EqualPoints (polar '(0.0 0.0 0.0) pi 1000.0) '(-1000.0 0.0 0.0))

retourne T

 

(gc:EqualPoints (polar '(0.0 0.0 0.0) (/ pi 4.0) 1000.0) (list (* 1000.0 (sqrt 0.5)) (* 1000.0 (sqrt 0.5)) 0.0))

retorune T

 

Ces fonctions sont intégrées à la bibliothèque gc_MathGeom.lsp en téléchargement au bas de cette page.

[Goldorak44]

Super.

 

Un grand merci à toi pour toutes ces explications. ;)

[bonuscad]

Salut,

Mais dans certains domaines, on travaille beaucoup plus loin de l'origine, il faut donc encore augmenter la tolérance.

 

Sur qu'en topographie cartographie, le problème est récurent, ce genre de fonction m'avait traversé l'esprit, tu l'a concrétisé.

Merci

[VDH-Bruno]

Bonjour et merci (gile),

 

Le sujet est excellent et bienvenu, j’avoue ne pas toujours être très à l’aise avec ces notions, j’ai donc pris les 5 mn nécessaire à la bonne compréhension des fonctions proposés.

 

Certains points anecdotique me chagrine (mais rien de bien méchant, je pense qu’il faut les laisser mûrir), par contre dans la rédaction du sujet il y a comme un semblant de contradiction.

 

mais au fur et à mesure qu'on s'éloigne de l'origine (par exemple à 1000 unités), il faut être plus tolérant

 

(equal (polar '(0.0 0.0 0.0) pi 1000.0) '(-1000.0 0.0 0.0) 1e-15)

retourne nil

 

Cette affirmation laisse penser que les fonctions de comparaison proposée amèneront automatiquement cette tolérance de comparaison (une comparaison à 1e-12 par exemple pour ce cas précis).

 

 

Mais tel qu'elles sont écrite ce n’est pas le cas:

(gc:EqualPoints (polar '(0.0 0.0 0.0) pi 1000.0) '(-1000.0 0.0 0.0))

retourne T

 

Cela n’est pas possible car

_$ (gc:Fuzz (cadr (polar '(0.0 0.0 0.0) pi 1000.0)))
1.0e-027

Et

_$ (gc:Fuzz 0.0)
1.0e-015

De plus la fonction de comparaison gardant le plus grand Fuzz la fonction equal ne peut que retourner nil

 

Donc pour moi

_$ (gc:EqualPoints (polar '(0.0 0.0 0.0) pi 1000.0) '(-1000.0 0.0 0.0))
nil

 

A+ Bruno

[(gile)]

Salut,

 

Je ne comprends pas bien ce que tu veux dire.

 

(defun gc:EqualPoints (p1 p2)
 (vl-every 'gc:EqualNumbers p1 p2)
)

gc:equalPoints compare chaque coordonnée correspondante des deux points avec la tolérance calculée en fonction de la valeur de la coordonnée.

 

(mapcar 'gc:fuzz '(-1000. 0. 0.)) retourne (1.0e-012 1.0e-015 1.0e-015)

(mapcar 'gc:fuzz (polar '(0. 0. 0.) pi 1000.) retourne (1.0e-012 1.0e-027 1.0e-015)

 

Donc les coordonnées X sont comparées avec une tolérance de 1e-12 et les coordonnées X et Z avec 1e-15.

 

Il me semble normal qu'une fonction de comparaison de points considèrent comme égaux

(polar '(0. 0. 0.) pi dist)

et

(list (- dist) 0. 0.)

quelle que soit la valeur de dist.

 

Je ne sais pas comment est implémentée la fonction LISP equal*, mais j'imagine que, comme il n'y a pas de type Point2d ou Point3d en LISP et que equal fonctionne indifféremment avec des nombres et des listes de nombres quelle que soient leurs longueur, equal compare chacun de termes correspondant des deux listes avec la tolérance qui lui est passé en argument.

gc:equalPoints est 'plus précise' puisque la tolérance est calculée 'au mieux' pour chacune des termes.

 

* dans l'API .NET d'AutoCAD, les types Point2d et Point3d ont des fonctions de comparaison qui peuvent utiliser une tolérance. Ces fonctions comparent la distance entre les deux points avec la tolérance, ce qui est peut-être plus rigoureux en ce qui concerne des points.

[VDH-Bruno]

Bonjour (gile)

Je ne suis pas un grand spécialiste de la question, et je n’ai jamais réfléchi plus que cela au problème. Je suis totalement d’accord avec l’idée suivante:

 

Il me semble normal qu'une fonction de comparaison de points considèrent comme égaux

(polar '(0. 0. 0.) pi dist)

et

(list (- dist) 0. 0.)

quelle que soit la valeur de dist.

 

Là où je me perds c’est que les fonctions proposées ne permettent pas cela, si tu teste dans la console, tu obtiens:

_$ (setq dist 1000)
1000
_$ (gc:EqualPoints (polar '(0. 0. 0.) pi dist) (list (- dist) 0. 0.))
nil

 

Le résultat est nil, tel que sont codé les fonctions cela me semble juste car la fonction gc:EqualNumbers garde le fuzz maxi soit 1.0e-015 pour la coordonné Y,je souligne seulement qu’à cette précision les chiffres significatifs sont toujours différents…

 

Au risque de dire une énormité et de simplifier abusivement, instinctivement je serai tenté de dire que devant un fuzz supérieur à 1.0e-015, il faut garder la différence des deux exposant du fuzz dans notre exemple (27 - 15)=12, pour faire une comparaison à 1.0e-012 pour pouvoir considérer les deux coordonnées en Y égal, et par conséquence les points aussi.

 

En espérant avoir été un peu plus clair, je ne pense pas avoir proposé la solution mais seulement une piste de réflexion, ou alors j’ai rien compris ce qui est également possible…

 

A+ Bruno

[VDH-Bruno]

Re,

 

A y repenser, je pense que la fonction de comparaison pour être juste doit s’inspirer de ta réflexion suivante :

* dans l'API .NET d'AutoCAD, les types Point2d et Point3d ont des fonctions de comparaison qui peuvent utiliser une tolérance. Ces fonctions comparent la distance entre les deux points avec la tolérance, ce qui est peut-être plus rigoureux en ce qui concerne des points.

 

C’est-à-dire dans le cas de 2 fuzz différent, il faudrait garder le plus grand des 2 fuzz puis arrondir le nombre qui à le plus petit fuzz au fuzz retenu.

 

A+

[(gile)]

Salut,

 

Tu as raison, j'ai modifié la fonction gc:EqualPoints pour qu'elle compare les points avec une tolérance calculée avec la plus grande coordonnée en valeur absolue.

 

(defun gc:EqualPoints (p1 p2)
 (equal p1 p2 (gc:fuzz (apply 'max (mapcar 'abs (append p1 p2)))))
)

[GEGEMATIC]

Salut Gile,

tu as mis le doigt sur un problème qui va devenir de plus en plus récurent avec les nouvelles coordonnées en RGF93, qui font qu'on s'éloigne de plus en plus du zéro

 

mais ce sujet m'a rappelé de vieilles discussions, arbitrées par Kamal Boutora, sur Planetar

 

pour ceux qui veulent du vintage, voilà un pdf du fil, avec les doctes explication de Kamal:

 

Precision_discussion_vintage_2005_2007.pdf

[DenisHen]

Bonjour à tous.

 

Voilà, je tente de dessiner un rectangle avec deux point et une hauteur, j'utilise DistanceTo de (gile) mais AutoCAD me sort une erreur, voici mon bout de code :

  (initget 1)
 (setq pt1 (getpoint "\nPoint bas gauche : "))
 (setq pt2 (getpoint "\nPoint bas droit : "))
 (setq pt12 (getpoint "\nHauteur : "))
 (Setvar "OSMODE" 0)
 (setq PtPerp (DistanceTo pt12 pt1 pt2))
 (setq pt3 (polar pt2 (angle Pt12 PtPerp) (distance pt12 PtPerp)))
 (setq pt4 (polar pt1 (angle pt12 PtPerp) (distance pt12 PtPerp)))
 (Command "_PLINE" pt1 pt2 pt3 pt4 "_C")

Et voici le message d'AutoCAD :

Point bas gauche :

Point bas droit :

Hauteur : type d'argument incorrect: point 2D/3D: 108.617

Commande:

Et "108.617" ne correspond à rien, je suis en Lambert93...

 

Si quelqu'un a une idée, une solution... Je suis preneur...

[(gile)]

Salut,

 

Essaye de nommer tes variable avec des noms plus explicites, ça t'éviteras des confusions...

(setq PtPerp (DistanceTo pt12 pt1 pt2))

contrairement à ce que son nom tendrait à faire croire, PtPerp est une distance (un nombre réel), pas un point...

[DenisHen]

Salut (gile), et merci pour cette réponse.

 

Je n'avais pas compris ça... Je cherchais à créer un point sur la droite Pt1/Pt2 perpendiculaire au point PtPerp...

[DenisHen]

Si ça peut être utile à d'autres, voici le bout de code qui permet de dessiner un rectangle à la souris en trois points, pt1 et pt2 pour la base du rectangle et pt3 pour sa hauteur :

  (initget 1)
 (setq pt1 (getpoint "\nPoint bas gauche : "))
 (setq pt2 (getpoint "\nPoint bas droit : "))
 (setq pt12 (getpoint "\nHauteur : "))
 (Setvar "OSMODE" 0)
 (setq DistPerp (DistanceTo pt12 pt1 pt2))
 (setq pt3 (polar pt2 (+ (angle Pt1 Pt2) (/ pi 2)) DistPerp))
 (setq pt4 (polar pt1 (+ (angle pt1 Pt2) (/ pi 2)) DistPerp))
 (Command "_PLINE" pt1 pt2 pt3 pt4 "_C")

Attention, selon le sens des angles (trigo ou horaire) il faut soustraire "(- (angle..." ou ajouter "(+ (angle..." la moitié de pi.