Bonjour
 
Je travaille sur l'implémentation d'un algorithme qui trace les veines d'une feuille.
Voilà le papier : http://algorithmicbotany.org/paper [...] ig2005.pdf
 
La phase la plus lente c'est la recherche des plus proche voisins.  
En gros, il y a deux listes de points : Les veines, et les sources.
Chaque veines cherchent quelles sont les source les plus proches, en suivant cette formule :
 
(∀u ∈ V)||v−s|| < max{||u−s||,|v−u||}.
 
Où u est une veine parmi les autres, s la veine pour laquelle ont cherche ses plus proches voisins, et v les sources testées.
 
L'implémentation "naïve" me donne ça :  
 

 
(_distance renvoi la distance au carrée entre deux points, ça évite d'avoir un calcul de racine carrée.)
 
Le soucis, c'est que le nombre de veines et de sources augmentent très rapidement, du coups les temps sont assez longs.
Dans leur papier, ils parlent des diagrammes de Voronoi pour optimiser ce problème, et de la triangulation de Delaunay pour générer ce diagramme, mais je dois avouer que c'est assez flou pour moi..
 
Si quelqu'un pouvait m'éclairer un peu à ce sujet ça serait cool
 
Merci à vous

Ces 2 algos permettent de limiter les zones sur lesquelles l'algo va travailler.
Dans Wikipedia, y'a de bons articles sur ces 2 sujets

Oui j'ai compris le principe, mais je vois pas trop comment le mettre en pratique..
Je sais qu'il faut un diagramme de Voronoi pour les veines, et un pour les sources, mais je vois pas comment se passe la recherche une fois ceci mis en place.

Y'a un truc pas très clair pour moi (et j'ai pas trop le temps de lire le papier ) : tu dis que pour chaque veine "s", tu cherches la source "v" la plus proche (au passage, pas très logique d'appeler "s" la veine et "v" la source ). Du coup, que vient faire "u" qui est une autre veine là-dedans ?
 
Je précise que si je connais le principe de Voronoï, je l'ai jamais utilisé. Par contre, la notion de plus proche voisin me fais penser à dijkstra et le plus court chemin, voire, peut-être plus adapté, les plus courts chemins d'un graphe via l'algo de Bellman-Ford :  
http://fr.wikipedia.org/wiki/Algor [...] llman-Ford
Ca pourrait pas t'aider ?

Bonjour,
 
Je ne sais pas si mon post va être utile mais on peut aussi utiliser une structure de données particulières les kd-tree pour les recherches de plus proche voisin.

Bon effectivement en fait j'avais compris l'algo de travers

Dans mon implémentation, chaque veine cherche les sources les plus proche, c-a-d qu'il n'existe aucune autre veine plus proche des sources.
Les résultats étaient pas mauvais, mais en relisant ça se fait dans l'autre sens.

Chaque sources cherchent la veine la plus proche (unique veine), et influence celle-ci (open pattern, si je ne me trompe pas c'est plus pour simuler les branches / racines d'un arbre que des veines de feuilles).
Ensuite, pour le closed pattern, une source S peut influencer plusieurs veines, auquel cas ça donne que la source S et ses plus proches voisins influencent la veine la plus proche de S.
Pour les plus proche voisins, l'algo dit ça :

"La source V est un plus proche voisin de la source S si pour toutes veines U plus proche de S que ne l'est V, V est plus proche de S que de U." ( )

Bon, pour l'instant je vais rester sur ma première implémentation, c'est déjà assez le bordel comme ça

J'ai commencé à réfléchir pour l'implémentation de l'opti avec un quad-tree, ça ressemble du coups aux KD-Tree ( sauf qu'eux se basent sur la médiane si j'ai bien compris).
Mon approche donnerait ça :

A chaque fois qu'une veine doit vérifier si une source est belle et bien son plus proche voisin, elle retrouvera sa position dans le quad-tree et commencera par vérifier toute les autres veines du noeud correspondant. Si aucune de ces veines ne sont plus proche, alors ça ira sur le noeud parent du noeud de la source.
Du coups, pour chaque veine ça donnerai dans le pire des cas (aucune veine n'est plus proche de cette source que ne l'est la veine actuelle) une complexité en O(n) où n est le nombre de source, et dans le meilleur... Bah là de tête je saurais pas dire, mais bien mieux

Pour ce qui est de Djikstra et Bellman-Fort, les graphs ont un nombres d'arcs donnés, moi dans mon cas chaque point serait reliés les un aux autres, du coups ça va pas faire un truc assez lent

Je sais pas si ça peut fonctionner Bellman-Ford, ça dépend un peu du contexte. l'idée, c'était de pouvoir pré-calculer la matrice des distances entre toutes les veines et sources. Si à une feuille tu peux associer la matrice déjà calculée, après, pour ton algo, il reste plus qu'à faire des recherches dans la matrice. Dans ce cas, là, je pense que tu peux gagner du temps... Par contre, si tes feuilles sont générées dynamiquement, à chaque fois, faudra calculer le matrice puis l'exploiter : dans ce cas, c'est pas dit que tu gagnes du temps...

Oui effectivement, les points sont rajoutés au fur et à mesure donc ça ne me semble pas être l'idéal...

J'ai retapé le déroulement de l'algo, ma première implémentation était vraiment dégueu en fait
Rien que le fait de faire que chaque source trouve sa veine la plus proche (au lieu que chaque veine trouve ses sources les plus proche) ça a ajouté un sacré boost de temps.
J'ai essayé ensuite de créer un quad-tree qui continent chaque noeud de chaque veine pour booster la recherche du plus proche voisin (basé sur cet exemple : http://bl.ocks.org/patricksurry/6478178), et ça ralenti l'algo énormément au final..

J'vais tenter avec l'implémentation de Voronoi de la librairie Boost, mais je sais pas trop ce que ça va donner (l'insertion dans un quad-tree est extrêmement rapide, je sais pas si c'est le cas pour Voronoi), après au pire je peux toujours "optimiser" la version naïve du plus proche voisin en faisant du multi-threading ( grouper les sources par threads, ça devrait être un gros speed-up non ?)

Faut aussi que je jette un coups d'oeil aux kd-trees, sur le quad-tree l'arbre était quasiment toujours parcouru...

edit : En fait mon implé pour les quad-trees était mal foutu, j'avais pas adapté pour bosser avec les distances au carrée. Le quad-tree est en moyenne 2x plus rapide que la version naïve sur mon algo