How can I have the Centroidal Voronoi tessellation according to Lloyd's algorithm ?

23 views (last 30 days)
Ang Vas
Ang Vas on 19 Jun 2015
Commented: Ang Vas on 23 Jun 2015
I want to find the Centroidal Voronoi but I have been confused . For instance lets say that I have two vectors X=[1 2 1.1 1.3 1.4 1.5 1.3 1.2 1.8 2.1 2.2]; and Y=[1.5 1.3 1.5 1.8 1.4 1.6 2.5 2.3 2.4 1.1 1.8]; I use the command voronoi(X,Y) in order to have the diagram (see the attachment) . How can I have the Centroidal Voronoi tessellation according to Lloyd's algorithm ? I have found the Lloyd's algorithm in the internet :
while generating points xi not converged to centroids do
Compute the Voronoi diagram of xi
Compute the centroids Ci
using equation (1)
Move each generating point xi to its centroid Ci
end while
but I can't understand what I have to do in order to write the code and take the Centroidal Voronoi in matlab. Any ideas or alternatives please ?

Accepted Answer

Mukul Rao
Mukul Rao on 22 Jun 2015
I believe this can be done, but the process I have in mind is slightly tedious because the "voronoi" command in MATLAB does not appear to clip the boundaries to user specified values. However , here is what I have in mind based on the brief research I was able to do. I have explained my suggestions in terms of a pseudo-code:
%Define points for Voronoi diagram
X=[1 2 1.1 1.3 1.4 1.5 1.3 1.2 1.8 2.1 2.2];
Y=[1.5 1.3 1.5 1.8 1.4 1.6 2.5 2.3 2.4 1.1 1.8];
%Define diagram boundaries
xlim1 = 1;
xlim2 = 2.5;
ylim1 = 1;
ylim2 = 2.5;
%Generate the diagram and clip the boundaries
[vx,vy] = voronoi(X,Y);
axesHandle = gca;
axesHandle.XLim = [xlim1 xlim2];
axesHandle.YLim = [ylim1 ylim2];
%Extract topological information of the diagram
[v,c] = voronoin([X(:) Y(:)]);
%c is a cell array
%Each cell 'j' in c gives the set of indices 'i' that index into v such that
%all v(i,:)s define the polygon corresponding to X(j),Y(j)
%Example c{1} = [15 3 2 1 14]
%Polygon 1 that contains the seed or generator X(1),Y(1) is defined by
%vertices v(15,:) , v(3,:) , v(2,:), v(1,:) and v(14,:)
%%To account for the finite domain, write a routine to clip the edges for
%the generators or seeds at the boundares and add extra edges if necessary
%I do NOT have suggestions on how to write the code for this routine.
%%At this stage you should have all the required vertices [Vx,Vy] for each data point X(j) ,Y(j)
for iterations = 1:100 %Iterations for Lloyd's algorithm, you can replace this with a
%while loop with the correct termination criteria
for j = 1:length(X) %This loop can be vectorized
[ GEOM, INER, CPMO ] = polygeom(Vx,Vy) %polygeom is available on file exchange
centroidX = GEOM(2);
centroidY = GEOM(3);
%Replace the Xs and Ys with the computed centroids to form the
%seeds for the next iteration
X(j) = centroidX;
Y(j) = centroidY;
end
%Recompute Voronoi diagram
%Reprocess the edges to obtain the new pair of Vx and Vy for each
%X(j),Y(j)
end
Note that this code uses a function from file exchange called "polygeom" that can compute the centroid of a polygon as one of the many useful parameters, given the polygon's vertices. The link for this application is given below:

More Answers (0)

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!