# lisser une courbe



## peon.master (19 Mars 2004)

Hello.
J'en appelle aux matheux, car ma question ne concerne pas directement la programmation. J'aimerai lisser une courbe. c'est-a-dire, rajouter des points aux bons endroits entre les points déja existants [2D].

Donc mon idée de départ, c'est de traiter les points 3 par 3. Je crois savoir que si trois points existent (et qu'ils ne sont pas alignés), il existe un cercle qui passe par ces trois points. Donc ma question c'est
- comment trouver le centre de ce cercle?
- c'est la bonne maniere ou il y en a une autre, meilleure?


----------



## Luc G (19 Mars 2004)

peon.master a dit:
			
		

> Hello.
> J'en appelle aux matheux, car ma question ne concerne pas directement la programmation. J'aimerai lisser une courbe. c'est-a-dire, rajouter des points aux bons endroits entre les points déja existants [2D].
> 
> Donc mon idée de départ, c'est de traiter les points 3 par 3. Je crois savoir que si trois points existent (et qu'ils ne sont pas alignés), il existe un cercle qui passe par ces trois points. Donc ma question c'est
> ...



Un cercle, ce n'est pas trop la bonne manière. Il existe d'assez nombreuses possibilités (à commencer par tracer des segments de droite 
	

	
	
		
		

		
			





).

- Quand on veut une équation simple (et pas seulement les points), on approche par une fonction qui a des chances d'approche correctement la courbe : polynôme de degré pas trop élevé, exponentielle ou logarithme par exemple;

- Quand on veut obtenir une "belle" courbe du genre de celle qu'on fait avec illustrator (ou avec un autre logiciel y compris dans le module vectoriel d'appleworks), où tu as des points de conduite et des poignées qui te permettent d'ajuster la courbe à ton goût, on utilise souvent des fonctions spline (les courbes de bézier par exemple). C'est ce genre de truc qu'il te faudrait, je pense.

En fait, c'est assez simple (pour peu qu'on n'ait pas besoin de rajouter les poignées des courbes de Bézier. Par exemple, pour les B-spline

