Discussion :

[BBouille]

Bonjour les amis,
Je cherche à simplifier une courbe composée de pixels (épaisseur 1 pixel). J'ai plus ou moins compris la théorie des courbes ou segments discrets mais je butte sur le point principal.

Partant d'un premier point, on passe au suivant et on calcule la pente entre les 2. On passe au troisième et on recalcule la pente toujours à partir du premier point et ce sur une certaine longueur de segment.
J'imagine qu'à chaque fois qu'on recalcule la pente il faut vérifier que les points précédents appartiennent toujours à la droite médiane (distance < 1/2 pixel).
Je me trompe sûrement sur le principe et peut-être avez-vous une idée car en fait j'aurais bien voulu éviter cette "marche arrière"?

[tbc92]

Ce que tu cherches à faire n'est pas clair.
Le titre parle de segment maximal, et du coup on se dit que, peut-être, tu cherches à décomposer une courbe en succession de segments, et donc, tu cherches à quels endroits il faut considérer que la pente change. Peut-être ?

[BBouille]

Oui c'est ça, je cherche à former le plus long segment (maximal rectiligne) où chaque pixel ne s'écarte pas de la moitié d'un pixel de la droite qui relie les pixels en cours.

[Mat.M]

Partant d'un premier point, on passe au suivant et on calcule la pente entre les 2. On passe au troisième et on recalcule la pente toujours à partir du premier point et ce sur une certaine longueur de segment.

d'après ce que je comprends vous voulez faire le lissage d'une courbe par interpolations bref le tracé d'une Spline
Chercher dans Google "spline C++" ou "spline Java" il y a des tas de bibliothéques qui existent pour ça

Oui c'est ça, je cherche à former le plus long segment (maximal rectiligne) où chaque pixel ne s'écarte pas de la moitié d'un pixel de la droite qui relie les pixels en cours.

à part procéder par interpolations je ne vois pas.

[BBouille]

Non, justement je ne veux pas passer par les splines, je veux réduire le nombre de pixels utiles de la courbe dans l'image sinon je n'aurais pas posé la question.

[tbc92]

Dans ton premier message, tu parles d'éviter cette marche arrière. Pourquoi ? Si les volumes de données sont raisonnables, les temps de traitement ne devraient pas être un problème. Dans les pistes que je vois, il y a systématiquement des phases de recalcul.

Par ailleurs, dans le plan que tu proposes, tu pars de la gauche vers la droite. Ce n'est pas symétrique.

Imaginons ces points :
Pour x entre 0 et 20 , y vaut 0.1389*x (arrondi à l'entier le plus proche)
Puis pour x entre 20 et 40 , y vaut 0.1389*(40-x) (arrondi à l'entier le plus proche)
J'ai donné 2 fois la formule pour x=20, mais ça donne le même point au final.
Les 2 segments sont parfaitement symétriques

Si tu pars de la gauche, tu vas considérer qu'il y a un segment qui va de (0,0) à (21,3). Puis partant de (21,3), tu vas galérer pour trouver une succession de segments qui collent à la courbe.

En particulier, si tu as un segment qui part de (21,3) à (25,2), comment gères-tu l'arrondi ? Tu considères que le point (23,2) est sur ce segment ? Et (23,3) aussi est sur ce segment ?

Dans mon esprit (mais ce n'est pas totalement clair), il faut regarder les 2 extrémités, et les relier par une droite. Si tous les points sont à moins de 0.5 de cette droite, tout va bien, sinon on retient le point le plus loin de cette droite. On place temporairement un sommet à ce point, et on recommence avec les 2 segments obtenus. Et ainsi de suite. Et au final, on va probablement supprimer certains sommets, s'il s'avère qu'ils sont inutiles. Mais ce n'est certainement pas suffisant.

Sur mon exemple, c'est même pire que ça.
Quand tu vas tester tes points 1 par 1, quand tu vas tester : Les points sont-ils tous très proches de la droite qui va de (0,0) à (20,3), tu vas considérer que non. Tu vas dire que la droite qui va de (0,0) à (20,3), pour x = 17, elle devrait donner y=3. Or dans les données, on a (17,2). Les points de x=0 à 20 ne semblent pas alignés.
Et en effet, ma droite ne va pas tout à fait de (0,0) à (20,3) ; c'est bien l'équation d'une droite que j'ai donnée, mais une droite qui va de (0,0) à (20, 2.778) suivie d'une autre droite qui redescend de (20, 2.778) à (40,0).


Autre question. Tu parles d'une succession de pixels. Est-ce que les pixels sont forcément avec des x de plus en plus grands, de gauche à droite, disons une courbe y=f(x). Ou bien tu as une courbe qui peut être comme une spirale.

[wheel]

Tu peux jeter un coup d'oeil dans la partie polygone

https://potrace.sourceforge.net/potrace.pdf

[BBouille]

TBC: Je veux éviter les boucles dans le traitement graphique, ça augmente très vite le temps de calcul dès qu'on a une image d'une certaine taille.
Avant d'avoir parcouru les pixels tu ne sais pas quelles sont les extrémités, c'est pourquoi je voudrais éviter de recalculer les points précédents.
Je pars du haut vers le bas d'une image et de la gauche vers la droite.
Dès que je rencontre un pixel noir j'applique la méthode.
L'image a déjà été squelettisée donc je n'ai pas à me soucier de l'épaisseur du trait des courbes.
Peu importe si je tombe sur le haut d'une courbe et que je doive parcourir le reste de la courbe dans l'autre sens ensuite, je les fusionne après.
Justement je cherche à réduire au maximum les tronçons rectilignes.
Ensuite pour des segments dont la pente varie "brusquement" j'applique une courbe de Bézier passant par 4, 3 ou 2 points selon les cas.
Wheel: Tu as tapé dans le mille, j'ai lu pas mal d'articles traitant le sujet et notamment Potrace mais aucun n'indique le principal c'est-à-dire comment arriver à cette droite médiane. J'ai lu tout ce qui concerne les paths, etc de Potrace.
Pour le moment je pars de 10 points à la queue-leu-leu par exemple et si le xième point n'est pas sur la droite formée par ces prédécesseurs j'arrête la boucle et je recommence pour les suivants mais ça ne me semble pas très élégant.