bugGNU Octave - Bugs: bug #38295, Voronoi outputs wrong results...


bug #38295: Voronoi outputs wrong results (more edges than necessary)

Submitted by:  None
Submitted on:  Sat Feb 9 23:43:55 2013  
Category: Octave FunctionSeverity: 3 - Normal
Priority: 5 - NormalItem Group: Incorrect Result
Status: FixedAssigned to: None
Originator Name: poacheROriginator Email: -unavailable-
Open/Closed: ClosedRelease: dev
Operating System: Any

Add a New Comment (Rich MarkupRich Markup):

You are not logged in

Please log in, so followups can be emailed to you.


(Jump to the original submission Jump to the original submission)

Sun Oct 30 18:55:52 2016, 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.

Rik <rik5>
Project Administrator
Sat Oct 29 13:29:03 2016, 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.

Rik <rik5>
Project Administrator
Fri Oct 28 19:30:54 2016, comment #7:

uploading data.mat as requested (generated on matlab 2013b)

(file #38838)

Tasos Papastylianou <tpapastylianou>
Fri Oct 28 19:25:41 2016, 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.

Rik <rik5>
Project Administrator
Fri Oct 28 19:06:26 2016, comment #5:

Could someone try the following code in Matlab and upload the resulting data matrix?

Rik <rik5>
Project Administrator
Fri Oct 28 12:08:50 2016, 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).

Tasos Papastylianou <tpapastylianou>
Fri Oct 28 10:14:37 2016, 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)

Armin Müller <arm_in>
Fri Oct 28 05:25:25 2016, 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.

Mike Miller <mtmiller>
Project Administrator
Wed Mar 20 19:35:29 2013, 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.

Rik <rik5>
Project Administrator
Sat Feb 9 23:43:55 2013, 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.


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.



(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach File(s):

Attached Files
file #38838:  data.mat added by tpapastylianou (405B - application/octet-stream - data.mat file as requested by Rik.)
file #38828:  Voronoi 38295 - Matlab R2015b.png added by arm_in (21kB - image/png - Screenshots for sample code)
file #38829:  Voronoi 38295 - Octave 4.0.3.png added by arm_in (19kB - image/png - Screenshots for sample code)


Depends on the following items: None found

   bug dependencies.


Carbon-Copy List
  • -unavailable- added by tpapastylianou (Posted a comment)
  • -unavailable- added by arm_in (Updated the item)
  • -unavailable- added by mtmiller (Updated the item)
  • -unavailable- added by rik5 (Posted a comment)
  • -unavailable- added by None (Submitted the item)

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only project members can vote.


    Please enter the title of George Orwell's famous dystopian book (it's a date):



    Follow 10 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Sun Oct 30 18:55:52 2016rik5StatusNeed Info=>Fixed
    Fri Oct 28 19:30:54 2016tpapastylianouAttached File-=>Added data.mat, #38838
    Fri Oct 28 10:14:37 2016arm_inAttached File-=>Added Voronoi 38295 - Matlab R2015b.png, #38828
      Attached File-=>Added Voronoi 38295 - Octave 4.0.3.png, #38829
    Fri Oct 28 05:25:25 2016mtmillerItem GroupInaccurate Result=>Incorrect Result
      Operating SystemGNU/Linux=>Any
    Fri Oct 28 05:23:33 2016mtmillerDependencies-=>bugs #49463 is dependent
    Mon Sep 30 01:23:11 2013mtmillerCategoryNone=>Octave Function
      StatusNone=>Need Info

    Back to the top

    Powered by Savane 3.1-cleanup1