How to break up voronoi cell into triangles (points from center, and two cell vertices)?

clc
clear all
close all
n=6;
 x=10*rand(n,1);
 y=10*rand(n,1);
 X = [x y];
[V,C] = voronoin(X);
 for i = 1:length(C)
 disp(C{i})
 end
[vx,vy] =voronoi(x,y);
close all
plot(x,y,'r+',vx,vy,'b-');

I am trying to break up each voronoi cell into triangles in order to find each cells area, but I do not know how. After 4 cell vertices, each cell can be broken up into n triangles (n vertices) assuming the cell is a closed simple curve.

[Sean]

The image below is a possible voronoi cell 'broken' up into triangles.

Answer 1

[Geoff Hayes]

Using the first example of http://www.mathworks.com/help/matlab/ref/voronoi.html,

 x = gallery('uniformdata',[1 10],0);
 y = gallery('uniformdata',[1 10],1);
 voronoi(x,y)

we see that there is one cell that is closed region with six vertices and point. As you have shown above, we can get all vertices for all cells with

 [V,C] = voronoin([x' y']);

In this case, the fourth cell is the closed region that we wish to find the area of with vertices and point in the cell given by

 cellVrtcs = V(C{4}',:);   % vertices for cell
 pntInCell = [x(4) y(4)];  % point in the cell

In this example, we have six vertices, so we have six triangles to find the areas of. So we take two neighbouring vertices, v1 and v2, and these two will form the base of the triangle which we can calculate as

 b = sqrt(sum((v1-v2).^2));  % using Euclidean distance to calculate base

We can find the lengths of each of the other two sides of the triangle, u and v, in a similar manner using the pntInCell

 u = sqrt(sum((pntInCell-v1).^2));
 v = sqrt(sum((pntInCell-v2).^2));

So we have the three lengths of the triangle and just need to find the height which we can easily do by splitting this triangle into two right-angled triangles with u and v each being the hypotenuse of one triangle. Let h be the height that we are trying to solve for, then by the Pythagorean Theorem

 % x^2     + h^2 = u^2   equation (1)
 % (b-x)^2 + h^2 = v^2   equation (2)

Note that we are solving for x and h. Substitute (1) into (2)

 % (b-x)^2            + u^2 - x^2 = v^2   from (1), h^2 = u^2 - x^2
 % b^2 - 2*b*x + x^2  + u^2 - x^2 = v^2   with (b-x)^2 expanded

 % x = (v^2-u^2-b^2)/(-2*b) gives us x
 % h = sqrt(u^2 - x^2)      gives us h

So given two neighbouring vertices and a point in the cell, the area of that triangle is

 b  = sqrt(sum((v1-v2).^2));
 u = sqrt(sum((pntInCell-v1).^2));
 v = sqrt(sum((pntInCell-v2).^2));
 x = (v^2 - u^2 - b^2)/(-2*b);
 h = sqrt(u^2 - x^2);
 triArea = 0.5*h*b;

So you just have to repeat this for every pair of neighbouring vertices in cellVrtcs, summing each triangle area which will give you the area of the cell.

To validate your calculated area, compare with polyarea(cellVrtcs(:,1),cellVrtcs(:,2)); which does the area calculation given a set of vertices.

Try out the above and see what happens!