[MATLAB] Delaunay/Veronoi Diagram - Get polygons

elbarto · #1 $Old$ September 15th, 2009, 01:08 AM

I am trying to calculate polygons around nodes to provide criteria for where the nodes can move during an optimization routine I am working on. Nodes are restricted to the square region u={0,1} and v = {0,1}.

Here is the code for the attached image. It is simply a delaunay triangulation and veronoi diagram of 10 random node positions.

Code:

x = [0.196 0.992 0.802 0.424 0.729 0.498 0.809 0.357 0.073 0.591];
y = [0.910 0.194 0.432 0.749 0.039 0.946 0.764 0.559 0.184 0.498];
figure(1)
TRI = delaunay(x,y);
[vx, vy] = voronoi(x,y,TRI);
triplot(TRI,x,y,'k-')
axis([0 1 0 1]);
hold on;
plot(x,y,'r+',vx,vy,'b-','LineWidth',3)
hold off
txt = cell(1,length(x));
for j=1:length(x);txt{j}=sprintf('  %i',j);end
text(x,y,txt,'FontSize',18)
axis square
xlabel('u')
ylabel('v')
title('Optimizing Nodes in u-v Domain')

Idealy what I would like to achieve is an array for the position of each voronoi point and a cell array containing the indexes of each point corresponding to each nodes polygon or voronoi cell depending on what you want to call it. All veronoi points must be within / lie on the square region and each node must be completely bound.

I can do something like this which will return something close to what I want for the bound cells ONLY (it also return points outside the bounds I am interested in):

Code:

[V,C] = voronoin(unique([vx(:) vy(:)],'rows'));
figure(2)
cla
hold on
for j = 1:length(C)
    patch('faces',C{j},'vertices',V)
end
hold off

Is there an efficient way to find out the bound regions of each node by also considering the boundaries u={0,1} and v = {0,1}. I am considering using this for an optimization routine I am working on where no node can be moved outside its veronoi cell within 1 iteration to prevent 2 nodes occupying the same possition so it is important that I can find a way to make sure each node has a corresponding "bound" cell consisting of points in the range u={0,1} and v = {0,1}.

I hope I have been clear enough, Please let me know if I need to post up more information.

Regards Elbarto