Discussion :

[tchize_]

Bonjour,

J'ai grosso modo le besoin suivant pour une application:
"l'utilisateur place des points d'une courbe 2D dans une zone de dessin, et il faut dessiner la "courbe" qui passe par ces points"

Vu les contraintes techniques, on s'oriente vers du SVG pour le rendu, donc vers des courbes de bézier.
Je cherche donc comment il est possible de déterminer rapidement (réactivité de l'interface) les points de controles d'une courbe de bézier à partir de points où elle doit passer. Et aussi de savoir combien de points de contrôles il faut en fonction des points placés. Je vois plein de programmes réaliser ce genre de chose couramment, mais je ne trouve pas d'algorithme standard pour le faire.

Voir en attachement une idée du visuel auquel je veux arriver.

[pseudocode]

Vu les contraintes techniques, on s'oriente vers du SVG pour le rendu, donc vers des courbes de bézier.
Je cherche donc comment il est possible de déterminer rapidement (réactivité de l'interface) les points de controles d'une courbe de bézier à partir de points où elle doit passer. Et aussi de savoir combien de points de contrôles il faut en fonction des points placés. Je vois plein de programmes réaliser ce genre de chose couramment, mais je ne trouve pas d'algorithme standard pour le faire.

ET bien, c'est parce qu'il n'y a pas vraiment d'algorithme pour faire cela.

Il s'agit simplement de relier le debut d'un segment à la fin du précédent, comme on le ferait pour une ligne continue par morceaux. Les points de contrôle servent uniquement pour "arrondir" les segments.

L'astuce c'est simplement de prendre des points de controle qui sont "miroirs" l'un de l'autre pour l'extrémité commune à 2 segments, afin qu'il n'y ait pas de cassure. C'est d'ailleurs expliqué dans la spec du SVG, cf. la dernière courbe en "S" où le point de controle bleu est miroir de l'autre par rapport au point de passage.



Tout ce qu'il reste à choisir c'est l'orientation des "tiges de contrôle" (= segment formé par une extrémité et le point de contrôle associé). Une méthode simple c'est de prendre la même orientation que la droite reliant les points précédent/suivant. Dans ton exemple, la tige de contrôle du point "2" serait parallèle à la droite "1"-"3".

[tchize_]

mm non, ce n'est pas le but. L'utilisateur n'a pas à choisir les point de controle. Lui il dessine des point de passage et c'est tout. Pour reprendre ton image, c'est comme si, pour chacune des courbes, l'utilisateur avait donné 4 points. A partir de ces quatres points, en supposant le premier et le dernier comme le début et fin de la courbe, il faut calculer les deux points de controle pour que la courbe passe par les deux autres points données par l'utilisateur. Bref, il doit y avoir moyen de dessiner un courbe "naturelle".

Si tu as déjà essayé de dessiner avec des points de controle bézier une courbe qui passe par des points déterminé, tu peux comprendre la complexité de la chose (on change un truc ça bouge à l'autre bout), donc ce n'est productivement pas envisageable pour la performance de l'utilisateur. Lui, il veux bouger des points "sur la courbe".

Maintenant j'ai trouvé une solution qui s'appelle "natural spline", mais les spline, c'est pas du bézier -> ça rentre pas dans le svg final


Pour donner une idée, je dois obtenir à partir des points donnés par l'utilisateur une courbe qui s'approche de ce que sort calc ou excel avec un graphe "x,y courbe"

[pseudocode]

mm non, ce n'est pas le but. L'utilisateur n'a pas à choisir les point de controle. Lui il dessine des point de passage et c'est tout. Pour reprendre ton image, c'est comme si, pour chacune des courbes, l'utilisateur avait donné 4 points. A partir de ces quatres points, en supposant le premier et le dernier comme le début et fin de la courbe, il faut calculer les deux points de controle pour que la courbe passe par les deux autres points données par l'utilisateur. Bref, il doit y avoir moyen de dessiner un courbe "naturelle".

Bon, c'est de ma faute. Je n'ai pas été assez clair.

1. la courbe finale passe TOUJOURS par les points passages, pour la bonne raison qu'on dessine la courbe morceau par morceau et que chaque morceau est une courbe de bezier définie par 2 points de passages consécutifs + 2 points de contrôle.

2. L'utilisateur n'a pas à choisir les points de contrôle: la position des points de contrôle est calculée automatiquement en prenant comme règle que la "tige de contrôle" d'un point de passage est parallèle à la droite formée par les points de passages précédent/suivant.

[tchize_]

je vois ce que tu veux dire. Seulement avec cette méthode j'ai un problème.
A partir de deux points, points de passage, je me retrouve à devoir déterminer déterminer 4 points: deux points de passage et deux points de controle. En rajoutant la contrainte "parallèle", je peux donc forcer un troisième paramètre de mon équation. Mais il reste une inconnue: quelle "distance" donner aux points de controle (au delà de la courbe)

Je vais déjà faire des essais

[tchize_]

bon j'ai fait quelques essais. voir la pièce jointe. En bleu le tracé d'origine (lignes droites). En vert ce qu'on obtient en respectant les pentes pour les deux points. Et encore, en ajustant au visu l'intensité (distance) des controles. En rouge ce que me propose automatiquement inkscape quand je fait ctrl-clic sur les sommets et qui est le genre de courbe que je cherche à obtenir.

Question fondamentale, une idée sur l'algorithme qu'il utilisent?


Je cherche (si ça peux aider) à obtenir quelque chose d'aussi intuitif que ça

http://www.cse.unsw.edu.au/~lambert/.../natcubic.html

[pseudocode]

bon j'ai fait quelques essais. voir la pièce jointe. En bleu le tracé d'origine (lignes droites). En vert ce qu'on obtient en respectant les pentes pour les deux points. Et encore, en ajustant au visu l'intensité (distance) des controles. En rouge ce que me propose automatiquement inkscape quand je fait ctrl-clic sur les sommets et qui est le genre de courbe que je cherche à obtenir.

La méthode que j'ai donné (la droite //) n'est qu'une astuce rapide. Elle permet d'avoir une continuité C1 (continuité de la courbe et de sa dérivée).

Peut-être faut-il pousser plus loin et avoir une continuité C2 (page 4 de la présentation).

Question fondamentale, une idée sur l'algorithme qu'il utilisent?

heu, non. Mais d'après l'image je dirais qu'au lieu de prendre la // au 2 points, ils prennent la tangente.

Je cherche (si ça peux aider) à obtenir quelque chose d'aussi intuitif que ça

http://www.cse.unsw.edu.au/~lambert/.../natcubic.html

Et bien, les sources sont dispo.

[tchize_]

oui les sources sont dispo, et sans solution je les utiliserais, mais ce sont des source pour faire un spline, pas une courbe de bézier. Et les spline, en svg, c'est niet

Merci pour la présentation, mais je suis pas plus avancé, ça me dit pas comment calculer mes valeur à partir de mes points

Ce problème a l'air tellement courant qu'il me semblait que les algos ne devaient pas manquer, mais j'arrive à rien faire sortir de mon amis google

[pseudocode]

oui les sources sont dispo, et sans solution je les utiliserais, mais ce sont des source pour faire un spline, pas une courbe de bézier. Et les spline, en svg, c'est niet

Merci pour la présentation, mais je suis pas plus avancé, ça me dit pas comment calculer mes valeur à partir de mes points

Ce problème a l'air tellement courant qu'il me semblait que les algos ne devaient pas manquer, mais j'arrive à rien faire sortir de mon amis google

Tu as essayé d'utiliser la tangente au lieu de la parallèle ?

Si A,B,C sont 3 points de passage consécutifs, la tangente à la même direction que (vecteur "AB" normalisé) + ( vecteur "BC" normalisé).

[MABROUKI]

bonjour tchize..
Effectivement c'est un probleme que j'appellerai "bete & mechant" à la fois suivant l'expression consacree ...quand j'ai lu le post...

1/"bete" cas de 3 points parce que :
-l'on doit simplement resoudre une equation à 1 inconnue -x-(et la meme equation pour -y-) s'agissant de trouver le 3eme point(pt milieu)
- equation bezier quadratique(2eme degre en -t-) : :
Pc =B(t)= (1-t)^2*P0 + 2*(1-t)*t*P1 + t^2*P2

Trouver Pc1 le pt milieu pour tout -t- dans l'intervalle ouvert ]0,1[ :
Pc devant etre valable -quelque soit t- et sachant que sur un "bezier curve" prendre t=0.5 equivaut à avoir un pt de controle au milieu,t=1/3 un pt de controle au 1/3....etc..
On aura à resoudre si t=0.5:
Pc1.x =(0.5)^2*P0.x + 2*(0.5)*0.5*P1.x + (0.5)^2*P2.x(idem pour y)....

d'ou l'on tirera le "maudit pt de controle" necessaire P1 en permutant:
2*(0.5)*0.5*P1.x =Pc1.x -(0.5)^2*P0.x-(0.5)^2*P2.x


1/quand on traite le cas de 4 points je t'epargnerai les details
- 1ere equation pour P1 sera fixee avec t=1/3 (1er tiers courbe)
- 2eme equation pour P2 sera fixee avec t=2/3 ( 2e tiers courbe)
- equation bezier cubique(3eme degre en -t-) :
Pc1=B(t) = (1-t)^3*P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3
Trouver Pc1 pour t=1/3 :

Resoudre en -x- (& y):
Pc1.x=B(t) = (1-t)^3*P0.x + 3*(1-t)^2*t*P1.x + 3*(1-t)*t^2*P2.x + t^3*P3.x
Permutant:
3*(1-t)^2*t*P1.x=Pc1.x- (1-t)^3*P0.x - 3*(1-t)*t^2*P2.x -t^3*P3.x(eq.1)

Trouver Pc2 pour t=2/3 :
Pc2.x=B(t) = (1-t)^3*P0.x + 3*(1-t)^2*t*P1.x + 3*(1-t)*t^2*P2.x + t^3*P3.x
Permutant:
3*(1-t)*t^2*P2.x =Pc2.x-(1-t)^3*P0.x -3*(1-t)^2*t*P1.x - t^3*P3.x(eq.2)

La valeur de P2.x(eq.2) sera "injectee" dans (eq.1)......et on fera les permutations necessaires pour avoir une formule pour la coord -x- de P1 (& idem pour y).....
La valeur de P1.x etant connue on l ' "injectera" dans l' (eq.2) pour avoir la coord. -x- de P2...
On s'en trouvera à l'aise pour l'algo si on pose :
-P1.x=X1 , P2.y=Y1,P2.x=X2 , P2.y=Y2
-Pc1.x=XC1,Pc1.y=YC1,Pc2.x=XC2.x,Pc2.y=YC2

L'equation quadratique s'ecrirait plus clairement :
2*(0.5)*0.5*X1 =XC1 -(0.5)^2*P0.x-(0.5)^2*P2.xLe systeme à 2 equations cubiques s'ecrirait:
3*(1-t)^2*t*X1 =XC1- (1-t)^3*P0.x - 3*(1-t)*t^2*X2 -t^3*P3.x(eq.1)
3*(1-t)*t^2*X2 =XC2-(1-t)^3*P0.x -3*(1-t)^2*t*X1 - t^3*P3.x(eq.2)

3/ "mechant" :
Je te laisse mediter le cas de -(N-2) points intermediares Pc1...à Pcn (P0 et PN etant exclus car connus) car il va falloir resoudre un system lineaire à N-2 inconnues pour trouver les (N-2) pts de controles ...
Pour ce cas general il faut :
-prendre -(N-1) valeurs differentes- de t ...en "progression arithmetique" regulierement espacees :
Pour chaque pt de controle Pi : ti = i *1/n ,i=0....à N
-Chaque -ti- engendrera une equation avec N-2 inconnues et necessitera le calcul des fameux coeff de Bernstein B(i,n) pour chaque Pi

Au final le systeme Ax=B à resoudre comportera :
- la matrice A d'ordre (N-2) :un tableau (N-2,N-2) avec les coeff de Bernstein concernes(P0 et PN exclus).....(i=1 à N-1)
- le vecteur-colonne B second membre plus simple à calculer d'ordre (N-2): tableau (N) avec comme element ci-P0-PN (i=1 à N-1)

-trouver un bon "algo" d'inversion de la matrice A (gradient cpnjugue ou autre) .....

Sur ce lien on discute d'un algo pour l'equation quadratique:
http://www.google.fr/url?sa=t&rct=j&...HVMFL-LBQQ1LZQ
Sur ce lien on discute d'un algo pour l'equation cubique:
http://www.google.fr/url?sa=t&rct=j&...O72dKDXtKx2osQ

Pour les coeff. de Bernstein il faut faire attention à ne pas programmer un algo de simple factorielle "penalisant bloquant en memoire" mais un algo de simple boucle .....
bon algo...................

[tchize_]

ça y est, j'ai mal à la tête

blague à part, on va se contenter de l'algorithme des spline, car, apparament, on s'oriente vers des format de fichiers ne gérant que le polygonal. Donc on va être obligé de toutes façons de décomposer la courbe en segments de droites. Je n'ai pas trouvé de format géographique supportant des dessins complexes comme du bézier


Je marque résolu, un grand merci

[souviron34]

blague à part, on va se contenter de l'algorithme des spline,

C'est effectivement le seul simple à metttre en place si on veut passer par les points.

Si tu es intéressé, j'avais fait, pour justement du dessin sur un SIG, une petite fonction "souple" passant par les points, et s'adaptant.. (une combinaison d'un cos et d'une puissance), qui évitait les inconvénients oscillatoires lors de points très rapprochés et permet d'avoir un dessin "souple" néanmoins.. (si tu es intéressé, envoie un MP. Mais je la mettrais peut-être sur Contribuez si ça intéresse du monde)

Un exemple ci-joint

Je n'ai pas trouvé de format géographique supportant des dessins complexes comme du bézier

ben la raison est dans ta phrase même : format géographique..

Mettre une courbe indique un interpétreur, ce qui n'est pas le but des formats géographiques.

Tu as alors 2 solutions :

• te faire un format "interne" (ce que moi j'ai fait) afin de gérer des dessins complexes
  
  
• effectivement stocker des segments, avec autant de points que tu peux pour la précision souhaitée

Tout dépend dans quel but tu fais ça : créer puis transmettre un fichier lisible de l'extérieur, ou créer/transmettre un fichier lisible, mais interprétable via un soft (le tien par exemple)

[tchize_]

te faire un format "interne" (ce que moi j'ai fait) afin de gérer des dessins complexes

On préfère se baser sur des formats standardisés, pour éviter les pirouettes de lecture dans 5 ans quand tout le monde aura oublié comment est ce format custom qu'on a créé Le format kml permet de faire les deux (metadata additionnelle pour les points de passage et segment pour les interpréteurs ne reconnaissant pas ces méta données).

De toutes façons, pour le moment, c'est juste de la prospection

PS on aura peu de points rapproché, l'opérateur placant a priori 4 ou 5 points maximum. Il doit encore animer tout ça après, donc plus il a de points, plus il a de boulot

[souviron34]

et MapInfo ne permet pas ça ?? ils n'ont pas inclus ce genre de possiblités (je n'ai pas touché depuis plus de 10 ans) ??




PS: en aparté, j'ai un gros problème avec la manière dite "standard" de se passer des données géo-référencées, et la notion de meta-data telle qu'elle est définie par le OGS, mais ceci est une autre histoire

[MABROUKI]

Rebonjour tchize..
En fait j'ai expose le probleme dans toute sa generalite....pour eviter que tu ne sois tente par la generailisation.... car c'est une voie de recherche impraticable sur un plan pratique ....

Pour le cas de -N points - mettons 10 il suffit simplement de generer soit la quadratique (2 pts de controle à calculer) ou plus simple encore la cubique (un pt de control à calculer) comme deja habilement suggere par pseudocode...

Si on prends l'exemple de la cubique ,chaque courbe est mise bout à bout avec la suivante .....
Donc apres avoir saisi les points "user" P0.....P10 on cree des cubiques mises à bout et "tangentes" :

Etat initial :
-Calcul de la 1er cubique entre P0 et P1.
-en fixant un pt de controle Pc1 avec t=0.5.(cela repond à ta question distance du point de control).

k=2
Etat itere: pour Pk à P10 faire (variable Pk)
- generer cube suivante : Pk-1 à Pk
- calculer le pt de control Pck avec condition "tangence"des courbes
(dramatiquement simple).
Pck doit etre simplement le "symetrique"(miroir suivant pseudocode) du pt de control Pck-1 (symetrie par rapport au point Pk-1 de la courbe courante) soit :

Pck.x=Pk-1.x-(Pk-1.x-Pki-1.x) (idem y).....

repeter tant que k<10

Le calcul de chaque pt de controle depend du precedent............qui est finalement le 1er....

L'algo dans le cas de la cubique demande 5 minutes pour etre implemente:
1/-tenir à jour une Liste des pts de passage P0....P10.
2/-tenir à jour une Liste des pts de controle Pc0 à Pc10 (en y incluant P1 et P10 car ils ont une double nature).

Cette 2eme liste a une autre utilite en rapport avec l'aplatissement de la courbe de bezier en ligne polygonale("flatenning")

3/-faire le traitement de l'algo ci-dessus..

Par ailleurs il n'est pas de toute necessite que l'user "voit " les fameux pts de controle.Il lui suffit d'afficher les pts de passage :
P0 Pc1 P1 Pc2 P2 Pc3 P3........P9 Pc10 P10 qu'il ajustera à son avantage.....

Ceci est du -à cette observation au passage -que l'Algo ci-dessus peut etre appele illico presto si l'user deplace un pt de passage quelconque.....moyennant notre procedure CreateControlPoints()

Un "ingredient" indispensable au moment de l'aplatissement en ligne polygonale approximante de notre courbe c'est :
-elever le degre d'une courbe sans changer sa forme (dans la litterature anglophone) c.à.d multiplier ses points de ctrl (sujet effleure par pseudo-code).C'est cela le "razoir d'occam" de Mr Bezier.
Il suffit d'une procedure SplitControlPoints :
-à chaque appel elle prend notre 2eme Liste(points de ctrls courants) et cree une Nvelle Liste de points de ctrl en remplacement comme suit :
partant de P0 creer un pt de ctrl entre :
-P0-Pc1, Pc1-P1,P1-Pc2, Pc2-P3 et ainsi de suite.......et abandonner la liste courante....

NB: seuls les 2 "hermaphrodites" P0 et P10 figure dans la nouvelle liste tels quels...
En fait c'est le vieux artifice de geometrie elementaire(approximer un cercle par une ligne polygonale) à l'oeuvre.....

A chaque clic la ligne polygonale se ressere autour de la courbe et elle est est "visualise" à l'user qui peut alors intervenir dessus pour la finition des sommets...
Quand il a termine ,voulez-vous l'aplatir (flatten the curve)?..
Oui et ...la 1ere liste (points de passage) est abandonnee au profit des pts de controls(ligne polygonale)....et on redessine une ligne polygonale à la place du bezier curve...

Je m'excuse d'insister la dessus mais c'est parce que je n'aime pas l'inelegante methode anglaise des splines avec ses "knots" et ses "points" de controls....
Comme aurait dit pseudocode ,je me suis peut etre mal exprime....ou incompletement..
sur ce lien un article bien clair qui illustre l'algo de l'elevation de degre:
http://www.google.fr/url?sa=t&rct=j&...0wj45eEBkN41ZQ

bon courage...........

[souviron34]

Je m'excuse d'insister la dessus mais c'est parce que je n'aime pas l'inelegante methode anglaise des splines avec ses "knots" et ses "points" de controls....

Je m'excuse d'insister, mais que vois-tu d"inélégant" dans les splines ? Pour info, il n'y a pas de points de contrôles dans leur utilisation normale : c'est le but de passer par les points.. en assurant la continuité de la dérivée premiere ET seconde...


Mais ils sont fait pour interpoler et lisser une courbe, en général.. Pas pour faire (en général) ce pour quoi ils seraient utilisés dans ce cas de figure.. C'es tout..

En général, je n'aime pas les Béziers justement parce que ça ne passe pas par les points, et qu'il faut s'arracher les cheveux pour trouver ce qu'l faut. Mais mon domaine est de lisser des courbes réeles, sur lesquelles les points ont un sens là où ils sont (une mesure, par exemple). . Mais en ce qui concerne le dessin "à main levée", soit une Bézieers, soit le genre de courbe dont je parlais (qui passe par les points, est continue en dérivée et en dérivée seconde), est simple à mettre en oeuvre et sans calculs complexes..

[tchize_]

que ce soit clair, dans mon cas de figure, les points de passage sont placé (3 à 5) par l'utilisateur, ça dessine une courbe et l'utilisateur ajuste les point pour que la courbe aie la "gueule" qu'il veux lui donner. En ce sens pour moi, peux importe donc l'algorithme utilisé. J'avais posé la question de bézier car on envisageait du svg et que, en svg, on a bézier mais pas spline. En pratique, on a quitté bézier, donc pour moi peu importe l'algorithme utilisé. J'ai un truc qui marche avec les splines, je vais pas me casser la nenette plus loin

[asmaeH]

Bonjour,

sauriez vous si le même principe existe pour des surfaces,
la méthode: carreaux de Béziers construit une surface à partir de points de contrôles en 3d , voir le lien: http://www.paris-lavillette.archi.fr...e_BezierTC.htm
Or moi je veux forcer ma surface à passer par des points précis.


auriez vous une idée?

je vous remercie

[Alex64]

Bonjour,

J'ai grosso modo le besoin suivant pour une application:
"l'utilisateur place des points d'une courbe 2D dans une zone de dessin, et il faut dessiner la "courbe" qui passe par ces points"

Vu les contraintes techniques, on s'oriente vers du SVG pour le rendu, donc vers des courbes de bézier.
Je cherche donc comment il est possible de déterminer rapidement (réactivité de l'interface) les points de controles d'une courbe de bézier à partir de points où elle doit passer. Et aussi de savoir combien de points de contrôles il faut en fonction des points placés. Je vois plein de programmes réaliser ce genre de chose couramment, mais je ne trouve pas d'algorithme standard pour le faire.

Voir en attachement une idée du visuel auquel je veux arriver.

voici en pièce jointe un algorithme Pièce jointe 153701

[tchize_]

merci pour le doc, j'y jetterais un oeil. Au final, on est parti sur l'idée de laisser simplement l'utilisateur positionner les points de contrôle plutôt que de dessiner la courbe et ça leur convient.