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
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.
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?
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.
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.
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.
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?
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.
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?
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?
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.
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.
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.
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.
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.
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.
25 Mar 2015
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
29 Mar 2015
29 Mar 2015
30 Mar 2015
31 Mar 2015
[31th March 2015]: Bugfixes
26 Jun 2015
Bugfixes + addition of triangle external boundary example