IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
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 :

Algorithme de Bresenham


Sujet :

Algorithmes et structures de données

  1. #1
    Membre habitué
    Profil pro
    Inscrit en
    Avril 2011
    Messages
    428
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2011
    Messages : 428
    Points : 170
    Points
    170
    Par défaut Algorithme de Bresenham
    Bonjour, j'aimerai avoir quelque explication sur cette algorithme ;
    si on prend l'algo naïf soit y=m(x-x1)+y1+0.5.
    Pourquoi on ajoute 0.5, à quoi corresponde les 0.5.
    Merci par avance.

  2. #2
    Expert éminent sénior
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2005
    Messages
    27 369
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2005
    Messages : 27 369
    Points : 41 518
    Points
    41 518
    Par défaut
    C'est marqué: https://fr.wikipedia.org/wiki/Algori...t_de_Bresenham

    C'est pour arrondir à l'entier le plus proche plutôt que l'entier inférieur.
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

  3. #3
    Membre habitué
    Profil pro
    Inscrit en
    Avril 2011
    Messages
    428
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2011
    Messages : 428
    Points : 170
    Points
    170
    Par défaut
    Désolé mais je ne comprend toujours pas.

  4. #4
    Expert éminent sénior
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2005
    Messages
    27 369
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2005
    Messages : 27 369
    Points : 41 518
    Points
    41 518
    Par défaut
    La plupart des opérations impliquant un arrondissement (comme la conversion en entier) arrondissent automatiquement à l'inférieur (ou tronquent, ce qui est la même chose pour les nombres positifs).
    Mais il s'avère que:
    Code X : Sélectionner tout - Visualiser dans une fenêtre à part
    x+0.5 arrondi à l'inférieur == x arrondi au plus proche

    Exemple: 0.75 arrondi à l'inférieur = 0; 0.75 arrondi au plus proche = 1; 0.75+0.5 arrondi à l'inférieur = 1 aussi.
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

  5. #5
    Membre habitué
    Profil pro
    Inscrit en
    Avril 2011
    Messages
    428
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2011
    Messages : 428
    Points : 170
    Points
    170
    Par défaut
    Ha ok merci pour ton aide

    Donc sa veut dire que si j'ai une droite qui passe par le point A(0;0) et B(7;4), en appliquant la formule :
    y=m(x-x1)+y1+0.5 j'obtiens :

    pour x=0 y=0.50 y est donc arrondit au plus proche soit y==0
    pour x=1 y=1.64 y est donc arrondit au plus proche soit y==2
    pour x=2 y=2.21 y est donc arrondit au plus proche soit y==2
    pour x=3 y=2.78 y est donc arrondit au plus proche soit y==3
    pour x=4 y=3.35 y est donc arrondit au plus proche soit y==3

    Donc si je comprend bien quand on compile l'os quand il transformera un float en int arrondira au plus proche.
    Mais si on ne met pas les 0.5 à la compilation l'os arrondira aussi au plus proche non ? c'est à dire :

    au lieu d'avoir y=0.50 on a y=0.00 y à l'arrondit le plus proche vaudra y==0
    au lieu d'avoir y=1.64 on a y=1.04 y à l'arrondit le plus proche vaudra y==1
    au lieu d'avoir y=2.21 on a y=1.71 y à l'arrondit le plus proche vaudra y==2
    au lieu d'avoir y=2.78 on a y=2.28 y à l'arrondit le plus proche vaudra y==2
    au lieu d'avoir y=3.35 on a y=2.85 y à l'arrondit le plus proche vaudra y==3

    Mais alors pourquoi choisir de mettre 0.5 moi sans les 0.5 sa me convient aussi est-ce que le faite de rajouté les 0.5 fait que la droite tracé sera plus jolie à l'écran ?

  6. #6
    Expert éminent sénior
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2005
    Messages
    27 369
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2005
    Messages : 27 369
    Points : 41 518
    Points
    41 518
    Par défaut
    Non, par défaut lors d'une conversion en int il tronque au lieu d'arrondir au plus proche.
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

  7. #7
    Membre habitué
    Profil pro
    Inscrit en
    Avril 2011
    Messages
    428
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2011
    Messages : 428
    Points : 170
    Points
    170
    Par défaut
    Donc comment fait on pour arrondir au plus proche? pour qui si on a float y=1.67 devienne y==2 et non pas y==1 ?

  8. #8
    Membre expert
    Homme Profil pro
    Développeur .NET
    Inscrit en
    Octobre 2013
    Messages
    1 563
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur .NET
    Secteur : Industrie

    Informations forums :
    Inscription : Octobre 2013
    Messages : 1 563
    Points : 3 404
    Points
    3 404
    Par défaut
    Citation Envoyé par hbx360 Voir le message
    Donc comment fait on pour arrondir au plus proche? pour qui si on a float y=1.67 devienne y==2 et non pas y==1 ?
    Si tu appliques +0.5 à ton float (1.67) tu obtiens 2.17. Lorsque la valeur sera arrondie, tu recevras un int = 2 (soit ton arrondi au plus proche de 1.67)

    Le 0.5 sert juste a berner ton compilateur qui voudra tronquer une valeur plutôt que l'arrondir au plus près.

  9. #9
    Membre habitué
    Profil pro
    Inscrit en
    Avril 2011
    Messages
    428
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2011
    Messages : 428
    Points : 170
    Points
    170
    Par défaut
    Merci à toi je comprends mieux.

    Mais alors qu'elle est l'intérêt pour l'algorithme de bresenham de faire cela perso je n'en vois pas.
    Je fais des droites sans les 0.5 et sa marche très bien aussi.

    Pourquoi alors rajouter les 0.5 pour que la droite soit plus jolie ?

  10. #10
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 238
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 238
    Points : 13 443
    Points
    13 443
    Par défaut
    Bonjour
    Citation Envoyé par hbx360 Voir le message
    Pourquoi alors rajouter les 0.5 pour que la droite soit plus jolie ?
    Plus juste surtout. Entre 1.0 et 1.999, il y a presque une différence de 1.
    Alors qu'en déplaçant de 0.5, l'erreur ne sera pas de plus que 0.5.
    L'erreur e est entre 0 et 1 dans le premier cas et entre -0.5 et +0.5 dans le second cas (celui de l'algorithme)
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  11. #11
    Membre habitué
    Profil pro
    Inscrit en
    Avril 2011
    Messages
    428
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2011
    Messages : 428
    Points : 170
    Points
    170
    Par défaut
    Merci Flodelarab pour ta réponse.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Algorithme de Bresenham
    Par ToTo13 dans le forum Codes sources à télécharger
    Réponses: 0
    Dernier message: 19/01/2011, 16h33
  2. algorithme de bresenham pour la détection de droite
    Par soumayacheikh dans le forum Images
    Réponses: 6
    Dernier message: 23/04/2010, 16h21
  3. [2D] Algorithme de Bresenham
    Par Trillian dans le forum Développement 2D, 3D et Jeux
    Réponses: 2
    Dernier message: 09/03/2006, 15h48
  4. L'algorithme de bresenham
    Par ccensam dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 06/11/2005, 23h57

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo