Calculate Voronoi Cell Area

Question

I am trying to calculate the Area of each Voronoi cell in matlab but I am stuck. I found this code online:

[v , c] = voronoin(sdata);
for i = 1 : size(c ,1)
  ind = c{i}';
  tess_area(i,1) = polyarea( v(ind,1) , v(ind,2) );
end

This code does not work because one of the points in v is [Inf,Inf]. This is a point in infinity. How can I bypass this problem?

score 4 · Answer 1 · answered May 08 '12 at 05:20

According to the example in the documentation for 'voronoin', the first point of v will always be [Inf, Inf]. Here's a quote:

The first row of V is a point at infinity. If any index in a cell of the cell array is 1, then the corresponding Voronoi cell contains the first point in V, a point at infinity. This means the Voronoi cell is unbounded.

If you want to use 'polyarea' on the vertices v without getting NaNs then my naive answer is to chop off the first row of v before inputting it into 'polyarea':

 sdata = [ 0.5    0
      0      0.5
     -0.5   -0.5
     -0.2   -0.1
     -0.1    0.1
      0.1   -0.1
      0.1    0.1 ]
[v , c] = voronoin(sdata);
for i = 1 : size(c ,1)
  ind = c{i}';
  tess_area(i,1) = polyarea( v(2:end,1), v(2:end,2))
end

But if that's not what you meant by "not working" then perhaps you can elaborate more on what you expected to see?

score 1 · Answer 2 · answered Oct 24 '13 at 15:53

this can avoid the NaN thing :

      [ v, c] = voronoin ( sdata );
       tess_area=zeros(size(c,1),1);

       for i = 1 : size(c ,1)
          ind = c{i}';
         if ind~=1
          tess_area(i,1) = polyarea( v(ind,1) , v(ind,2) );
         end
       end

score 0 · Answer 3 · edited May 23 '17 at 12:33

You need to define the boundaries of the space that you are interested in. For example, if you draw a square surrounding your voronoi cells, depending on the size of your square, the cells will have different areas.

The Voronoi partitioning by itself cannot set outer bounds on the cells.

If Matlab has a polygon intersection function, then it should be easy to do. Some relevant threads may be:

intersection and union of polygons

What is an simple way to compute the overlap between an image and a polygon?

If Matlab doesn't have this, you could manually calculate the intersection between the voronoi lines and the boundary lines of your polygon, and then calculate a new polygon based on that, from which you then calculate the area.

Calculate Voronoi Cell Area

3 Answers3