1
$\begingroup$

I am facing a problem as follows: I have created a Voronoi diagram and now I want to assign to each region, a value, i.e., I want to extend this Voronoi diagram to form a 2 variable function in Matlab. For example, let one of the cells be named $R_1$, I want that the 2 variable function I am going to assign a constant value (e.g., $f(x,y)=4$) to all the points in $R_1$. Similarly for the other cells.

Edit: I am including the information about how Voronoi diagram is being stored herein. What I am using is voronoin function that returns the vertices of polygons and cells with corresponding vertices of which they are made up of. Also, since the edges partitioning in Voronoi diagrams are straight lines, it is possible to trace out the cells.

$\endgroup$
2
$\begingroup$

You can use the griddata function with the 'nearest' option to accomplish this. For better performance with multiple calls to your function use a kd-tree nearest neighbor search.

To use the griddata method, simply define a set of values, F for the cells and use the points that determined the Voronoi diagram X, Y for nearest neighbor interpolation. To do this you will obviously need to know the points that defined the Voronoi diagram. I'm guessing you have those points since you said you're using the voronoin function to produce the Voronoi diagram. You can define your function as f = @(x_in,y_in) griddata(X,Y,F,x_in,y_in,'nearest'); and then call it as f(x,y).

If you need to do this for many separate calls to your function it will be much faster to define a search tree and then re-use it. If you have the statistics toolbox you can do this with KD Trees as follows:

clear
X=rand(15,1);
Y=rand(15,1);
kdtree = KDTreeSearcher([X(:),Y(:)]);
F(:,1)=(1:15);
f = @(x_in,y_in) F( kdtree.knnsearch([x_in(:),y_in(:)]) );
x=rand(1000,1);
y=rand(1000,1);
fvals = f(x,y);
figure(1)
clf
hold on
voronoi(X,Y,'kx')
scatter(x,y,100,fvals,'.')

Scatter plot with Voronoi cells


Note:
I think any solution that explicitly searches for which polygonal Voronoi cell contains a point will be much slower than this method. If you do not know the points that determined the Voronoi diagram it might be possible to determine them from the cells.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.