Sun 30 Oct 2016 06:55:52 PM UTC, comment #9:
I had to completely change the algorithm that voronoi was using to determine whether edges were included or excluded from the output. The new method seems much more robust. I have tested it on the two failing cases in this bug report, as well as a few other corner cases. Since I was modifying the function, I also recoded sections for performance. It now runs 48% faster as well.
The change was made on the stable branch (http://hg.savannah.gnu.org/hgweb/octave/rev/8acad59ecec0). I think it will be part of the 4.2.1 bug fix release. But, this is just an m-file so if you need the change immediately you can get the file from Mercurial source control and just copy it in to your distribution.
Fixed, closing report.
|
Sat 29 Oct 2016 01:29:03 PM UTC, comment #8:
Copying the example problem from bug #49463
This sample input also has problems, but requires a different scale factor. That sugests that tuning the scale factor isn't the right solution because there will always be some input for which the scale factor is incorrect.
However, on the good news side, the points determined by voronoin are identical to Matlab. It is only the additional algorithm that we are applying after the calculation of these points in order to try and find the bisecting lines and rays to infinity that is at issue.
And even here, it is only the rays to infinity which are the problem.
|
Fri 28 Oct 2016 07:30:54 PM UTC, comment #7:
uploading data.mat as requested (generated on matlab 2013b)
(file #38838)
|
Fri 28 Oct 2016 07:25:41 PM UTC, comment #6:
There is quite a bit of post-processing in voronoi.m after the call to the internal function _voronoi_ which does the bulk of the work. The post-processing does the edge detection and there is a single scale parameter which, according to the note in the code, should be >= 2 in order to make the edge detection work well.
The scale factor was set exactly at 2. I changed it to 2.1 and I now get the correct output.
|
Fri 28 Oct 2016 07:06:26 PM UTC, comment #5:
Could someone try the following code in Matlab and upload the resulting data matrix?
|
Fri 28 Oct 2016 12:08:50 PM UTC, comment #4:
Apologies, I'm the original author of this bug, but this was back when I didn't have an account so I don't think I was notified of Rik's reply / request.
I'm still using the same matlab version as then (2013b), so it's not a case of former software versions. I probably just counted the edges by eye (and there's an edge which is very small and easily missed by eye).
|
Fri 28 Oct 2016 10:14:37 AM UTC, comment #3:
For your convenience, I've attached two screenshots from Matlab R2015b and Octave 4.0.3, respectively.
Matlab R2015b yields 8 vertices and 8 edges,
Octave 4.0.3 yields 10 vertices and 10 edges
(in contrast to the original bug report, which obviously is based on former software versions)
It look, at least, as if the bounds / limits / constraints are different.
(file #38828, file #38829)
|
Fri 28 Oct 2016 05:25:25 AM UTC, comment #2:
This can be considered confirmed, based on duplicate report bug #49463, but I guess that more detailed information is needed than just confirming that Matlab does return fewer vertices than Octave.
|
Wed 20 Mar 2013 07:35:29 PM UTC, comment #1:
Do you have access to Matlab? How many vertices does it return? This could be something about the options passed to the underlying QHull library.
|
Sat 09 Feb 2013 11:43:55 PM UTC, original submission:
In certain cases, the output of voronoi.m creates more edges than necessary.
In the example that follows, there should only have been 7 edges, but voronoi outputs 9; it's almost as if there's a phantom 6th point in that data which gets its own voronoi space.
Code:
Note: running voronoi(x,y) without collecting the vertices in vx and vy seems to plot well ... until you zoom out to reveal the extra edges.
|