Dessiner une courbe

[Médiat]

Bonjour,


Le problème est le suivant :


On dispose d'une courbe plane paramétrée d'équation avec , le but est de représenter cette courbe, à l'aide de (de l'ordre de 1000) points, mais de telle sorte que la distance entre deux points successifs soit à peu près identiques.


La solution bourrin consiste à calculer la longueur (Length) de la courbe en calculant points (K de l'ordre de 30 ou plus).


On suppose que la distance entre deux points successifs, dans la division fine est bien inférieure à .


Ensuite, on recalcule les points de la division fine, mais on ne garde que :

1. Si , on prend
2. Si , les points tels que la longueur de la courbe soit juste supérieure ou égale à
3. Si on prend

Si quelqu'un a une idée pour améliorer cela, je suis preneur


Bien sûr, je peux donner tous les détails que vous voulez.
-----

[umfred]

représenter la courbe où? comment ? quel langage ? quel est le souci qui te bloque? tu nous donnes juste un énoncé là, sauf erreur.

[Médiat]

Merci de votre réponse, la représentation proprement dite n'est pas un souci, le langage non plus, juste l'algorithme m'intéresse sous réserve qu'il soit plus efficace que la méthode bourrin.

[polo974]

Donc on a (x,y) = f(v)
Ou x = fx(v) et y = fy(v)

Déjà ces fonctions sont-elles faciles à dériver ?

Ensuite, un peu au pif, je regarderais racine(dfx² + dfy²)

J'ai l'impression que ça donne une info sur la "l'étirement" de la courbe en fonction de v.

Mais c'est pas gagné (il faut à minima intégrer pour avoir la "longueur" totale).

Et si c'est pas clair, on va dire que c'est que je suis un peu dans le flou et le confus...

[A voir en vidéo sur Futura]

[Médiat]

Salut, merci

on a (x, y) = f(v)
Et ces fonctions ne sont pas dérivables facilement (certaines ne sont pas partout dérivables (mais elles sont continues)), c'est pour cela que j'ai posté en informatique et non en mathématiques.

Calculer la longueur totale est relativement facile et efficace, c'est le découpage en points équidistants qui me semble très bourrin avec ma méthode et compliquée de trouver autre chose.

[polo974]

Je dirais qu'il faut dichotomiser sur la longueur. Mais c'est juste une piste en mode ensomeillé...
Je t'abandonne pour ce soir...

[Paraboloide_Hyperbolique]

Bonjour,

J'ai trouvé l'article suivant qui traite du problème:

https://ariel.chronotext.org/dd/defi...93adaptive.pdf

[Médiat]

et merci, c'est exactement ce qu'il me manquait !

[polo974]

Sympa mais dangereux,

Même s'ils ont échappé à sin(x) avec leur bidouille (et encore, pas à tous les coups), un truc genre sin(x) - k.sin(3.x) en choisissant bien k, et hop, ça gamelle à quasi tous les coups...

Il faut ajouter des points intermédiaires et qu'aucun ne révèle une courbure.
Et même avec ça, le résultat n'est pas garanti. Il sera juste un moins incertain.

Le mieux serait de pouvoir découper la courbe en tronçons où la courbure ne s'inverse pas et où le point départ est différent du point d'arrivée.

[Médiat]

Salut polo

Je fais mes tests avec un cercle, une épicycloïde et une hypocycloïde, et cela marche plutôt pas mal (j'utilise le test 4 : , étant le milieu de au sens du paramètre).

Je posterai les résultats statistiques.

Ceci dit il me reste le problème principal, que je ré-expliquerais aussi plus tard.

[Paraboloide_Hyperbolique]

Sympa mais dangereux

Je n'ai pas testé le truc. J'ai juste l'impression que l'idée tient la route (à quel point, cela reste à voir). Les techniques classiques font généralement appel à une mesure de la courbure (analytiquement ou numériquement). Comme il est spécifié par Mediat que le calcul des dérivées n'est pas une option, c'est la meilleure option que j'ai trouvée pour l'instant. Il y a peut être (surement) mieux en recherchant dans des articles publiés sous comités de lectures (encore faut-il y a avoir accès).

[polo974]

Le cercle aurait dû planter, vu que le point de départ = point d'arrivée... sauf s'il à préalablement été découpé en arcs.

En fait, j'ai aussi chercher à transformer des Béziers (fichier SVG) en gcode, et même avec les points de contrôle, c'est pas si simple de bien faire ça...

Sinon, le code est un peu daté (comme nous )...

[Médiat]

Un premier résultat significatif, le test porte su un simple cercle :

Précision	Temps (ms)	Départ	Calls	Résultat	Erreur
1000000	134	1000000	1000000	6,28319159036960	1,00000074905195
1,00E-09	0	1000	3000	6,28318272332360	0,41123345241907
1,00E-10	1	1000	15000	6,28318514568850	0,02570210464694
1,00E-11	2	1000	31000	6,28318526680680	0,00642552845880

La première ligne est la division de l'intervalle en 1 000 000 d'intervalles égaux (du paramètre) les autres lignes partent d'un découpage en 1000 intervalles égaux, mais applique le test d(AM) + d(MB) - d(AB) < précision. La colonne erreur est en millionièmes.

En particulier, la ligne 4 donne une division du temps par 130 et une erreur 40 fois plus faible par rapport à la première.

Même chose avec une hypocycloïde à 5 rebroussements :

Précision	Temps (ms)	Départ	Calls	Résultat	Erreur
1000000	140	1000000	1000000	6,40001005296980	1,57077653120674
1,00E-09	2	1000	9800	6,39999755685660	0,38174115632450
1,00E-10	3	1000	23236	6,39999953967080	0,07192643758369
1,00E-11	8	1000	50976	6,39999990483600	0,01486937503681

[polo974]

Heu, dans les lignes à 1000 points, c'est le temps et le nombre de call pour un segment ou pour les 1000 ?

Le résultat, c'est bien la longueur de la courbe ?

Comment sur un cercle pourrait-on avoir une meilleure précision avec une subdivision plus faible (tant qu'on ne dépend pas de la précision des doubles).

[Médiat]

C'est le temps pour toute la courbe (donc les 1000 segments de départ).

Je ne comprends pas la dernière remarque, il n'y a que pour les droites que la subdivision n'est pas pertinente

[polo974]

J'ai l'impression que pour la première ligne (à 1 millions de points), l'erreur est plus importante, donc ça doit découler des problèmes d'arrondi en double.

Les doubles ne sont pas des réels, mais des approximations de ces derniers, c'est le gros piège des doubles en informatique.
C'est par exemple pour ça qu'on ne cumule pas les produits matriciels pour une animation 3D, les pauvres matrices se déforment de façon trop visible.

[Médiat]

On a quand même 14 décimales, au pire, on devrait avoir une erreur de l'ordre de 1.E-08, alors qu'elle est de l'ordre de 1E-05

[polo974]

Chaque addition apporte un bruit d'un demi bit max en + ou en - du nombre le plus grand (en module)).

Il faudrait donc déjà veiller à sommer de façon arborescente plutôt que faire une intégration.
(En double 10¹⁰ + 10^-10 donne 10¹⁰)

Ensuite, l'erreur finale est une somme d'erreurs, et donc peut très bien être positive avec 1000000 point et négative avec 1234567 points (juste un exemple) ou quasi nul avec 987654 points, tout dépend de ce qui est sommé (de l'erreur de chaque nombre sommé et de celle résultante de la somme, et vu d'aussi loin, c'est juste du bruit...)

Et en fait, on chipote sur le cas qu'on veut de toute façon éviter...

[Médiat]

Pour revenir sur la question de fond (les échanges précédents ont été très utiles), vous trouverez ci-dessous deux images, l'une calculée en divisant le paramètre en 40 segments égaux (parameter.jpg) et l'autre en divisant la longueur en 40 segments égaux (length.jpg), la courbe en question est celle que l'on voit à l'extrême gauche (et à l'extrême droite) de chaque image. L'image Length.jpg a été obtenue à l'aide de l'algorithme "bourrin" décrit dans mon premier message, et qui est le point important, même si le document fourni par paraboloide_hyperbolique m'a déjà beaucoup aidé.

[Paraboloide_Hyperbolique]

D'après ce que je vois/comprend, il s'agit d'une surface de révolution. Ne serait-il pas plutôt envisageable de recourir à une surface de type NURBS ? (Approximer la courbe génératrice à la précision voulue en la faisant passer par quelques points de la fonction f(v)*, puis générer une surface de révolution**)

*Il existe des algorithmes pour cela.
**Procédure assez standard.

[Médiat]

Salut,

C'est bien une surface de révolution (dans un sens généralisé, la directrice pouvant suivre une courbe fermée quelconque et pas uniquement un cercle).

Je ne vois pas en quoi des NURBS peuvent résoudre mon souci ?

[Paraboloide_Hyperbolique]

Les NURBS peuvent approximer ce genre de surfaces (appelées "surfaces profilées"). Reste à voir si cela pourrait te convenir.

Voir par exemple à partir de la page 29 du cours suivant:

https://www.cgeo.uliege.be/CAO/CAD_06.pdf

[Médiat]

Je n'ai pas de problème pour dessiner la surface, comme le montre les deux figures ci-dessus, par contre, on voit bien sur la deuxième image que la distance entre deux lignes horizontale est très variable, alors que sur l'image 1, cette distance est à peu près constante (aux erreurs de parallaxe prêt), cette image est obtenue avec la méthode bourrin qui ne me plait pas beaucoup, et j'aimerais aussi améliorer la précision sans exploser les performances.