Vertices of polygons in bounded voronoi diagram

I am new to matlab and I am facing a problem as follows.

I want to find out the vertices of polygons that make up the voronoi diagram limited by a rectangular boundary. I was trying to use 'Voronoin' function but I am not able to think of a way to extract out the vertices of the bounded polygons. Voronoin gives us vertices of unbounded polygons and not that of bounded version. Besides it also treats both posotive and negative infinities as Inf only. So, please help me.

[KalMandy]

Hi, have you found the solution for the above question? Please be kind enough to mention the solution here. Thanks

[Bruno Lopes]

You can use this code: https://it.mathworks.com/matlabcentral/fileexchange/34428-voronoilimit-varargin

It is the best I found on the internet.

Answer 1

[Matt J]

I have created a function (attached) which will obtain the Voronoi polygons in inequality form, and also optionally in vertex form if bounds are specified. It relies on files available in this FEX submission, which must be downloaded. It is probably not an optimally fast algorithm and I don't know how it compares to VoronoiLimit, but it is a simple and flexible tool. On my machine, I am able to process an input data set of 2000 seed points in 2D in about 2 sec.(R2021b);

[KalMandy]

Hi Matt, Thank you very much.I want to obtain vertices of the voronoi diagram bounded by the unit square defined by as x=0,y=0,x=1 and y=1. Do you know hoe to do it? Thanks!

[Matt J]

Yep. See my answer and the code attached there.

[KalMandy]

Hi Matt, I am very new to Matlab. So I am having hard time in understanding how to manipulate your code. I will be very grateful if you can help me with how to give the inputs in my case.

[Matt J]

The syntax of the routine is as below. It sounds like you want lb=[0,0] and ub=[1,1] if your points are in the unit square. Since you're new to MATLAB, I just want to be sure you know that you can obtain this kind of documentation with the commands "help voronoiPolyhedrons" or "doc voronoiPolyhedrons".

     [A,b,vert] = voronoiPolyhedrons( seeds,lb,ub )

 IN:        

     seeds: an NxM matrix of N-dimensional seed points
        lb: N-vector of lower bounds
        ub: N-vector of upper bounds

 OUT:       

        A,b: length M cell arrays such that A{i}*x<=b{i} 
             are the inequalities  
             of the i-th Voronoi polyhedron (i.e., of seed(:,i)), but
             restricted to bounds lb,ub

     vert: length M cell array such that vert{i} are the vertices of the
           i-th polyhedron. For this output to be requested, 
           finite box bounds, lb, ub must be given.

[Matt J]

I've made some edits to the help text which might clarify things further. Just to be absolutely clear, the "seeds" input is a matrix whose columns are the points you want to derive Voronoi cells from and lb,ub are upper and lower bounds defining a bounding box containing the points.

[KalMandy]

Hi Matt, thanks for your kind response.I have tried,

 [A,b,vert] = voronoiPolyhedrons( S,[0,0],[1,1] )

where

x = gallery('uniformdata',[1 10],1); %x coordinate of the seed 
y = gallery('uniformdata',[1 10],2); %y coordinate of the seed
S(:,1)=x;
S(:,2)=y;
But I am getting the following error, which I don't know how to fix.

Dimensions of matrices being concatenated are not consistent.

Error in voronoiPolyhedrons (line 54)
          A{i}=[A{i};Aq];

Error in testing (line 12)
[A,b,vert] = voronoiPolyhedrons( S,[0,0],[1,1] )

[Matt J]

Transpose S and rerun,

 S=S.';
 [A,b,vert] = voronoiPolyhedrons( S,[0,0],[1,1] )

[Adam Schroeder]

Hi Matt,

I appreciate the work you've done.

For others working with this, I would note that the vertices listed under 'vert' are listed in order from smallest value to largest value of the 1st dimension. This means that the function 'polyarea' cannot be used to calculate the area of these polygons, because the vertices are not in the required order.

For an example, look at the resultant 9th polygon:

   xmax=100;
  Nx=[39.0718    1.1132   12.0260   29.7727   59.0536   59.9179   21.2499   46.9227   15.6197   62.8036];
  Ny=[70.3064   77.4245   81.4226   96.5986    1.6205   36.6248   87.5568   62.7982   77.6720   77.2653];

    X(1,:)=Nx;
    X(2,:)=Ny;

    lb=[0 0];
    ub=[xmax xmax];
     [A,b,vert] = voronoiPolyhedrons(X,lb,ub); 

%calculate cell area using voronoiPolyhedrons
for i=1:length(vert)
    temp=cell2mat(vert(i));
    area(i)=polyarea(temp(1,:),temp(2,:));
end
disp(area)

[Matt J]

Hi Adam,

Because the polygons are convex in this case, it is probably better to use convhull() or convhulln() to compute the area. This will not depend on the ordering of the vertices.

[~,area(i)]=convhulln(vert{i}.');

[sanglok Yoo]

Hi, Matt

I tried your code voronoiPolyhedrons.m

But, error voronoiPolyhedrons (line 39) [Aq,bq]=addBounds([],[],[],[],varargin{:});

addBounds Undefined function or variable.

Could you solve this problem?

[Matt J]

sanglok, Looks like you didn't download the code mentioned in my post.

[sanglok Yoo]

Hi, Matt In my case, my boundary is polygon. I attached my zip file including .m file and .mat file. I'd like to plot voronoi in the polygon boundary. But my voronoi lines are out of the polygon boundary. Do you have idea to solve my code?

[Matt J]

Hi sanglok,

You can use voronoiPolyedrons to find the unconstrained voronoi polygons in inequality form A*x<=b. Once you have that, you can use intersectionHull, which you have already downloaded, to find their intersections with your boundary polyhedron.

[Matt J]

Thushananth Rajendra commented

Hey Matt,

I transposed my matrix and tried your code. It gave me the error

 Error using vertcat
 Dimensions of matrices being concatenated are not consistent.

 Error in voronoiPolyhedrons (line 54)
          A{i}=[A{i};Aq];

[Matt J]

Thushananth,

All input matrices should be in the orientation specified in the help doc.

[Matt J]

wang's comment relocated here:

It works, it runs much faster than VoronoiLimit.

[Mahmoud AlaaEldin]

Great work Matt J, I really benefited from your function and it fits exactly what I want. It runs much faster than VoroniLimit. Thanks alot for your effort. I just modified your main m-file by adding few lines that order the vertices of the polygons in the counter clock-wise direction. The ordering of the vertices is useful so that we can pass them to other functions that require this ordering.

[HG]

https://www.mathworks.com/matlabcentral/answers/855885-color-voronoi-diagram-and-coresponding-matrix?s_tid=prof_contriblnk

please answer my question if it's possible for you.

[Bruno Lopes]

You can also use this code: https://it.mathworks.com/matlabcentral/fileexchange/34428-voronoilimit-varargin

It is one the the best I found on the internet.

[Matt J]

That submission has been discussed. An earlier poster seemed to say

https://www.mathworks.com/matlabcentral/answers/258667-vertices-of-polygons-in-bounded-voronoi-diagram#comment_844383

that it was slow.

Answer 2

[Preetham Manjunatha]

Here is the link function to clip the extending edges of the Voronoi Diagram for rectangular or square region. Rigorously tested on the random points, this function can process an input data set of 2000 seed points in 2D in about 0.015 seconds on average.

[Matt J]

But it is exclusively for 2D, correct?

[Preetham Manjunatha]

Yes, only for 2D.