4.2 | 8 ratings Rate this file 39 Downloads (last 30 days) File Size: 1.65 MB File ID: #34428 Version: 1.6
image thumbnail




03 Jan 2012 (Updated )

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

| Watch this File

File Information

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


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

Required Products Mapping Toolbox
MATLAB release MATLAB 7.13 (R2011b)
MATLAB Search Path
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (22)
05 Apr 2015 shyam

shyam (view profile)

02 Apr 2015 Jakob Sievers

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

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

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?

Comment only
01 Apr 2015 Yuhang Wang  
31 Mar 2015 Jakob Sievers

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

Comment only
31 Mar 2015 Jakob Sievers

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

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.

31 Mar 2015 Yuanzhe

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?

Comment only
31 Mar 2015 Jakob Sievers

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?

Comment only
30 Mar 2015 Michele Guidi

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

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.

Comment only
30 Mar 2015 Yuanzhe

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,


22 Sep 2013 Jakob Sievers

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

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

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

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

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


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

Contact us