How to caluclate centroid of a voronoi cell of a voronoi diagram.

Suppose I have generated a voronoi diagram by following code:

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];

voronoi(X,Y)

Now, once the voronoi diagram is generated, how to find the centroid of each voronoi cell. I know there are lot of algorithms. One of them is Lloyd's Algorithm, the code of which is given here

https://www.mathworks.com/matlabcentral/fileexchange/41507-lloydsalgorithm-px-py-crs-numiterations-showplot

but after running the script , I am getting this error:

'poly2cw' requires Mapping Toolbox.

Error in lloydsAlgorithm>VoronoiBounded (line 178)

[X2, Y2] = poly2cw(V(C{ij},1),V(C{ij},2));

Error in lloydsAlgorithm (line 89)

[v,c]=VoronoiBounded(Px,Py, crs);

Can anyone help me in this.

[Bruno Luong]

The Vorinoi cells that contain a seed on the hull are unbounded, there is no centroid for such cells.

MATLAB voronoi just cuts them with an empiric bounding box. So of you use those outer vertexes the result is randomly cut.

Answer 1

[Matt J]

The voronoi cells are always convex, so assuming it is bounded, you can just take the mean of all the vertices of each cell.

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];

[V,C]=voronoin([X;Y]');

centroids = cell2mat(  cellfun(@(c) mean(V(c,:),1)'  , C','uni', 0)  )

centroids = 2×11

Inf 1.9180 1.1707 1.2800 1.1995 1.6029 Inf Inf Inf Inf Inf Inf 1.3544 1.4421 1.8802 0.5374 1.6873 Inf Inf Inf Inf Inf

[Matt J]

If you want to bound all the cells to, say ,a 5x5 square, you can use this FEX download

https://www.mathworks.com/matlabcentral/fileexchange/30892-analyze-n-dimensional-convex-polyhedra

together with the the attached voronoiPolyhedrons utility:

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];


[A,b,vert] = voronoiPolyhedrons( [X;Y],[-5 -5], [5 5]); %applies upper and lower bounds of +/-5

centroids=cell2mat(cellfun(@(z)mean(z,2), vert,'uni',0))

centroids =

Columns 1 through 8

-1.0711 1.9180 1.1707 1.2800 1.1995 1.6029 -0.1255 -1.6771

-0.5883 1.3544 1.4421 1.8802 0.5374 1.6873 4.0894 3.2947

Columns 9 through 11

2.6540 2.2785 3.2210

3.2021 -1.4444 2.0288

[Pallov Anand]

Thanks for your reply and this information, I needed this. But when I am running the section of the code you provided along with the voronoiPolyhedrons utility, I am getting this error:

Unrecognized function or variable 'addBounds'.

Error in voronoiPolyhedrons (line 39)

[Aq,bq]=addBounds([],[],[],[],varargin{:});

Can you help me with this. I can see, you have got the centroids, but why this error is showing in my case?

[Matt J]

Because you didn't download the files at the link I gave you.

[Pallov Anand]

Oh yes, my bad. I just downloaded voronoiPolyhedrons.m and was going through the overview given here

https://www.mathworks.com/matlabcentral/fileexchange/30892-analyze-n-dimensional-convex-polyhedra

Now, I downloaded and its working now. Thanks a lot mate.

Answer 2

[Constantino Carlos Reyes-Aldasoro]

This is not a trivial problem especially because the voronoi algorithm does not give you a series of closed polygons, i.e. change the axis of your current problem

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];
voronoi(X,Y)
axis([-2 4 -3 4])

You will see that the voronoi is finding lines that divide the points that you have provided, but it is not essentially generating polygons. Only some of these would be closed and then a centroid makes sense, but not for all of them

[Pallov Anand]

Ya, right. Lets take one region with vertices:

(1.7038, 1.3731) ; (1.8661, 1.6435); (1.7780, 1.9520); (1.6864, 1.9864); (1.29, 1.59); (1.2929, 1.5786)

For this region, I think centroid can be calculated and it should lie inside the region.