Bonjour, cliquez-ici pour vous inscrire et participer au forum.
  • Login:



+ Répondre à la discussion
Affichage des résultats 1 à 4 sur 4

Quel intérêt d'utiliser un RBTree dans l'algorithme de Fortune ?

  1. acropole

    Date d'inscription
    septembre 2006
    Localisation
    Gers
    Messages
    1 047

    Quel intérêt d'utiliser un RBTree dans l'algorithme de Fortune ?

    Bonjour,

    Raymond Hill utilise un RB Tree pour gérer sa ligne de rivage dans l’algorithme de Fortune : http://www.raymondhill.net/voronoi/rhill-voronoi.html
    Quel est l’intérêt de ce choix ?

    Merci.

    -----

    Sommes nous si différents des extra-martiens ?
     


    • Publicité



  2. polo974

    Date d'inscription
    février 2007
    Messages
    8 261

    Re : Quel intérêt d'utiliser un RBTree dans l'algorithme de Fortune ?

    rb tree = red black tree = arbre bicolore = arbre PRESQUE équilibré (en longueur) https://fr.wikipedia.org/wiki/Arbre_bicolore

    AVL tree = arbre équilibré (en longueur) https://fr.wikipedia.org/wiki/Arbre_AVL

    le premier est un poil plus rapide en insertion que le second, alors que le second est en moyenne plus rapide en recherche...

    et puis parfois le choix se fait en prenant le premier algo remplissant la fonction qu'on trouve...

    (il y a des rbtree dans linux: https://www.kernel.org/doc/Documentation/rbtree.txt )
    Le mieux est l'ennemi du bien, et c'est bien mieux comme ça...
     

  3. acropole

    Date d'inscription
    septembre 2006
    Localisation
    Gers
    Messages
    1 047

    Re : Quel intérêt d'utiliser un RBTree dans l'algorithme de Fortune ?

    Merci.
    Mais ça n'explique toujours pas pourquoi un RBTree, voir même un arbre quelconque.
    La ligne de rivage, comme son nom l'indique, est une ligne, pas un arbre.
    On est obligé de tester x paraboles jusqu'à trouver la bonne.
    Donc pourquoi ne pas simplement utiliser une liste, chaînée ou pas ?
    Sommes nous si différents des extra-martiens ?
     

  4. polo974

    Date d'inscription
    février 2007
    Messages
    8 261

    Re : Quel intérêt d'utiliser un RBTree dans l'algorithme de Fortune ?

    je n'ai pas vraiment fouillé le source, mais lorsqu'il faut insérer un point entre 2 autres, de façon aléatoire, il est plus efficace de ranger les points existants dans un arbre.
    sinon, il faudrait parcourir la liste jusqu'à trouver le point d'insertion (en moyenne la demi longueur de la liste), ce qui devient de plus en plus coûteux alors que dans un arbre ((quasi) équilibré), la progression est seulement en log(n).
    Le mieux est l'ennemi du bien, et c'est bien mieux comme ça...
     


    • Publicité







Sur le même thème :





 

Discussions similaires

  1. algorithme de Fortune pour Diagramme de Voronoï
    Par DeepKdd dans le forum Programmation et langages, Algorithmique
    Réponses: 6
    Dernier message: 17/06/2016, 14h27
  2. Dans quel cas utiliser les Limites
    Par paffthedog dans le forum Mathématiques du collège et du lycée
    Réponses: 3
    Dernier message: 21/04/2013, 13h23
  3. Réponses: 3
    Dernier message: 06/04/2013, 23h37
  4. Besoin de savoir quel test statistique utiliser dans mon exercice
    Par Weegee dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 15/12/2011, 12h34
  5. Quel est l'intérêt de la normalisation de l'erreur dans la régression
    Par saidgrd dans le forum Mathématiques du supérieur
    Réponses: 10
    Dernier message: 20/05/2009, 20h43