Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Simplification d'une courbe de Bézier


Sujet :

Algorithmes et structures de données

  1. #1
    Membre du Club
    Simplification d'une courbe de Bézier
    Bonjour,

    Travaillant sur les courbes de Bézier je voulais demander si quelqu'un avait déjà traité ce sujet s'il y avait un moyen sûr de simplifier une succession (multitude) de points afin d'obtenir la courbe de Bézier la plus fidèle à la courbe apparente des points initiaux.
    Pour le moment j'ai une multitude de points continus formant une courbe quelconque.
    J'ai d'abord appliqué Douglas-Peucker pour éliminer les points sortant d'une certaine limite.
    Mais il en reste encore pas mal et je ne sais pas trop quels points conserver pour appliquer mes équations qui détermineront les paramètres de contrôle de la courbe de Bézier.
    Faut-il conserver uniquement les points d'inflexion? Mais en zoomant les points on peut dire qu'il y en a beaucoup aussi.

    En bref je ne parviens pas à déterminer le seuil de tolérance entre un point qui peut être éliminé ou pas.

    Merci à vous.

    BB

  2. #2
    Membre chevronné
    Bonjour,

    Pourrais-tu donner une image du nuage de points ? Cela permettrait au moins d'avoir une idée de sa dispersion, et de la forme de la courbe apparaissant en pointillé.

    Ton énoncé suggère en effet un grand nombre de points se répartissant au voisinage d'une courbe moyenne, que son allure apparente à une courbe de Bézier.
    ... afin d'obtenir la courbe de Bézier la plus fidèle à la courbe apparente des points initiaux.
    Pour le moment j'ai une multitude de points continus formant une courbe quelconque...
    Cependant la méthode utilisée est-elle appropriée ? Les points sont apparemment beaucoup trop nombreux pour permettre une sélection partielle, et le choix de quelques uns d'entre eux pourrait bien conduire à un résultat décevant.

    Ne faudrait-il pas plutôt envisager un procédé de régression, qui conduirait à la courbe idéale, par une recherche de moindres carrés ?
    Ne pourrait-on pas segmenter raisonnablement le nuage en plusieurs parties, se raccordant selon une direction commune, tangente à la courbe recherchée ?
    Et d'ailleurs, l'ordre des courbes de Bézier envisagées est-il fixé ?
    Voilà une série de considérations qui permettraient peut-être de mieux cerner le problème.

    Je ne suis pas familier de ce sujet (d'où peut-être des remarques maladroites), mais personne n'a apporté de suggestion, jusque là.
    Il y a une issue, mais qui risque d'apparaître très lourde: une double régression cubique sur une partie au moins du nuage, conduisant à deux expressions polynômiales des coordonnées:
    x = a + b*t + c*t2 + d*t3
    y = a' + b'*t + c'*t2 + d'*t3
    à partir desquelles il est possible de remonter aux courbes de Bézier d'ordre 3 .
    La compensation apportée par ce procédé serait de connaître l'étalement moyen (s) des points de part et d'autre de la courbe trouvée, à partir des écarts-types:
    s2 = sx2 + sy2 ,
    et de permettre par ce biais l'élimination des points trop éloignés, sous la condition:
    si >= K*s (dans laquelle intervient une constante arbitraire K ~ 0.5 à 1).


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  3. #3
    Membre chevronné
    Simplification d'une courbe de Bézier
    Une variante plus rapide, trouvée ce matin: le procédé de régression, s'il porte sur deux suites complètes de polynômes de Bernstein - par exemple:

    x = a*(1 - t)3 + 3*b*t*(1 - t)2 + 3*c*t2*(1 - t) + d*t3 ,
    y = a'*(1 - t)3 + 3*b'*t*(1 - t)2 + 3*c'*t2*(1 - t) + d'*t3 ,

    - conduit directement aux coordonnées des points de contrôle, ici les quatre points (P0(a, a') , P1(b, b') ... P3(d, d')) de la courbe du troisième ordre.

    D'autres participants, rompus à l'utilisation des bibliothèques de fonctions , devraient pouvoir t'indiquer où trouver le logiciel effectuant le travail - il existe probablement, car la méthode décrite n'a rien d'original.
    Elle relève du procédé plus général de régression sur quatre fonctions élémentaires (gi(t)) qui ne présentent entre elles aucun rapport constant:
    z = a*g1(t) + b*g2(t) + c*g3(t) + d*g4(t) .
    D'ailleurs ne faudrait-il pas poser la question sur le forum "Statistiques et Data Mining" ?


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  4. #4
    Membre du Club
    Merci Wiwaxia si tu repasses par ici. Pardonne ma longue absence mais je me replonge dans le bain et après avoir essayé ta proposition je viendrai te faire part de la situation.
    Pour le moment je vais calculer la courbe passant par les points par régression linéaire,
    déterminer les points d'inflexion,
    couper la courbe en certains points
    et alors seulement sur les tronçons de courbes obtenus appliquer Bézier avec les tangences communes.
    À plus.

  5. #5
    Membre chevronné
    Simplification d'une courbe de Bézier
    Alors, bon courage !

    En relisant les messages précédents, je reste toujours aussi perplexe: quel est l'aspect du nuage des points ? Le graphe médian (pour autant qu'on puisse le définir) est-il une courbe fermée ? Présente-t-il des points d'inflexion, ou une discontinuité des tangentes en certains points ?
    Autant de question auxquelles l'observation de l'image permettrait de répondre, et à partir de laquelle peut-être le choix d'un procédé deviendrait possible ...


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique