Mes remarques après lecture :
Dans ce tutoriel nous allons d'une part voir rapidement ce qu'est un diagramme de Voronoï, et d'autre part, étudier la façon dont on s'en sert dans le cadre de l'algorithme dit de Lloyd-Max. Le tout sera appuyé par un exemple de cas d'usage très courant ainsi qu'un peu de code source en C/C++
Introduction mal ficelée. Ou bien on connaît le sujet et on en a pas besoin, ou bien on le connaît pas et on apprend rien et on se sent perdu.
Il s’agit d’un objet mathématique découpant l’espace en cellules de manière particulière. On parle de pavage de Voronoï, ou de Voronoï tesselation en anglais.
Introduction de la notion à revoir pour la même raison. Quelles sont les motivations ? Quels sont les problèmes sous-jacents ?
On appelle région ou cellule (cell, en anglais) de Voronoï, associé à un élément p de S, l’ensemble de TOUS les points qui sont plus proches de p que de tout autre point de S. Ici, les élément de S sont des points de références et on évalue les distances entre ceux là et tous les points qui existent sur le plan. Parmi tous les points d’une cellule de Voronoï V, il ne peut y avoir qu’un seul élément de S : Celui qui a servie à construire V.
Il faut préciser la distance choisie.
À titre de rappelle un plan affine est un plan dans lequel il n’y aurait pas de repère. En effet dans ce plan nous ne nous intéressons pas aux positions des points mais à la distance de ceux là entre eux.
À revoir.
De nombreux domaines d'applications peuvent être ramené à la théorie du signal ce qui rend donc l'algorithme de Lloyd-Max très commode à utiliser en une ou n dimensions. En effet on représente le plus souvent un diagramme de LLoyd en deux dimensions, mais il est tout à fait possible de généraliser son principe en une ou trois dimensions. Par exemple dans le cas du domaine du traitement d'image, lorsque l'on veut réduire le nombre de couleurs d'une image on travaille en réalité avec un diagramme de Voronoï en trois dimensions, une pour chaque composante RGB de l'image. On pourrait d'ailleurs faire la même c
Il aurait fallu développer cet exemple. On voit qu'il se passe quelque chose mais on reste sur notre faim. À ce stade du tutoriel on devrait largement avoir pris connaissance du domaine d'application et un cas concret et adaptable, ce qui n'est pas le cas.
D'un point de vue abstrait, pour un diagramme de Voronoï non-restreint (c'est à dire pour lequel on considère tous les points de l'espace), l'algorithme de Lloyd-Max fait converger le diagramme dans un état tel que la différence entre toutes distances entre tous les germes soit minimisé. Dit autrement l'algorithme dont nous parlons fait en sorte que le barycentre d'une cellule de Voronoï donnée coïncide avec son germe. Ce type de diagrammes où les germes coïncident avec le barycentre de leurs cellules respectives est appelé diagramme de Voronoï centroïdal.
Il faut beaucoup plus de détails.
Actuellement je vois deux chantiers à mener :
- rendre l'exposé compréhensible : actuellement ça ressemble plus à une présentation à des spécialistes qu'à des néophytes ;
- motiver l'apprentissage dès le début.