- entre 2 points, on approche par un polynôme de degré 2 ou 3 en général
- on impose que les de courbes entre A et B d'une part , entre B et C d'autre part, passent toutes 2 par A évidemment mais en plus que leurs dérivées soient égales en A (comme ça, on n'a pas de "cassure", la courbe est lisse) ou même que leurs dérivées secondes soient aussi continues (degré 3).

On construit donc une fonction "polynômiale par morceaux" qui passe par les points voulus et qui est bien lisse.

Il y a des algorithmes assez simples pour faire ça. Il y a bien longtemps, j'ai fait un programme sur mac qui permettait de faire des approximations diverses et variées : régressions polynômiales, exponentielles, log, mais aussi des B-spline. Le programme tourne toujous sous classic d'ailleurs (avec quelques bogues, mais il avait les mêmes au départ, c'était un truc vite fait pour des besoins spécifiques).

Tu peux chercher sur le net, je pense que tu peux trouver un outil de ce type ou les algos nécessaires, fais une recherche sur "B-spline".


----------



## arnolix (21 Mars 2004)

Ok pour ce que tu dis Luc, mise à part que les fonct log et exp ne sont pas des polynômes et consomment beaucoup plus de temps de calcul que ces derniers si on ne prend pas des précautions (optimisation).

Cependant il me semble que la classe NSBezierpath utilise justement les courbes de Bezier comme son nom l'indique. Il devrait être donc tout à fait possible de réaliser un lissage avec les fonctions de cette classe. En se plongeant dans la doc on devrait y trouver la réponse. Non ?


----------



## Luc G (21 Mars 2004)

arnolix a dit:
			
		

> Ok pour ce que tu dis Luc, mise à part que les fonct log et exp ne sont pas des polynômes et consomment beaucoup plus de temps  de calcul que ces derniers si on ne prend pas des précautions (optimisation).



Évidemment, log et exp ne sont pas des polynômes 
	

	
	
		
		

		
		
	


	




 (honte sur moi si tu as pensé que je confondais  
	

	
	
		
		

		
		
	


	




), ce sont d'autres exemples de fonctions de base qu'on peut utiliser à la place des polynômes. Ils peuvent être moins rapides mais ce n'est pas forcément gênant vu la vitesse des procs aujourd'hui, en particulier en 2D. Et si tes données représentent un phénomène de nature exponentielle, une exponentielle est la bonne solution mathématique au problème si on veut une solution explicite. L'intérêt d'avoir une fonction explicite (polynôme, exponentielle, log ou autre) est qu'on a une écriture simple de la fonction  facile à utiliser partout. Ce n'est pas pour rien qu'on fait souvent des régressions linéaires : on a une solution analytique par opposition à avoir des points. On ne cherche d'ailleurs pas, à passer par les points mais à proximité des points.

Quand on travaille avec des polynômes par morceaux, on raisonne autrement : on ne s'intéresse pas tellement à l'écriture de la fonction (elle est beaucoup trop complexe globalement même si localement c'est un polynôme de degré peu élevé). On peut avoir une courbe qui approche beaucoup mieux les données (ce qui est primordial sur le dessin) mais on n'a pas une écriture analytique qu'on puisse reprendre ailleurs. Souvent (pas toujours) on veut passer effectivement par tous les points donnés

Les besoins couverts sont donc différents sauf lorsque la courbe analytique est suffisamment proche des données ou lorsqu'on a un nuage de points qui rend assez illusoire la construction d'une approche beaucoup plus sophistiquée qu'une fonction analytique simple.



			
				arnolix a dit:
			
		

> Cependant il me semble que la classe NSBezierpath utilise justement les courbes de Bezier comme son nom l'indique. Il devrait être donc tout à fait possible de réaliser un lissage avec les fonctions de cette classe. En se plongeant dans la doc on devrait y trouver la réponse. Non ?



Ça me paraît logique, effectivement mais je ne connais pas ces nouvelles API (ça n'existait pas à l'époque  
	

	
	
		
		

		
		
	


	




). Il est de toutes façons toujours préférable, au moins au départ, d'essayer d'utiliser des outils qui ont en principe été testés et optimisés que de vouloir réinventer la roue. Ça me parait fondamental dans la programmation moderne.


----------



## Eddy58 (22 Mars 2004)

La méthode "setFlatness" de la classe NSBezierPath est dédiée au lissage. Plus ta valeur tendra vers 0, plus tu auras de points dans ton path.


----------



## peon.master (22 Mars 2004)

Eddy58 a dit:
			
		

> La méthode "setFlatness" de la classe NSBezierPath est dédiée au lissage. Plus ta valeur tendra vers 0, plus tu auras de points dans ton path.



Oui je suis d'accord, mais je ne peut pas récupérer tout ces points (coordonnées) pas la suite. La méthode "elementAtIndex:associatedPoints:" ne permet pas (ou alors qu'on m'explique) d'accéder aux points d'une courbe par exemple, ca retourne les points de controle de la courbe.
Finalement je vais peut être faire encore quelques tests avec ça.

Mes points sont au fait des objets-point et contiennes d'autres informations (selection, appartenance a une courbe, pointeur sur le point auquel il est relatif..) Je préfèrerais ne pas avoir recours au NSBezierPath pour ca.

La vitesse de calcul n'est pas primordiale car il s'agit là d'un programme de dessin vectoriel auquel je vais ajouter la fonction de lissage de courbe.
Je vais voir ce que je peux faire avec les B-Splines...

Je vais détailler ma manière une fois que j'aurai réussi si ça intéresse qqn.


----------



## la tortue (23 Mars 2004)

> Oui je suis d'accord, mais je ne peut pas récupérer tout ces points (coordonnées) pas la suite. La méthode "elementAtIndex:associatedPoints:" ne permet pas (ou alors qu'on m'explique) d'accéder aux points d'une courbe par exemple, ca retourne les points de controle de la courbe.


La méthode -[NSBezierPath elementAtIndex:associatedPoints: ] permet d'accéder aux points de la courbe et aux points de contrôle. La méthode renvoie le type d'élément (moveTo, curveTo, lineTo) et dans le tableau que tu passes en paramètre, elle renvoie dans l'ordre (ou pas) le point1, le point de contrôle 1, le point de contrôle 2 et le point 2 (suivant le type d'élément).


----------

