Vamos a usar autómatas celulares para calcular el diagrama de Voronoi de varios puntos. El diagrama de voronoi se calcula a partir de una serie de puntos P[i] en un espacio (en este caso un plano). A partir de cada uno de esos puntos P[i] crea uno polígono según la siguiente regla: un punto del plano pertenecerá a un polígono si no hay ningún otro punto P[i] más cercano. Las fronteras entre estos polígonos (Polígonos de Thiessen) son el diagrama de Voronoi.

<
De Gottie (fuente Wikipedia Image:Voronoi.png), Dominio público

En este las reglas del autómata son sencillas, si un vecino tiene una distancia menos que la propia, copia su color y su distancia + 1.

for(var i = 0; i < neighbors.length; ++i){
   if(neighbors[i].creature.distance < this.distance){
     this.distance = neighbors[i].creature.distance+1;
     this.point = neighbors[i].creature.point; 
} } 

Queda inicializar las celdas, para ello una celda puede ser dos tipos:

• un punto a partir del cual calcular las fronteras o una celda normal, su distancia es 0 y se inicializan con un color de una lista.
• una celda nomal, se inicializan sin pertenecer a ningún polígono, con color blanco y un valor de distancia muy grande (lo ideal seria infinito pero con que sea mayor que cualquier distancia entre dos puntos de la rejilla de celdas también sirve)

if(this.isPoint){
  this.distance = 0;
  this.point = initPointsNumber;
  initPointsNumber++;    
} else {
  this.point = -1;
  this.distance = 10000;
}

El funcionamiento del autómata es muy parecido al algoritmos de inundación las distancias menores se van propagando junto con el color hasta que encuentran un vecino cuya distancia es menor, en es punto es donde se encuentra el borde del polígono.

Tenéis el código aquí y un ejemplo aquí, el resultado es:

Si os fijáis bien parece que la imagen está cortada por los extremos, eso es porque en este caso no estamos calculando el diagrama de Voronoi en un plano si no en un toro (que es la forma geométrica del mundo de este autómata) por eso los polígonos cuando salen por un extremo continúan por el otro.

Puedes ver un vídeo sobre como funciona en mi canal de Youtube: