Code covered by the BSD License

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

### Highlights from VoronoiLimit

4.33333
4.3 | 15 ratings Rate this file 32 Downloads (last 30 days) File Size: 4.94 KB File ID: #34428 Version: 2.6

# VoronoiLimit

### Jakob Sievers (view profile)

03 Jan 2012 (Updated )

Constrain the vertices of a Voronoi decomposition to the domain of the input data.

File Information
Description

The routine performs a Voronoi decomposition of an input dataset and constrains the vertices to the domain of the data themselves, such that even unbounded Voronoi cells become useful polygons (See attached figure).
[25th March 2015]: The routine has been updated to allow for the description of both an external boundary and multiple internal boundaries. See help for info.
[29th March 2015]: Bugfixes
[31th March 2015]: Bugfixes
[26th June 2015]: Bugfixes + addition of triangle external boundary example
[29th June 2015]: Bugfixes + output vertex order set to counter-clockwise
[7th July 2015]: Treatment of xy input points around boundaries improved (See example figure)
[9th July 2015]: Bugfixes
[21th July 2015]: Routine improved to allow for proper handling of cells which are split into two, or more, closed polygons. In these cases the original cell is split into an appropriate number of new cells.
[5th August 2015]: Bugfixes

Acknowledgements

This file inspired Lloyds Algorithm(Px,Py, Crs, Num Iterations, Show Plot) and Bounded Power Diagram.

Required Products Mapping Toolbox
MATLAB release MATLAB 8.5 (R2015a)
MATLAB Search Path
`/`
Tags for This File   Please login to tag files.
Comments and Ratings (43)
11 Jul 2016 Laura Veldenz

### Laura Veldenz (view profile)

Hello,
there is a difference between the function and the comment about the function (first line in the comments), as seen below, the input is in different orders:

function [V,C,XY]=VoronoiLimi(varagin)

so which one is correct? Or does it not make any difference>

Laura

Comment only
28 Jun 2016 Michal Kvasnicka

### Michal Kvasnicka (view profile)

good piece of code ...
well done!!!

28 Jun 2016 Ban-Sok

### Ban-Sok (view profile)

Thank you for this great function!
Unfortunately, I sometimes get this error:

Subscript indices must either be real positive integers or logicals.

Error in VoronoiLimit (line 152)
mvx=vx(2,mix); %missing vx

I used the unit square as an external boundary. Any idea how I can avoid this error? Thanks in advance!

26 Mar 2016 Morten Rishøj

### Morten Rishøj (view profile)

Works as advertised, simply put.

23 Mar 2016 Matt J

### Matt J (view profile)

Just a question. Are the polygons obtained by VoronoiLimit guaranteed to be the same as what you get if you take the unbounded Voronoi cells (as computed by VORONOIN, for example) and intersect them with a large rectangle?

Comment only
18 Feb 2016 Paul Martin

### Paul Martin (view profile)

Excellent, thanks Jakob,

it worked just fine for me!

I used the convex hull of my data as a boundary, as follows:

% Get convex hull of data
K=convhull(X, Y);

% Turn the hull into X,Y boundary values

BX = X(K); BY = Y(K);

% Do the special Voronoi limited by the data
[V , C, XY] = VoronoiLimit(X, Y, 'bs_ext', [BX; BY], 'plot', 'on');

12 Dec 2015 swheim

### swheim (view profile)

This fails for me when I use large bounds, for example in the given examples using the following bounds:

world_bounds_x = [-8,10];
world_bounds_y = [-4,14];
bs_ext = [world_bounds_x([1 1 2 2 1]);world_bounds_y([1 2 2 1 1])]';

Also, when shrinking this bound, it sometimes makes slightly innaccurate bounds (i.e. one of the bounded-rectangle corners is slightly shifted).

10 Jul 2015 Pearl

### Pearl (view profile)

03 Jul 2015 Jakob Sievers

### Jakob Sievers (view profile)

Hi Preeti

Please send me an email with a description of the problem along with the specific xy coordinates you use (.mat file) so that I may have a look at it and figure out what the problem is.

Cheers

Comment only
03 Jul 2015 Preeti Goel

### Preeti Goel (view profile)

I wanted to get the points as per the external boundary, I got bugs with some examples. It was fixed when I used VoronoiBounded from the Lloyds Algorithm(Px,Py, Crs, Num Iterations, Show Plot).

Comment only
03 Jul 2015 Preeti Goel

### Preeti Goel (view profile)

I believe there is a bug in this section of the code

if length(C{ij})<3
C{ij}(1)=lV0+ixa(1);
C{ij}=[C{ij},lV0+ixa(2)];

for one of my examples:
with 3 points
one voronoi vertex in ext boundary
3 end points computed
the voronoi cells are not computed correctly and all are the same. Please help. I wanted to add files, but I do not see an option to do that here, I can send them an email id if needed. Thanks

Comment only
26 Jun 2015 Jakob Sievers

### Jakob Sievers (view profile)

Hi Zu
I have added a triangle example to the current version of the file. Please download and test to see how it works. You can use any form of external boundary as long as it contains all of the x,y input points.
Cheers
Jakob

Comment only
26 Jun 2015 Zu Mailand

### Zu Mailand (view profile)

could you give me an example? the external boundary is belonging to triangle.

Comment only
25 Jun 2015 Jakob Sievers

### Jakob Sievers (view profile)

The input variable "bs_ext" which is responsible for the external boundary, takes any number of vertices, meaning that you could just as easily describe a circle or whatever else you need :)

Comment only
24 Jun 2015 Francesco

### Francesco (view profile)

Hi Jakob,

The current limited domain is only a rectangular or a square. If the limited domain is a circle or a triangle, can we modify more for your Matlab code? Thanks

Comment only
24 Jun 2015 Jakob Sievers

### Jakob Sievers (view profile)

Hi francesco
I'm not sure I understand your question. The function supports both internal an external bounds such as illustrated (e.g. run with no input to see how it works). Is the bound you are thinking of not covered by any of these options?

Comment only
24 Jun 2015 Francesco

### Francesco (view profile)

Thanks Jakob. I figured out :)

We should use dt=DelaunayTri(x(:),y(:)).

A question, if I want a bound domain which is rectangular, triangle or any more complicated geometry. How could I do for your function?
Thanks

Comment only
24 Jun 2015 Jakob Sievers

### Jakob Sievers (view profile)

Hi Francesco. The DelaunayTri function will be removed from Matlab in favor of the DelaunayTriangulation function (http://se.mathworks.com/help/matlab/ref/delaunaytri.html). I don't know when the latter was implemented but it might be after the 2012 edition of Matlab, which is why it does not show up in your version of Matlab. Unless you upgrade to current matlab I suggest you use DelaunayTri if that works for you.

Cheers

Jakob

Comment only
24 Jun 2015 Jakob Sievers

### Jakob Sievers (view profile)

Hi Francesco

I forgot to add the link to the information in question:
http://se.mathworks.com/help/matlab/ref/delaunaytri.html

Comment only
24 Jun 2015 Francesco

### Francesco (view profile)

It seems that it should be the function 'dt=DelaunayTri(x(:),y(:))', right?

Comment only
24 Jun 2015 Francesco

### Francesco (view profile)

I have an error when compiling

Undefined function 'delaunayTriangulation' for input arguments of type 'double'.

Error in VoronoiLimit (line 96)
dt=delaunayTriangulation(x(:),y(:));

As checked, I cannot find the function delaunayTriangulation in my Matlab R2012b.

Thanks

05 Apr 2015 shyam

### shyam (view profile)

02 Apr 2015 Jakob Sievers

### Jakob Sievers (view profile)

One of my comments was removed so I'll reiterate briefly: three points is at the lower limit of when delaunayTriangulation can actually provide voronoi cells. if length(x)>3, however, cells begin to form.

Comment only
02 Apr 2015 Jakob Sievers

### Jakob Sievers (view profile)

Follow-up comment: You may be able to solve this by: (1) deriving the centroid of the three points, (2) extrapolating each point based on this centroid far beyond the external bounds you have specified to add three extra points, (3) using all 6 pointsto create the voronoi cells. The program should remove the outer three points automatically. This is just off the top of my head so get back to me if you try this and it works or doesn't.

Comment only
02 Apr 2015 Yuanzhe

### Yuanzhe (view profile)

Hi Jakob
That problem has been sovled. However, I find another bug. When you just choose three points as the generator, for example, (-1,0), (1,0) and (0,1) are generators, and choose the boundary as 'boundary_x=[-2;2;2;-2;-2];boundary_y=[-2;-2;2;2;-2];'. The program cannot give the right result. At this stage, I have not found the reason and I am trying to solve it. Do you know why?
Thanks.
Yuanzhe

Comment only
01 Apr 2015 Yuhang Wang

### Yuhang Wang (view profile)

31 Mar 2015 Jakob Sievers

### Jakob Sievers (view profile)

New version uploaded. Please let me know if this solves the problem for you!

Comment only
31 Mar 2015 Jakob Sievers

### Jakob Sievers (view profile)

AH. I just noticed I had made a "range" function back in the day and its output was a vector of size=[1 2] where the values where min/max of the input vector respectively. This explains everything. Matlab must have used my "range" function instead of the one native to the program. I will fix this immediately and upload a new version ASAP. Stay tuned for the update.

Comment only
31 Mar 2015 Yuanzhe

### Yuanzhe (view profile)

Hi Jakob
Another question. Could one vertex connect with three or more infinite vertices? If so, it seems that the program does not consider this situation. Is that right? Thank you.
Regards,
Yuanzhe

31 Mar 2015 Yuanzhe

### Yuanzhe (view profile)

Hi Jakob
I have check the result of the code. It seems that "range function gives the difference between the minimum and maximum of a vector". So the code "rx=range(x);" just gets rx of 1 times 1 dimension. But if I change this code to "rx=[min(x),max(x)];", the program could run. Is that right?
Thanks.
Yuanzhe

Comment only
31 Mar 2015 Jakob Sievers

### Jakob Sievers (view profile)

Dear Michele
This is all a bit puzzling to me. When run without input x and y are both vectors. Consequently rx=range(x) and ry=range(y) gives two-element min/max ranges (size=[1,2]) and bnd=[rx ry]; becomes a four-element vector (size=[1,4]) on which crs is based. I cant figure out what might be going wrong based on your (and Yuanzhe's) description. Could you elaborate a bit? Are you running with no input or with user-defined input, and if so; what kind?
Cheers
Jakob

Comment only
30 Mar 2015 Michele Guidi

### Michele Guidi (view profile)

I downloaded the last verion today since this function would really help me a lot and I found the same error of Yuanzhe.
It is in the creation of the crs matrix (lines 77-82), where using the function RANGE(X), with X being a vector, simply return the range between the max and min value and not a vector, so it attempt to access an index out of bound.
I tried to fix the problem myself but made some avalanche consecutive errors.

30 Mar 2015 Jakob Sievers

### Jakob Sievers (view profile)

Dear Yuanzhe
I do not get that error, but I have been doing a number of bugfixes these past few days so maybe if you try downloading the current version you won't experience that error? Please get back to me in case that didn't work for you.
Cheers
Jakob

Comment only
30 Mar 2015 Yuanzhe

### Yuanzhe (view profile)

Dear Jakob
When run the program without input, there is an error. As x and y are vectors, bnd only has two elements and bnd(4) does not exist. So how to solve it? Thanks.

Comment only
20 Mar 2015 Kobye

### Kobye (view profile)

Excellent function. I agree with Michele that an edge constraint functionality would be great to handle internal polygonal edges in the domain, e.g. plate with a hole cutout. The default DT = DelaunayTri(points,EC) function has the EC input variable to handle this. From this Delaunay Triangulation, the Voronoi tesselation can be calculated. This could be a good starting point.

01 Jul 2014 UIC

### UIC (view profile)

Dear Jakob,
There is only a small bug in the code you may resolve that. for some Voronoi cells (specially those near edges) vertices are not correct. Would you mind to check that.

Good luck,

Ashkan,

22 Sep 2013 Jakob Sievers

### Jakob Sievers (view profile)

Hi Michele
That is an interesting case. I am very limited timewise at the moment but when I do return to this function I will definitely take it into consideration. Could be interesting to add options for empty spaces of arbitrary polygon shapes within the bounding box.

Comment only
06 Sep 2013 Michele

### Michele (view profile)

Great function!
I have a question though. Is it possible to add new internal bounds, for example a "hole" inside a square region?
Thanks

Comment only
02 Jul 2012 maxime

### maxime (view profile)

Great function !
I upgraded it for using it with any bounding shape. Just replacing "crs" variable by any polygon.
Works fine !

20 Jun 2012 S

### S (view profile)

11 Mar 2012 Pearl

### Pearl (view profile)

I 2nd Richard. I'm trying to get extended boundary, but still have no luck. Let me know if you have chance to upgrade the code. However, I don't have the mapping toolbox either :"(

Comment only
03 Feb 2012 Jakob Sievers

### Jakob Sievers (view profile)

I have indeed considered adding an option to describe extended boundaries yourself. I will see if I get the time to make those changes.
I am not aware of any file-exchange alternatives to what polybool does, so I'm afraid the mapping toolbox remains a requirement.

Comment only
24 Jan 2012 Richard Garner

### Richard Garner (view profile)

Thanks for this, as I have run into the same problem, with a slight variation. I want the Voronoi diagram limited by a larger boundary outside of the original set of vertices from which the Voronoi diagram is calculated. HOWEVER, unfortunatey I cannot use your function because I do not have the mapping toolbox.

Comment only
25 Mar 2015 1.1

UPDATE 25th March 2015: The routine has been updated to allow for the description of both an external boundary and multiple internal boundaries. See help for info.

29 Mar 2015 1.2

Bugfixes

29 Mar 2015 1.3

New figure

29 Mar 2015 1.4

Bug fixes

30 Mar 2015 1.5

Bug fixes

31 Mar 2015 1.6

[31th March 2015]: Bugfixes

26 Jun 2015 1.7

Bugfixes + addition of triangle external boundary example

26 Jun 2015 1.8

Bug fixes

29 Jun 2015 1.9

Output vertex order set to counter-clockwise

29 Jun 2015 2.0

Bugfixes

07 Jul 2015 2.1

[7th July 2015]: Treatment of xy input points around boundaries improved (See example figure)

07 Jul 2015 2.2

bugfixes

09 Jul 2015 2.3

Bugfixes

21 Jul 2015 2.4

Routine improved to allow for proper handling of cells which are split into two, or more, closed polygons. In these cases the original cell is split into an appropriate number of new cells.

05 Aug 2015 2.5

Bugfixes

05 Aug 2015 2.6

Bugfixes