Hi Folks,

Does anybody know how to get a centroidal Voronoi tessellation (CVT)  out of a Voronoi tesellation generated with either the Voronoi Diagram from the Mesh Library ( http://www.leebyron.com/else/mesh/)     or toxiclibs library.

The algorithm is very simple, but somehow I cannot get hands on the correct solution: Its called Lloyds algorithm and goes like this

• The Voronoi diagram of all the points is computed.
• Each cell of the Voronoi diagram is integrated and the centroid is computed.
• Each point is then moved to the centroid of its voronoi cell.

So basically one just needs to access the myRegions[] array (on the Mesh library) and get the area or better directly the centroid.

Any ideas on how to to that?

The goal would be to iterate the Voronoi tesselation until the distribution of the polygons is almost even (with a certain threshold)
http://en.wikipedia.org/wiki/Lloyd%27s_algorithm

Anybody has ideas or has done something similar? Thanks alot.

Here the Mesh library code to begin with

1. float[][] points = new float[3][2];
   			
   points[0][0] = 120; // first point, x
   points[0][1] = 230; // first point, y
   points[1][0] = 150; // second point, x
   points[1][1] = 105; // second point, y
   points[2][0] = 320; // third point, x
   points[2][1] = 113; // third point, y
   
   Voronoi myVoronoi = new Voronoi( points );

   MPolygon[] myRegions = myVoronoi.getRegions();
   
   for(int i=0; i<myRegions.length; i++)
   {
   	// an array of points
   	float[][] regionCoordinates = myRegions[i].getCoords();
   	
   	fill(255,0,0);
   	myRegions[i].draw(this); // draw this shape
   }