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

3 visualizaciones (últimos 30 días)
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.

Respuesta aceptada

Geoff Hayes
Geoff Hayes el 27 de Jun. de 2014
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!

Más respuestas (0)

Categorías

Más información sobre Voronoi Diagram en Help Center y File Exchange.

Productos

Community Treasure Hunt

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

Start Hunting!

Translated by