A Voronoi diagram is a diagram consisting of a number of sites.

Each Voronoi site s also has a Voronoi cell consisting of all points closest to s.



Task

Demonstrate how to generate and display a Voroni diagram.



See algo K-means++ clustering.




fcn generate_voronoi_diagram(width,height,num_cells){
   image,imgx,imgy:=PPM(width,height),width,height;
   nx:=num_cells.pump(List,(0).random.fp(imgx));
   ny:=num_cells.pump(List,(0).random.fp(imgy));
   nr:=num_cells.pump(List,(0).random.fp(256));  // red
   ng:=num_cells.pump(List,(0).random.fp(256));  // blue
   nb:=num_cells.pump(List,(0).random.fp(256));  // green
 
   foreach y,x in (imgy,imgx){
      dmin:=(imgx-1).toFloat().hypot(imgy-1);
      j:=-1;
      foreach i in (num_cells){
         d:=(nx[i] - x).toFloat().hypot(ny[i] - y);
	 if(d<dmin) dmin,j = d,i
      }
      image[x,y]=(nr[j]*0xff00 + ng[j])*0xff00 + nb[j];
   }
   image
}