Discussion :

[Lintel-oo]

J'ai un peu réfléchi et je me suis posé une question :
Cette idée de lien entre 2 espaces est intéressante mais je trouve qu'elle pose certains problèmes avec ce que je fais.

Imaginons en effet cette classe :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
template <typename T, typename U>
class Curve
{
    private :
        Interval<T> m_definitionInterval;
        Interval<U> m_functionInterval;
 
    public:
 
        // fonctions a specialiser pour chaque type de curve
        template <typename V>
        std::list<U> getSolution(T val);
 
        template <typename V>
        T getValue(U value);
};

C'est cool : on peut spécialiser chaque fonction pour chaque type de courbe, eventuellement via des politiques pour empecher l'appel à une fonction non spécialisée, mais cependant, imaginons une courbe polynominale de degré 1, 2 ou 3 : comment avec ce schéma stocker les paramètres de la courbe, à savoir les 2,3 ou 4 coeff de la courbe ? Ici cela me paraît impossible sans faire quelque chose d'assez laid au niveau du code.

De plus, imaginons que je désire inclure un attribut de type pointeur sur curve, correspondant à la fonction appelée en premier dans une fonction composée : lors de l'instanciation d'une fonction curve, on pourrait choisir de la définir en fonction non pas de x mais d'une fonction de x (en fait j'explique très mal mais c'est juste le principe d'une fonction composée).
Concernant le type de la fonction composée de la Curve<T,U> déclarée,il ne s'agit pas forcément d'une curve de type Curve<T,U>. Au contraire, puisque c'est la "base" d'une fonction composée, elle est du type Curve<V,T>, puisque ses images correspondent aux "antécédents" de la courbe ayant cette fonction composée en attribut.
Je ne sais pas si vous m'avez suivi puisque je le répète j'explique très très mal enfin toujours est-il que si on considère cela on est obligé de rajouter des paramètres template infinis puisque chaque Curve peut être une fonction composée :

Curve<T,U> déclarée -> Curve<V,T> comme composée, qui est elle même une composée de Curve <W,V>, pouvant être également une composée -> Curve <X,W> et ainsi de suite
==>> impossible de définir la classe curve avec un nombre de paramètres template fini

