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 09 Feb 2013 11:43:55 PM UTC  
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 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 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.

Rik <rik5>
Project Administrator
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.

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

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

(file #38838)

Tasos Papastylianou <tpapastylianou>
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.

Rik <rik5>
Project Administrator
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?

Rik <rik5>
Project Administrator
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).

Tasos Papastylianou <tpapastylianou>
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)

Armin Müller <arm_in>
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.

Mike Miller <mtmiller>
Project Administrator
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.

Rik <rik5>
Project Administrator
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.


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 (21KiB - image/png - Screenshots for sample code)
file #38829:  Voronoi 38295 - Octave 4.0.3.png added by arm_in (19KiB - 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 30 Oct 2016 06:55:52 PM UTCrik5StatusNeed Info=>Fixed
    Fri 28 Oct 2016 07:30:54 PM UTCtpapastylianouAttached File-=>Added data.mat, #38838
    Fri 28 Oct 2016 10:14:37 AM UTCarm_inAttached File-=>Added Voronoi 38295 - Matlab R2015b.png, #38828
      Attached File-=>Added Voronoi 38295 - Octave 4.0.3.png, #38829
    Fri 28 Oct 2016 05:25:25 AM UTCmtmillerItem GroupInaccurate Result=>Incorrect Result
      Operating SystemGNU/Linux=>Any
    Fri 28 Oct 2016 05:23:33 AM UTCmtmillerDependencies-=>bugs #49463 is dependent
    Mon 30 Sep 2013 01:23:11 AM UTCmtmillerCategoryNone=>Octave Function
      StatusNone=>Need Info

    Back to the top

    Powered by Savane 3.1-cleanup1