Diminution de courbe

[Nuwanda]

Hello.

J'ai un petit soucis en algo et cela dépasse de loin mes compétences en la matière. Pour vous donner le contexte : je dois développer une librairie de courbe. Jusque là pas de problèmes. Sur cette courbe, on peut régler le début et la fin et aussi avoir un aperçu de la courbe un peu à la manière de ce qui est possible ici : http://code.google.com/apis/visualiz...dtimeline.html

Bref là où je coince c'est que je dois faire une sorte de miniature en bas de la courbe. Mais il faut que je réduise le nombre de points. En effet, il peut y avoir sur toute la courbe plus de 10000 points et il est irréaliste de tous les afficher dans la miniature. Je souhaite avoir une courbe qui représente "en gros" les données avec environ 200 points.

Je pourrais prendre un seul point tous les 50 mais cela me ferai sauter des pics ou autres. Je souhaite réduire le nombre de points et garder à peu près le même aspect.

Est-ce possible ? Comment cela s'appelle ? Connaissaient vous un bon algo ?

Merci de votre aide.

Nuwanda.

PS: Probablement que le titre du post n'est pas idéal mais je n'ai pas mieux

[ToTo13]

Bonjour,

tu pourrais prendre des blocs de 50 points et en faire la moyenne.
Ou sinon par groupe de 50 points prendre le point de plus représentatif au sens de la variance.

[Nuwanda]

Ok merci.

Donc il n'existe pas d'algo "tout prêt" pour faire cela ?

[souviron34]

je dirais 2 solutions :

• Comme l'a suggéré Toto13, une moyenne .
  
• Raisonner en terme graphiques purs, et non en courbe : faire une réduction d'image.

[Nemerle]

Envoyé par souviron34

je dirais 2 solutions :

• Comme l'a suggéré Toto13, une moyenne .
  
• Raisonner en terme graphiques purs, et non en courbe : faire une réduction d'image.

solution 2 ou crise de nerfs subjective

[FR119492]

Salut!
Sous quelle forme ta courbe t'est-elle donnée: par son équation, par 20000 valeurs discrètes ou autrement?
Jean-Marc Blanc

[Graffito]

Bonjour,

On applique un algo du même genre pour réduire le nombre de point de tracés géographiques (frontières, fleuves, côtes).

On définit un écart maxi EMax de distance entre courbe réelle et courbe réduite.
Partant du point Pi, on cherche le point Pk (i<k) dont l'indice k est le plus grand et tel que pour tout j entre i et k (i<j<k), la distance de Pj au segment Pi-Pk est inférieure à EMax. On peut alors éliminer tous les Pj et réitérer l'opération à partir de Pk que l'on garde et ... ainsi de suite.

[Nuwanda]

Hello.

Merci beaucoup de votre aide, donc mes données sont 20000 points de mesures qui provienne d'un capteur. Ca n'est pas un random mais ce n'y a pas non plus de formule derrière.

Merci beaucoup pour l'algorithme géographique c'est effectivement assez proche de ce que je souhaite faire. Je testerai ca quand j'aurai un peu de temps

Merci ^^

Nuwanda

[pseudocode]

L'algorithme géographique, je le connais sous le nom de "Douglas-Peucker".

Le principe/code est dispo sur wikipedia.

[Graffito]

Je ne connaissais pas "Douglas-Peucker".
Et, effectivement, les 2 algo présentent une certaine analogie, mais ne sont pas identiques. Aucun des 2 ne donne d'ailleurs la solution optimale (minimum de points) pour une distance E.