Comment puis-je alors contourner tous ces problèmes, tout en respectant LSP (en espérant que vous m'ayez compris )

Merci par avance !

[Flob90]

Pour les fonctions composé :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
template<class T, class U, class V>
Curve<T,V> compose(const Curve<T,U>&, const Curve<U,V&);

Après il y a d'autre problèmes mais ...

Il est vraiment difficile de te donner des solutions à des problèmes de conceptions sans savoir où tu vas. Quel est ton objectif final ? A quoi va te servir ta classe Curve ?

[Lintel-oo]

Pour faire simple, j'avais déjà plus ou moins bien codé ce que je voulais, avec de l'héritage (comme je l'avais dit au début), afin notamment de programmer le comportement de n'importe quel objet dans un espace bidimensionnel avec 2 curves, ou tridimensionnel avec 3 curves de façon simple et assez rapide : on définit l'intervalle de définition de la courbe, correspondant à un intervalle de temps, et on obtient les différentes valeurs de la courbe pour différents temps, qu'on assigne à la position de l'objet en X, Y ou Z.

Ensuite, je me suis demandé, notamment pour la création d'un jeu de type worms, comment faire en sorte de savoir quand un objet explosif ou non entrait en collision avec le terrain, sans utiliser le pixel perfect .

J'ai décidé que ce terrain serait constitué de courbes du 3eme degré établies à partir d'un bruit de perlin ayant subi de nombreuses transformations, histoire de rendre le défi intéressant. Pour trouver ces équations, je dois donc résoudre les équations de type ax^3+bx²+cx+d = Y, et ce Y allant de Ymin de l'objet à Ymax, afin d'être certain de ne pas louper de collision dans le cas notamment d'un gros objet.

Dans ce cas là, il n'est pas très difficile de résoudre l'équation, c'est d'ailleurs le cas pour toutes les fonctions de base (racine, exp, ln, sin, cos ...).

Cependant, cela se complique (très) fortement lorsqu'on ajoute des composées. Pour rendre mon espèce de "moteur de courbes " plus intéressant, j'ai décidé qu'on ne puisse pas seulement utiliser des fonctions simples mais aussi des fonctions beaucoup plus complexes en pouvant remplacer le paramètre x par une autre curve, pouvant elle aussi être composée, etc ...

Les équations sont alors beaucoup plus dures à résoudre, et cela pose également des problèmes d'intervalle. Il devient alors nécessaire d'inclure la notion de tableau de variation et de tableau de signe, ainsi que de dérivée. Sans eux, pas de résolution d'équation envisageable dans certains cas.

C'est pourquoi j'en arrive à ce que je veux obtenir, à savoir un "moteur" de courbes capable de déterminer les solutions d'équation d'une majorité de type sauf de sommes et de différences à moins que je décide d'y inclure plus tard un mode de recherche par dichotomie.

Voilà, j'espère que je n'ai pas trop mal formulé le problème

Edit : le nom du post n'a plus grand chose à voir avec le sujet actuel, je pourrais le changer ^^. Et je pourrais également passer en non résolu à nouveau

[Flob90]

Ton objectif c'est la résolution analytique, numérique ou les deux ?

Tu as besoin de gérer quoi comme opération sur les fonctions ? (Composition mais quoi d'autre)

Quel intérêt tires tu des tableaux de signes, de variations et du calcul de la dérivé ? Es-tu certain que le gain qu'elles apportent est supérieur aux coût qu'elles ont ?

[Lintel-oo]

Mon objectif est essentiellement la résolution numérique bien que la résolution analytique soit parfois inéluctable pour permettre la résolution numérique.

A vrai dire l'utilisateur choisit lorsqu'il veut calculer le tableau de signe ou de variation, ou la dérivée, d'une fonction, donc ce n'est pas obligatoire et il vaut mieux ne pas le faire lorsque c'est possible.

Enfin, pour l'instant je ne compte pas permettre d'autres opérations sur les fonctions que la composition, car :
-1 : pour l'instant je n'ai besoin que de ça
-2 : je ne vois pas ce que je pourrais inclure de plus, ça viendra avec le temps je pense

Que me conseillerais-tu comme design pour parvenir à cela ?

[Invité]

Salut,

l'approche pour les dérivées, j'imagine que c'est pour dresser la croissance/décroissance de la fonction, et de pouvoir discuter ensuite sur les éventuelles solutions de yMin<=f(x)<=yMax

Bon, c'est une prise de tête. Pour chercher cet éventuel x, je propose la fonction g à minimiser, telle que
g(x) = | E( f(x)/(yMax - yMin) )| *1000
l'idée étant que si f(x) est dans l'intervalle [yMin;yMax] alors on pénalise pas d'un coeff 1000...

Après bon, ca dépend de f, si elle est biscornue quand elle tape dans [Ymin;Ymax] alors ca va être la mort pour l'initialisation du solveur, mais on espère que tu composes avec des fonctions continues pas trop crapuleuses...

edit:

je ne compte pas permettre d'autres opérations sur les fonctions que la composition

Si t'autorises la composition, t'autorises pas mal de choses...
si tu prends la fonction f(x) = cst + x
et que tu la composes, tu effectues une addition.
idem f(x)=multipl * x
Je parle même pas des intervalles qui peuvent devenir taquins si tu composes une heavyside des sinus, et cie

[Flob90]

Si tu fais des résolutions numériques, alors l'algorithme de résolution va consister à parcourir l'ensemble de l'intervalle de départ et à retourner l'ensemble des éléments dont l'image est suffisament prend du résultat voulu.

Dans ce cas je partirais sur :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
template<class, class>
class Curve;
 
template<class T, class U, class V>
Curve<T,V> compose(const Curve<U,V>&, const Curve<T,U>&);
 
template<class T, class U>
class Curve
{
  std::function<U (T)> f;
  Space<T> s;
 
public:
  template<class F, class S>
  Curve(F f, S s) : f(f), s(s) {}
  template<class S>
  Space<U> image(S) const
  { /*algo 1*/ }
  template<class S>
  Space<T> solution(S) const
  { /*algo 2*/ }
  Space<T> definition() const
  { return s; }
 
  template<class V>
  friend Curve<T,V> compose(const Curve<U,V>&, const Curve&);
  template<class V>
  friend Curve<V,U> compose(const Curve&, const Curve<V,T>&);
};
 
template<class T, class U, class V>
class ComposeF
{
  std::function<U (T)> rhs;
  std::function<V (U)> lhs;
 
public:
  template<class F1, class F2>
  ComposeF(F1 lhs, F3 rhs) : rhs(rhs), lhs(lhs) {}
  V operator()(T t) const
  { return lhs(rhs(t)); }
};
 
template<class T, class U, class V>
Curve<T,V> compose(const Curve<U,V>& lhs, const Curve<T,U>& rhs)
{ return Curve<T,V>(ComposeF(lhs.f,rhs.f),rhs.s); }

Ensuite il manque un élément important, c'est la classe Space<>. L'idée c'est que ce soit un type erasure qui permet de manipuler différent type "d'espace", segment, interval, union (finie), intersection (finie). Et se comportant "comme" (au moins en partie) un conteneur. Ainsi les 2 algo vont être des boucles for sur ces espaces et vont construire les espaces voulus en utilisant le foncteur. Renseignes toi sur l'idée de type erasure (article de Alp Mestan sur le sujet sur developpez.com), c'est un point délicat.

Il manque aussi une fonction (membre ou libre ?) permettant de restreindre l'espace de départ. Et je ne les ai pas mis, mais ils faut protéger les fonctions avec des assertions qui vérifient si les espaces sont corrects :

• Si l'espace donné à image est bien inclut dans l'espace s
• Si l'image de l'espace de départ de rhs est bien dans l'espace de départ de lhs

@galerien69: Avec la composition tu n'autorises pas les additions et multiplication de fonctions. Resoudre (analytiquement) (f.g)(x)=cst c'est relativement simple si on connait f et g, alors que résoudre (f*g)(x)=cst ou (f+g)(x)=cst, l'est beaucoup moins. Par contre numériquement la difficulté est la même.

NB: Code non testé, j'ai pas de compilateur sous la main.

[Lintel-oo]

@galerien69 :

Effectivement

En fait je comptais également faire des multiplications de courbes mais pas des additions, du moins faire en sorte qu'il soit impossible de calculer le tableau de variation et de signe de somme de fonctions, car après c'est trop compliqué à gérer au niveau de la recherche de solutions

Je n'ai pas super bien compris ton histoire de fonction g à minimiser, peut-être pourrais-tu m'en dire plus ? Ce serait pour m'éviter de trouver les dérivées ?

Je précise également que je ne travaille qu'avec des fonctions continues sinon ce serait le chaos total bien que j'entrevoie de créer une courbe pouvant regrouper plusieurs fonctions sur différents intervalles pour pouvoir faire plein de choses par la suite

@ Flob90 :
Je vais bien regarder tout ça ce qui me paraît très intéressant !

[Invité]

@galerien69: Avec la composition tu n'autorises pas les additions et multiplication de fonctions. Resoudre (analytiquement) (f.g)(x)=cst c'est relativement simple si on connait f et g, alors que résoudre (f*g)(x)=cst ou (f+g)(x)=cst, l'est beaucoup moins. Par contre numériquement la difficulté est la même.

oui, je m'en suis rendu compte avant de partir. C'est un problème intéressant auquel j'ai pas du tout réfléchi pour l'instant...

fonction g à minimiser, peut-être pourrais-tu m'en dire plus

l'idée, c'est que il existe des solveurs tout pret qui font le travail pour toi à savoir:
tu donnes une borne xInf (ex:0) une borne xMax (ex:1000) et une fonction f, et tu appèles solveur(f,xInf,Xmax) qui te retourne la valeur de x qui minimise f. De cette manière, tu as pas besoin de te fouler.

edit2: bien que peu d'interêt pour cette discussion, ca reste quand même intéressant.

Resoudre (analytiquement) (f.g)(x)=cst c'est relativement simple si on connait f et g, alors que résoudre (f*g)(x)=cst ou (f+g)(x)=cst, l'est beaucoup moins

Je ne vois pas la différence entre f.g et f*g.
Mais je ne vois pas non plus le rapport entre résoudre (f+g)(x)=cst et l'assertion la composition n'autorise pas l'addition.
pour ma part, je concois les choses comme u(f(g(x)) = f(x)+g(x)
et moyennant la bijectivité de f et g (...), u(x) = f(g^-1(f^-1(x)))+f^-1(x)

[Lintel-oo]

Je pense que par f.g flob90 sous entendait la composition des 2 fonctions, donc ce n'est pas f*g

Il est ainsi plus facile de résoudre f.g = cste que f*g = cste :
pour résoudre f(g(x)) = cste, il suffit de résoudre f(X) = cste, puis g(x) = X, on a alors les solutions x, même si je pense ne rien apprendre à qui que ce soit

Alors que pour résoudre f*g = cste ou f+g = cste, il faut passer par la dérivée et établir une approximation de x dans une majorité des cas, sauf si il s'agit de résoudre f*g = 0

[Invité]

ah, ok normalement la composition est notée fog.
Cela dit, ca change pas que je vois pas le rapport.
Ni que de toute façon que c'est du détail (qu'on me reprenne s'il y avait un sous entendu derrière cette subtilité).

Le fait est que si tu veux dans un cas général composer plein de fois des fonctions continues, et de savoir si la fonction résultante tape bien dans l'intervalle [ymin;ymax] alors aborder le problème par étude de variation est oufzor (idem j'y crois pas, mais qui sait, ...).
Le deuxième point c'est que c'est quand même plus pratique quand on se passe des expressions analytiques (genre sinon va faloir un interpréteur).

Du coup, j'opterais vraiment pour un algorithme basé sur ta fonction f résultante.
A partir de là, tu peux implémenter le tiens, ou te servir d'un solveur.
Le problème du solveur, c'est qu'il est dépendant de l'initialisation et que tu peux passer a coté de solutions éventuelles. Il faut connaitre son l'implem (du moins lalgo) du solveur pour pas avoir de résultats imprévus, mais je pense que partir sur la minimisation que j'avais proposée est concluante.

[Flob90]

<HS>
@galerien69: Dans mon message le . (oui je sait bien que normalement c'est o, sauf que je trouve le . plus clair sur un forum, et c'est la notation utilisée par Haskell) indiquait ici l'opérateur de composition. La suite de mon message était pour souligner que la composition est le cas le plus simple à traiter analytiquement (et c'est d'ailleurs pour ca que j'avais demandé si il voulait faire analytiquement ou pas et si il avait autre chose que des composition). Pour ce qui est de mon assertion, (R^R, .) et (R^R, +) (ou (R^R, *)) ne sont pas isomorphes (fondamentalement car un des oéprateur est commutatif et l'autre non). Et la bijectivité que tu supposes est quelque chose de très fort, trop fort pour l'op.
</HS>

[Lintel-oo]

J'ai du mal à comprendre ce que fait le solveur et à partir de quoi il le fait.

Pouvez-vous m'en dire plus et éventuellement ou en trouver ?

Je ne sais également pas ce qu'est la minimisation d'une fonction si comment trouver la fonction résultante !

[Invité]

La suite de mon message était pour souligner que la composition est le cas le plus simple à traiter analytiquement.

Je suis (évidemment) ouvert sur ta méthode de procéder pour savoir si on tape dans le fameux [ymin;ymax].

Je vois pas trop comment tu peux te servir de la propriété "uniquement des compositions" pour arriver à une solution simple.

[Invité]

Pouvez-vous m'en dire plus et éventuellement ou en trouver ?

tu as par exemple gsl qui propose cette fonction

Typiquement tu poses x=0, et xMax=beaucoup
(je crois que x est un temps donc positif), et de fait tu as plus qu'à cueuillir la solution si elle existe.

[Flob90]

Si je connais analytiquement les solutions à f(x)=y et g(x)=y, alors je peux calculer directement les solutions. Ainsi pour résoudre f(g(x))=y, alors il suffit de calculer les z tel que f(z)=y puis les x tel quel g(x)=z pour tout les z.

[Lintel-oo]

En fait ça revient à ce que j'avais fait au départ (cf le début du post même si je n'explique pas vraiment comment je fais) mais ça ne respecte pas LSP

J'utilise en effet une classe Curve dont hérite chaque autre courbe : RacineCurve, PolynominalFirstDegreeCurve, ExpCurve etc...

L'avantage est qu'on peut définir un nouveau comportement à chaque fois pour la résolution d'équation, l'inconvénient c'est que ça respecte pas LSP puisque pour des courbes comme RacineCurve il faut restreindre les valeurs de x aux valeurs positives. Pour les composées j'avais trouvé un système sympathique mais assez lourd pour résoudre les équations, puisqu'il fallait à chaque fois réécrire de nombreuses lignes de codes

Voilà pourquoi il fallait que je trouve autre chose, ce que je suis en train de faire

[Lintel-oo]

Je ne sais même plus à qui je réponds
Toujours est-il que je me souviens maintenant pourquoi j'ai besoin de calculer des dérivées ! (je vous en dirai plus après avoir mangé ^^)

[Flob90]

C'est quoi qui "revient à ce que tu avais fait" ? Ce que je vient de dire ? C'est étrange puisque tu m'as dit que tu résolvais numériquement et pas analytiquement.

Si c'est le cas, alors une solution est d'ajouter un second foncteur qui retourne l'espace réciproque à un singleton. Ensuite c'est à ta factory d'initialiser correctement ta curve avec le foncteur et le foncteur réciproque qui convient.

[Invité]

Si je connais analytiquement les solutions à f(x)=y

ouais mais le problème, c'est que tu sais pas si f(x)=y admet des solutions, et si c'est pas le cas, il faut tenter f(x+epsilone) et ainsi de suite tant que pas de solutions. Ce qui au final est peut-être un peu lourd (mais mérite réflexion).