Wiki du LAMA (UMR 5127) - Contributions [fr]

Transformées en distance, diagramme de Voronoi et applications en geometry processing

2018-05-21T20:45:19Z

Wagner : /* Distance entre un point et un ensemble */

Le diagramme de Voronoï et les transformées en distance sont deux outils mathématiques permettant de changer un ensemble de points en une surface triangulée. L'avantage de ces outils est d'arriver à limiter les erreurs existante sur la surface créée et arriver à trouver des théorèmes mathématiques intéressantes concernant les surfaces.
== Les distances ==
En mathématique, on appelle une distance, une longueur qui sépare une chose d'une autre.
Néanmoins, la notion de chose est très vague car il peut exister sous plusieurs formes comme:
=== Distance entre deux points ===
On appelle la distance entre deux points « a » et « b » la mesure du segment joignant ces deux points, Cette distance se calcule : d(a,b)= <math>\sqrt{(a^2)+(b^2)}</math>
[[Fichier:Distance_entre_deux_points.jpg]]

=== Distance entre un point et un ensemble ===
On appelle la distance entre un point « a » et un ensemble « B » la mesure du segment entre « a » et un point appartenant à « B » tel que cette mesure soit minimale. En d'autre terme, d(a,B)=(min(d(a,b)) avec b appartenant à B. C'est cette distance qui va nous intéresser pour la suite de notre sujet.

[[Fichier:Distance_entre_un point_et_un_ensemble.jpg]]

=== Distance entre deux ensembles ===
On appelle la distance entre un ensemble A et un ensemble « B » la mesure du segment entre
un point appartenant à « A» et un point appartenant à « B » tel que cette mesure soit minimale. En d'autre terme, d(A,B)=(min(d(a,b)) avec a appartenant à A et b appartenant à B.
[[Fichier:Distance_de_Hausdorff.jpg|1000px|thumb|left|Ici on a A qui représente la carré rouge et B qui représente le cercle bleu (la partie violette représente la partie confondue entre ces deux ensembles). En cherchant un point a appartenant à A et possédant la distance maximale entre ce point et l'ensemble B, on tombe sur un des sommets du carré. On cherche également un point b appartenant à B tel que sa distance soit maximale avec l'ensemble A. On observe lequel des deux a une plus grande distance et on remarque que la distance de Hausdorff est la distance entre le point a et l'ensemble B, soit la plus grande distance qu'il peut exister entre ces deux ensembles.
]]
=== Distance de Hausdorff ===
En considérant A et B deux ensembles et a et b des points appartenant respectivement aux ensembles A et B. Soit a le point le plus éloigné de l'ensemble B qui admettra une distance r1 et b le point le plus éloigné de l'ensemble A qui admettra une distance r2
La distance de Hausdorff est la mesure maximale qui peut exister entre r1 et r2
exemple :

== Stabilité d'une fonction, Diagramme de Voronoï et Triangulation de Delaunay ==
=== Stabilité d'une fonction ===
Ce procédé admet ainsi plusieurs avantages afin de créer une surface stable. En effet, en remarquant que chaque germe a une distance minimale par rapport au diagramme de Voronoi. Si ce germe admet une erreur de position, le diagramme ne va pas modifier beaucoup et ainsi rendre la surface stable.
=== Diagramme de Voronoï ===
Soit un ensemble de points P appartenant à un plan R. Pour tout point P(n), on peut lui attribuer une zone d'influence Z(n) tel qu'à chaque point « p » appartenant à Z(n), « p » aura une transformée en distance minimale de P(n) par rapport aux autre points appartenant à R.
La délimitation de chacune de ces zones d'influence forme un réseau appelé le diagramme de Voronoi. Les points P sont quand à eux nommés les germes.
Autrement dit, si on formait des cercles de même rayon ayant comme centre chaque point du plan et qu'on les agrandissait au fur et à mesure, chacune des droites d'intersection de deux cercles formerait le diagramme de Voronoi.
=== Triangulation de Delaunay ===
La triangulation de Delaunay est la connexion en triangles des germes qui composent le diagramme de Voronoi. Il compose ainsi le dual du diagramme de Voronoi
Une règle de cette triangulation est que le cercle circonscrit à un de ces triangles ne contient aucun autre point de Voronoi.
== Propriétés ==
=== Autour du Diagramme de Voronoï ===
1) Une arête de Voronoi sépare deux régions de Voronoï (zone d'influence des germes) en étant caractérisée comme la médiatrice du segment portant comme sommets les deux germes qui entoure cette arête.

2) Un sommet de Voronoï séparant trois cellules est le centre du cercle circonscrit au triangle portant comme sommets les germes du diagramme de Voronoï

=== Autour de la triangulation de Delaunay ===
1)L'écart angulaire des triangles compris dans le triangulation de Delaunay doit être maximale.
La triangulation de Delaunay d’un ensemble de points est donc celle qui évite le mieux la création de triangles aplatis : les triangles ont la forme qui ressemble le plus à un triangle équilatéral.

2)Les cercles circonscrits pour chaque triangle contenu dans la triangulation de Delaunay ne doivent contenir aucun autres germes.

== Lien avec l'axe médian et le squelette ==
=== Lien avec l'axe médian ===
L'axe médian est l'ensemble des points qui admet au moins deux plus proches voisins dans un ensemble A
On peut ainsi en déduire que dans un polygone, on peut construire son axe médian grâce à ses médiatrices et ainsi utiliser le diagramme de Voronoï pour permettre cette construction.
=== Lien avec le squelette ===
== Algorithme permettant de générer un Diagramme de Voronoï ==
Il est assez compliqué de programmer un diagramme de Voronoi entièrement avec un code propre et efficace, une solution aurait été de d'abord générer des points aléatoirement sur l'image, calculer les distances entres chaque point puis tracer les médiatrices des segments pour laquelle la distance entre chaque points serait minimale. Néanmoins, il aurait alors fallut supprimer les extrémités des médiatrices pour laquelle la distance minimale entre deux germes devenait trop grande, ce qui rend le programme plus compliqué à résoudre.

Une autre solution aurait été de générer des droites entre les points en faisant en sorte que chaque point soient à nombre égale dans chaqu'une de leurs parties et que les points les plus proches de la courbes soient à égales distances entre la droite et leur position, jusqu'à qu'il y reste qu'un point dans chaque unique partie du diagramme (Une sorte de dichotomie). On a ainsi plusieurs problèmes qui persistent. En plus du fait qu'il faudrait effacer des parties de médiatrices, si on se retrouve un nombre de points impair, il sera difficile de générer une droite séparant la moitié des points.

Le programme le moins compliqué est bien sûr le plus long à faire exécuter, sans parler qu'il utilise des répétitions. Il ne serait pas de générer le diagramme de Voronoi mais ses régions en différentes couleurs. Ainsi, le diagramme sera alors représenté par l'intersection des différentes couleurs. Voici le programme permettant de générer ces région:

<pre>
def distance2( p, q ):
return (p[0]-q[0])**2 + (p[1]-q[1])**2

def region_voronoi(n):
fenetre = Tk()
canvas=Canvas(fenetre, width=largeur, height=hauteur, background='white')
img = PhotoImage(width=largeur, height=hauteur)
couleurs=[]
points=[]
for i in range(n):
x =int(random.random()*(largeur-1))
y =int(random.random()*(hauteur-1))
points.append([x,y])
couleurs.append([int(random.random()*255),int(random.random()*255),int(random.random()*255)])
for i in range(hauteur-1):
for j in range(largeur-1):
min_k = 0
for k in range(1,n):
if distance2( (i,j), points[k] ) < distance2( (i,j), points[min_k] ):
min_k = k
r = couleurs[min_k][0]
g = couleurs[min_k][1]
b = couleurs[min_k][2]
img.put( "#%02x%02x%02x" % (r,g,b), (i,j) )
canvas.create_image((largeur/2,hauteur/2), image=img, state="normal")
canvas.pack()
fenetre.mainloop()
</pre>

Ainsi dans ce programme, il faut créer une fenêtre, un canvas qui sera compris dans la fenêtre et une image pour lui apporter des modification. Ce programme sera aussi constitué de deux doubles tableaux (couleurs et points) où l'on placera des couleurs en version RGB de couleurs différentes et des points de coordonnées aléatoires et de la fonction distance qui nous aidera à calculer lisiblement des distances (au carré ou non, il n'y a aucune différence car on doit chercher sa distance minimale). "n" sera le nombre de germes qu'on voudra attribuer au diagramme de Voronoi(et ainsi le nombre de régions puisque les germes ne seront pas représentés). On commence ainsi d'abord à ajouter au tableaux points des coordonnées aléatoires selon "n" représentant leur germes. Puis on associe un même nombre de couleurs aléatoires selon "n" (chaque germe aura sa couleur) au tableau couleurs. Ensuite on parcours deux boucles for représentant l'image (j va parcourir l'abscisse et i va parcourir l'ordonnée de l'image) pour passer de pixel en pixel. Pour chaque pixel, on calcul leur distance avec chaque germe de Voronoi et on doit trouver sa plus petite distance. Lorsque on l'a trouvé (ce qui voudra dire que le pixel appartient à la région de Voronoi durant laquelle son germe est influent) on lui transmet la couleur du germe et ainsi de suite jusqu'à la fin du programme. Enfin, on crée l'image puis on démarre la boucle Tkinter qui s'interrompt quand on ferme la fenêtre.

Transformées en distance, diagramme de Voronoi et applications en geometry processing

2018-05-21T15:17:33Z

Wagner : /* Algorithme permettant de générer un Diagramme de Voronoï */

Le diagramme de Voronoï et les transformées en distance sont deux outils mathématiques permettant de changer un ensemble de points en une surface triangulée. L'avantage de ces outils est d'arriver à limiter les erreurs existante sur la surface créée et arriver à trouver des théorèmes mathématiques intéressantes concernant les surfaces.
== Les distances ==
En mathématique, on appelle une distance, une longueur qui sépare une chose d'une autre.
Néanmoins, la notion de chose est très vague car il peut exister sous plusieurs formes comme:
=== Distance entre deux points ===
On appelle la distance entre deux points « a » et « b » la mesure du segment joignant ces deux points, Cette distance se calcule : d(a,b)= <math>\sqrt{(a^2)+(b^2)}</math>
[[Fichier:Distance_entre_deux_points.jpg]]

=== Distance entre un point et un ensemble ===
On appelle la distance entre un point « a » et un ehttps://www.lama.univ-savoie.fr/mediawiki/index.php/VISI201_CMI_:_visite_de_laboratoirensemble « B » la mesure du segment entre « a » et un point appartenant à « B » tel que cette mesure soit minimale. En d'autre terme, d(a,B)=(min(d(a,b)) avec b appartenant à B. C'est cette distance qui va nous intéresser pour la suite de notre sujet.

[[Fichier:Distance_entre_un point_et_un_ensemble.jpg]]

=== Distance entre deux ensembles ===
On appelle la distance entre un ensemble A et un ensemble « B » la mesure du segment entre
un point appartenant à « A» et un point appartenant à « B » tel que cette mesure soit minimale. En d'autre terme, d(A,B)=(min(d(a,b)) avec a appartenant à A et b appartenant à B.
[[Fichier:Distance_de_Hausdorff.jpg|1000px|thumb|left|Ici on a A qui représente la carré rouge et B qui représente le cercle bleu (la partie violette représente la partie confondue entre ces deux ensembles). En cherchant un point a appartenant à A et possédant la distance maximale entre ce point et l'ensemble B, on tombe sur un des sommets du carré. On cherche également un point b appartenant à B tel que sa distance soit maximale avec l'ensemble A. On observe lequel des deux a une plus grande distance et on remarque que la distance de Hausdorff est la distance entre le point a et l'ensemble B, soit la plus grande distance qu'il peut exister entre ces deux ensembles.
]]
=== Distance de Hausdorff ===
En considérant A et B deux ensembles et a et b des points appartenant respectivement aux ensembles A et B. Soit a le point le plus éloigné de l'ensemble B qui admettra une distance r1 et b le point le plus éloigné de l'ensemble A qui admettra une distance r2
La distance de Hausdorff est la mesure maximale qui peut exister entre r1 et r2
exemple :

== Stabilité d'une fonction, Diagramme de Voronoï et Triangulation de Delaunay ==
=== Stabilité d'une fonction ===
Ce procédé admet ainsi plusieurs avantages afin de créer une surface stable. En effet, en remarquant que chaque germe a une distance minimale par rapport au diagramme de Voronoi. Si ce germe admet une erreur de position, le diagramme ne va pas modifier beaucoup et ainsi rendre la surface stable.
=== Diagramme de Voronoï ===
Soit un ensemble de points P appartenant à un plan R. Pour tout point P(n), on peut lui attribuer une zone d'influence Z(n) tel qu'à chaque point « p » appartenant à Z(n), « p » aura une transformée en distance minimale de P(n) par rapport aux autre points appartenant à R.
La délimitation de chacune de ces zones d'influence forme un réseau appelé le diagramme de Voronoi. Les points P sont quand à eux nommés les germes.
Autrement dit, si on formait des cercles de même rayon ayant comme centre chaque point du plan et qu'on les agrandissait au fur et à mesure, chacune des droites d'intersection de deux cercles formerait le diagramme de Voronoi.
=== Triangulation de Delaunay ===
La triangulation de Delaunay est la connexion en triangles des germes qui composent le diagramme de Voronoi. Il compose ainsi le dual du diagramme de Voronoi
Une règle de cette triangulation est que le cercle circonscrit à un de ces triangles ne contient aucun autre point de Voronoi.
== Propriétés ==
=== Autour du Diagramme de Voronoï ===
1) Une arête de Voronoi sépare deux régions de Voronoï (zone d'influence des germes) en étant caractérisée comme la médiatrice du segment portant comme sommets les deux germes qui entoure cette arête.

2) Un sommet de Voronoï séparant trois cellules est le centre du cercle circonscrit au triangle portant comme sommets les germes du diagramme de Voronoï

=== Autour de la triangulation de Delaunay ===
1)L'écart angulaire des triangles compris dans le triangulation de Delaunay doit être maximale.
La triangulation de Delaunay d’un ensemble de points est donc celle qui évite le mieux la création de triangles aplatis : les triangles ont la forme qui ressemble le plus à un triangle équilatéral.

2)Les cercles circonscrits pour chaque triangle contenu dans la triangulation de Delaunay ne doivent contenir aucun autres germes.

== Lien avec l'axe médian et le squelette ==
=== Lien avec l'axe médian ===
L'axe médian est l'ensemble des points qui admet au moins deux plus proches voisins dans un ensemble A
On peut ainsi en déduire que dans un polygone, on peut construire son axe médian grâce à ses médiatrices et ainsi utiliser le diagramme de Voronoï pour permettre cette construction.
=== Lien avec le squelette ===
== Algorithme permettant de générer un Diagramme de Voronoï ==
Il est assez compliqué de programmer un diagramme de Voronoi entièrement avec un code propre et efficace, une solution aurait été de d'abord générer des points aléatoirement sur l'image, calculer les distances entres chaque point puis tracer les médiatrices des segments pour laquelle la distance entre chaque points serait minimale. Néanmoins, il aurait alors fallut supprimer les extrémités des médiatrices pour laquelle la distance minimale entre deux germes devenait trop grande, ce qui rend le programme plus compliqué à résoudre.

Une autre solution aurait été de générer des droites entre les points en faisant en sorte que chaque point soient à nombre égale dans chaqu'une de leurs parties et que les points les plus proches de la courbes soient à égales distances entre la droite et leur position, jusqu'à qu'il y reste qu'un point dans chaque unique partie du diagramme (Une sorte de dichotomie). On a ainsi plusieurs problèmes qui persistent. En plus du fait qu'il faudrait effacer des parties de médiatrices, si on se retrouve un nombre de points impair, il sera difficile de générer une droite séparant la moitié des points.

Le programme le moins compliqué est bien sûr le plus long à faire exécuter, sans parler qu'il utilise des répétitions. Il ne serait pas de générer le diagramme de Voronoi mais ses régions en différentes couleurs. Ainsi, le diagramme sera alors représenté par l'intersection des différentes couleurs. Voici le programme permettant de générer ces région:

<pre>
def distance2( p, q ):
return (p[0]-q[0])**2 + (p[1]-q[1])**2

def region_voronoi(n):
fenetre = Tk()
canvas=Canvas(fenetre, width=largeur, height=hauteur, background='white')
img = PhotoImage(width=largeur, height=hauteur)
couleurs=[]
points=[]
for i in range(n):
x =int(random.random()*(largeur-1))
y =int(random.random()*(hauteur-1))
points.append([x,y])
couleurs.append([int(random.random()*255),int(random.random()*255),int(random.random()*255)])
for i in range(hauteur-1):
for j in range(largeur-1):
min_k = 0
for k in range(1,n):
if distance2( (i,j), points[k] ) < distance2( (i,j), points[min_k] ):
min_k = k
r = couleurs[min_k][0]
g = couleurs[min_k][1]
b = couleurs[min_k][2]
img.put( "#%02x%02x%02x" % (r,g,b), (i,j) )
canvas.create_image((largeur/2,hauteur/2), image=img, state="normal")
canvas.pack()
fenetre.mainloop()
</pre>

Ainsi dans ce programme, il faut créer une fenêtre, un canvas qui sera compris dans la fenêtre et une image pour lui apporter des modification. Ce programme sera aussi constitué de deux doubles tableaux (couleurs et points) où l'on placera des couleurs en version RGB de couleurs différentes et des points de coordonnées aléatoires et de la fonction distance qui nous aidera à calculer lisiblement des distances (au carré ou non, il n'y a aucune différence car on doit chercher sa distance minimale). "n" sera le nombre de germes qu'on voudra attribuer au diagramme de Voronoi(et ainsi le nombre de régions puisque les germes ne seront pas représentés). On commence ainsi d'abord à ajouter au tableaux points des coordonnées aléatoires selon "n" représentant leur germes. Puis on associe un même nombre de couleurs aléatoires selon "n" (chaque germe aura sa couleur) au tableau couleurs. Ensuite on parcours deux boucles for représentant l'image (j va parcourir l'abscisse et i va parcourir l'ordonnée de l'image) pour passer de pixel en pixel. Pour chaque pixel, on calcul leur distance avec chaque germe de Voronoi et on doit trouver sa plus petite distance. Lorsque on l'a trouvé (ce qui voudra dire que le pixel appartient à la région de Voronoi durant laquelle son germe est influent) on lui transmet la couleur du germe et ainsi de suite jusqu'à la fin du programme. Enfin, on crée l'image puis on démarre la boucle Tkinter qui s'interrompt quand on ferme la fenêtre.

Transformées en distance, diagramme de Voronoi et applications en geometry processing

2018-05-21T14:58:32Z

Wagner : /* Algorithme permettant de générer un Diagramme de Voronoï */

Le diagramme de Voronoï et les transformées en distance sont deux outils mathématiques permettant de changer un ensemble de points en une surface triangulée. L'avantage de ces outils est d'arriver à limiter les erreurs existante sur la surface créée et arriver à trouver des théorèmes mathématiques intéressantes concernant les surfaces.
== Les distances ==
En mathématique, on appelle une distance, une longueur qui sépare une chose d'une autre.
Néanmoins, la notion de chose est très vague car il peut exister sous plusieurs formes comme:
=== Distance entre deux points ===
On appelle la distance entre deux points « a » et « b » la mesure du segment joignant ces deux points, Cette distance se calcule : d(a,b)= <math>\sqrt{(a^2)+(b^2)}</math>
[[Fichier:Distance_entre_deux_points.jpg]]

=== Distance entre un point et un ensemble ===
On appelle la distance entre un point « a » et un ehttps://www.lama.univ-savoie.fr/mediawiki/index.php/VISI201_CMI_:_visite_de_laboratoirensemble « B » la mesure du segment entre « a » et un point appartenant à « B » tel que cette mesure soit minimale. En d'autre terme, d(a,B)=(min(d(a,b)) avec b appartenant à B. C'est cette distance qui va nous intéresser pour la suite de notre sujet.

[[Fichier:Distance_entre_un point_et_un_ensemble.jpg]]

=== Distance entre deux ensembles ===
On appelle la distance entre un ensemble A et un ensemble « B » la mesure du segment entre
un point appartenant à « A» et un point appartenant à « B » tel que cette mesure soit minimale. En d'autre terme, d(A,B)=(min(d(a,b)) avec a appartenant à A et b appartenant à B.
[[Fichier:Distance_de_Hausdorff.jpg|1000px|thumb|left|Ici on a A qui représente la carré rouge et B qui représente le cercle bleu (la partie violette représente la partie confondue entre ces deux ensembles). En cherchant un point a appartenant à A et possédant la distance maximale entre ce point et l'ensemble B, on tombe sur un des sommets du carré. On cherche également un point b appartenant à B tel que sa distance soit maximale avec l'ensemble A. On observe lequel des deux a une plus grande distance et on remarque que la distance de Hausdorff est la distance entre le point a et l'ensemble B, soit la plus grande distance qu'il peut exister entre ces deux ensembles.
]]
=== Distance de Hausdorff ===
En considérant A et B deux ensembles et a et b des points appartenant respectivement aux ensembles A et B. Soit a le point le plus éloigné de l'ensemble B qui admettra une distance r1 et b le point le plus éloigné de l'ensemble A qui admettra une distance r2
La distance de Hausdorff est la mesure maximale qui peut exister entre r1 et r2
exemple :

== Stabilité d'une fonction, Diagramme de Voronoï et Triangulation de Delaunay ==
=== Stabilité d'une fonction ===
Ce procédé admet ainsi plusieurs avantages afin de créer une surface stable. En effet, en remarquant que chaque germe a une distance minimale par rapport au diagramme de Voronoi. Si ce germe admet une erreur de position, le diagramme ne va pas modifier beaucoup et ainsi rendre la surface stable.
=== Diagramme de Voronoï ===
Soit un ensemble de points P appartenant à un plan R. Pour tout point P(n), on peut lui attribuer une zone d'influence Z(n) tel qu'à chaque point « p » appartenant à Z(n), « p » aura une transformée en distance minimale de P(n) par rapport aux autre points appartenant à R.
La délimitation de chacune de ces zones d'influence forme un réseau appelé le diagramme de Voronoi. Les points P sont quand à eux nommés les germes.
Autrement dit, si on formait des cercles de même rayon ayant comme centre chaque point du plan et qu'on les agrandissait au fur et à mesure, chacune des droites d'intersection de deux cercles formerait le diagramme de Voronoi.
=== Triangulation de Delaunay ===
La triangulation de Delaunay est la connexion en triangles des germes qui composent le diagramme de Voronoi. Il compose ainsi le dual du diagramme de Voronoi
Une règle de cette triangulation est que le cercle circonscrit à un de ces triangles ne contient aucun autre point de Voronoi.
== Propriétés ==
=== Autour du Diagramme de Voronoï ===
1) Une arête de Voronoi sépare deux régions de Voronoï (zone d'influence des germes) en étant caractérisée comme la médiatrice du segment portant comme sommets les deux germes qui entoure cette arête.

2) Un sommet de Voronoï séparant trois cellules est le centre du cercle circonscrit au triangle portant comme sommets les germes du diagramme de Voronoï

=== Autour de la triangulation de Delaunay ===
1)L'écart angulaire des triangles compris dans le triangulation de Delaunay doit être maximale.
La triangulation de Delaunay d’un ensemble de points est donc celle qui évite le mieux la création de triangles aplatis : les triangles ont la forme qui ressemble le plus à un triangle équilatéral.

2)Les cercles circonscrits pour chaque triangle contenu dans la triangulation de Delaunay ne doivent contenir aucun autres germes.

== Lien avec l'axe médian et le squelette ==
=== Lien avec l'axe médian ===
L'axe médian est l'ensemble des points qui admet au moins deux plus proches voisins dans un ensemble A
On peut ainsi en déduire que dans un polygone, on peut construire son axe médian grâce à ses médiatrices et ainsi utiliser le diagramme de Voronoï pour permettre cette construction.
=== Lien avec le squelette ===
== Algorithme permettant de générer un Diagramme de Voronoï ==
Il est assez compliqué de programmer un diagramme de Voronoi entièrement avec un code propre et efficace, une solution aurait été de d'abord générer des points aléatoirement sur l'image, calculer les distances entres chaque point puis tracer les médiatrices des segments pour laquelle la distance entre chaque points serait minimale. Néanmoins, il aurait alors fallut supprimer les extrémités des médiatrices pour laquelle la distance minimale entre deux germes devenait trop grande, ce qui rend le programme plus compliqué à résoudre.

