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

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 ?

[Walter Roberson]

The attachment did not make it.

[Ang Vas]

anyone for this ???

Answer 1

[Mukul Rao]

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:

http://www.mathworks.com/matlabcentral/fileexchange/319-polygeom-m

[Ang Vas]

Thanks so much for your help.