DIAGRAMME DE VORONOI
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
28 févr. 2007 à 13:03
alfaquireilaallah Messages postés 5 Date d'inscription dimanche 12 avril 2009 Statut Membre Dernière intervention 26 juillet 2009 - 26 juil. 2009 à 19:54
alfaquireilaallah Messages postés 5 Date d'inscription dimanche 12 avril 2009 Statut Membre Dernière intervention 26 juillet 2009 - 26 juil. 2009 à 19:54
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/41658-diagramme-de-voronoi
https://codes-sources.commentcamarche.net/source/41658-diagramme-de-voronoi
26 juil. 2009 à 19:54
j'ai un pb concernant comment on peut intégrer ces classes et fonctions
dans une application donnée en c++builder.
pouvez-vous m'aider?
11 avril 2008 à 09:40
Voronoi est une methode de segmentation, c'est a dire qu'il segmente l'image initiale et chaque nouvelle region obtenue aura une unique valeur.
Ex:
La region 1 aura le label 0
La region 2 1 etc...
Apres c'est a toi de faire comme tu veux. Moi j'ai choisi de mettre des couleurs aleatoires pour chaque region mais c'est un choix personnel.
donc le label 0 aura comme valeur R=rand()%255, G=rand()%255, B=rand()%255
A+
10 avril 2008 à 21:45
ma question sur cette methode esk ca marche avec des image en couleur ou non cad esk c 1 des methodes de segmentation des images couleurs car j'ai appliqué sur une photos un proramme sur DV mais resultat était en noir et blans mais je vois ici que le resulta est en couleur??
esk kelk1 peut m'expliqué...merciii
10 sept. 2007 à 08:20
Merci de ton message, il met les choses en place au niveau de la complexité. En effet je savais bien qu'il devait y avoir une différence entre ma facon de faire et celle des chercheurs...
Merci d'avoir pris le temps de poster ce message.
Tu as travaillé sur les diagramme de Voronoi ? Parce que je serais intéressé de trouver le code de la construction du réseau comme le font les chercheurs.
A+
6 sept. 2007 à 16:11
Si j'ai bien compris ton algo, ça consiste en gros à parcourir tous les points de l'image et à choisir pour chacun d'entre eux la ville la plus proche. À ce moment là, l'algorithme est en effet linéaire suivant le nombre de villes, il est aussi linéaire suivant le nombre de pixels dans ton image.
Le meilleur connu actuellement est en n*log(n) suivant le nombre de villes, et s'applique dans un cadre plus général: il renvoie les équations des segments qui séparent chaque région et définit de manière exacte chaque région d'influence tandis qu'ici, tu ne t'attaches qu'aux points à coordonnées entières. De plus il est en O(n) en espace mémoire utilisé tandis que le tien est en O(la surface de l'image = la surface du plan entre les villes aux extrémités, ce qui est dépendant de leurs coordonnées).
Voilà qui conclura peut-être le débat sur la complexité
Sinon, très jolies les mosaïques et sympa le choix de la distance.
On pourrait se servir de ce principe pour mettre un effet de mosaïque sur une image
10 avril 2007 à 14:44
J'aimerai aussi comprendre car mon algo est très simple...
Tous mes tests ont été fait en mesurant le temps c'est peut etre à cause de cela.
8 avril 2007 à 20:16
7 mars 2007 à 18:20
merci.
1 mars 2007 à 07:58
Tu as tout à fait raison pour n< nlog n, je me suis emballé.
J'ai dit cela car j'ai vu des algorithmes tourner qui était bien plus rapide que le mien...
Je vais essayer de laisser tourner mon pc plus longtemps pour tester des n>800, mais c'est vrai qu'à priori, c'est bien un algo linéaire!
28 févr. 2007 à 20:45
Et ton analyse statistique est convainquante pour n < 800 en tout cas, je peux difficilement contredire. C'est juste très étonnant.
Sinon, n < n log n pour tout n > 1, donc oui, de manière tout à fait certaine, n est mieux que n log n. Aucun doute là dessus.
28 févr. 2007 à 20:05
J'avoue que je suis assez surpris du résultat du diagramme pour la distance de manhattan. Cela donne vraiment un diagramme assez inabituelle.
Je vous invite à allez le voir, il est très sympas.
Ah oui au fait Kirua, tu peux réafficher les villes une fois que tu as tracé les polygones. (Appuye sur POINTS)
28 févr. 2007 à 19:50
Je t'assure que mon algo est linéaire. Je vais bientôt mettre un doc de stat sur les performances en temps de mon algorithme.
L'équation de la droite est : y = 90 x+200 le tout en ms.
Je ne comprends pas pourquoi tu dis qu'un algo en nlog(n) est moins performant qu'un algo linéaire. La différence en temps ce fait surtout lorsque n devient très grand à l'avantage de l'algo en nlog(n)?
Sinon mon programme utilise la distance euclidienne mais je vais voir ce qui ce passe avec les autres distances...
Merci de ton commentaire en tout cas.
28 févr. 2007 à 13:03
Du reste, le résultat est assez joli, mais ça aurait été chouette que tu dessines les villes par dessus les polygones :).
Tu as utilisé quoi comme définition de distance? Euclidienne ou manhattan? (ie: sqrt(a² + b²) ou abs(a) + abs(b) ?). En fait, je ne suis pas familier avec le diagramme de voronoi, mais j'en comprends bien la définition, et je suis étonné de voir des polygones plutôt que des formes courbes quelconques, ce qui s'expliquerait assez simplement si tu as utilisé la distance de manhattan.
Sinon, le rendu est splendide!