DIAGRAMME DE VORONOI

Commentaire de Kirua le 28/02/2007 13:03:15

Euhm, je doute fortement que ton algorithme soit linéaire ( O(n) )comme tu dis. Et si c'était le cas, ce serait vraiment dommage de vouloir le transformer en un O(n lg n)... La triangulation de delaunay, qui est le problème "dual" de celui-ci, donc de complexité intrinsèque équivalente, peut être construit en au mieux O(n lg n). D'où mes doutes.

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!

Commentaire de Pistol_Pete le 28/02/2007 20:05:16

Voila voila j'ai ajouté la possibilité de choisir la distance que l'on souhaite: euclidienne ou manhattan.

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)

Commentaire de Pistol_Pete le 01/03/2007 07:58:41

Salut

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!

Commentaire de f le 08/04/2007 20:16:17

Le meilleur algo existant est en n*log(n), meme pour les plus grands chercheurs..

Commentaire de Muff le 06/09/2007 16:11:07

Salut,
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

Commentaire de nilda2007 le 10/04/2008 21:45:34

salut!
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