Une autre solution aurait été de générer des droites entre les points en faisant en sorte que chaque point soient à nombre égale dans chaqu'une de leurs parties et que les points les plus proches de la courbes soient à égales distances entre la droite et leur position, jusqu'à qu'il y reste qu'un point dans chaque unique partie du diagramme (Une sorte de dichotomie). On a ainsi plusieurs problèmes qui persistent. En plus du fait qu'il faudrait effacer des parties de médiatrices, si on se retrouve un nombre de points impair, il sera difficile de générer une droite séparant la moitié des points.

Le programme le moins compliqué est bien sûr le plus long à faire exécuter, sans parler qu'il utilise des répétitions. Il ne serait pas de générer le diagramme de Voronoi mais ses régions en différentes couleurs. Ainsi, le diagramme sera alors représenté par l'intersection des différentes couleurs. Voici le programme permettant de générer ces région:

<pre>
def distance2( p, q ):
return (p[0]-q[0])**2 + (p[1]-q[1])**2

def region_voronoi(n):
fenetre = Tk()
canvas=Canvas(fenetre, width=largeur, height=hauteur, background='white')
img = PhotoImage(width=largeur, height=hauteur)
couleurs=[]
points=[]
for i in range(n):
x =int(random.random()*(largeur-1))
y =int(random.random()*(hauteur-1))
points.append([x,y])
couleurs.append([int(random.random()*255),int(random.random()*255),int(random.random()*255)])
for i in range(hauteur-1):
for j in range(largeur-1):
min_k = 0
for k in range(1,n):
if distance2( (i,j), points[k] ) < distance2( (i,j), points[min_k] ):
min_k = k
r = couleurs[min_k][0]
g = couleurs[min_k][1]
b = couleurs[min_k][2]
img.put( "#%02x%02x%02x" % (r,g,b), (i,j) )
canvas.create_image((largeur/2,hauteur/2), image=img, state="normal")
canvas.pack()
fenetre.mainloop()
</pre>

Transformées en distance, diagramme de Voronoi et applications en geometry processing

2018-05-18T08:35:08Z

Wagner : /* Distance de Hausdorff */

Transformées en distance, diagramme de Voronoi et applications en geometry processing

2018-05-18T08:33:33Z

Wagner : /* Distance de Hausdorff */

Transformées en distance, diagramme de Voronoi et applications en geometry processing

2018-05-18T08:32:08Z

Wagner : /* Distance de Hausdorff */

Transformées en distance, diagramme de Voronoi et applications en geometry processing

2018-05-18T08:27:24Z

Wagner : /* Distance de Hausdorff */

Transformées en distance, diagramme de Voronoi et applications en geometry processing

2018-05-18T08:23:03Z

Wagner : /* Distance entre un point et un ensemble */

Transformées en distance, diagramme de Voronoi et applications en geometry processing

2018-05-18T08:16:13Z

Wagner : /* Distance entre un point et un ensemble */

Fichier:Distance entre un point et un ensemble.jpg

2018-05-18T08:10:57Z

Wagner :

Transformées en distance, diagramme de Voronoi et applications en geometry processing

2018-05-18T08:08:00Z

Wagner : /* Distance entre deux points */

Fichier:Distance entre deux points.jpg

2018-05-18T08:06:51Z

Wagner :

Transformées en distance, diagramme de Voronoi et applications en geometry processing

2018-05-18T08:06:02Z

Wagner : /* Distance de Hausdorff */

Fichier:Distance de Hausdorff.jpg

2018-05-18T08:03:52Z

Wagner :

Transformées en distance, diagramme de Voronoi et applications en geometry processing

2018-05-18T07:36:24Z

Wagner :

Transformées en distance, diagramme de Voronoi et applications en geometry processing

2018-05-17T21:27:30Z

Wagner : Page créée avec « Le diagramme de Voronoï et les transformées en distance sont deux outils mathématiques permettant de changer un ensemble de points en une surface triangulée. L'avanta... »