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

 
 

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

Submitter:  None
Submitted:  Sat 09 Feb 2013 11:43:55 PM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  Fixed Assigned to:  None
Originator Name:  poacheR Originator Email:  -email is unavailable-
Open/Closed:  * Closed Release:  * dev
Operating System:  * Any Fixed Release:  None
Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

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>
Group administrator
Sat 29 Oct 2016 01:29:03 PM UTC, comment #8: 

Copying the example problem from bug #49463


x=[1,2,3]
y=[2,3,1]
voronoi(x, y)


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>
Group 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>
Group 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?


x = [ 0.375797   0.756674   0.343954   0.202575   0.032301 ];
y = [ 0.16625   0.87870   0.83778   0.59153   0.59301 ];
[vx, vy] = voronoi(x,y);
vn = voronoin ([x(:), y(:)]);
save data.mat vx vy vn -v4



Rik <rik5>
Group 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.


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>
Group Member
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>
Group 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.

Code:

x = [ 0.375797   0.756674   0.343954   0.202575   0.032301 ];
y = [ 0.16625   0.87870   0.83778   0.59153   0.59301 ];
[vx vy] = voronoi(x,y);
plot(vx,vy);


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.

Anonymous

 

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

Attach Files:
   
   
Comment:
   

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

Items that depend on this one

Digest:
   bug dependencies.

 

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

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 10 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2016-10-30 rik5 StatusNeed Info Fixed
        Open/ClosedOpen Closed
    2016-10-28 tpapastylianou Attached File- Added data.mat, #38838
    2016-10-28 arm_in Attached File- Added Voronoi 38295 - Matlab R2015b.png, #38828
        Attached File- Added Voronoi 38295 - Octave 4.0.3.png, #38829
    2016-10-28 mtmiller Item GroupInaccurate Result Incorrect Result
        Operating SystemGNU/Linux Any
    2016-10-28 mtmiller Dependencies- bugs #49463 is dependent
    2013-09-30 mtmiller CategoryNone Octave Function
        StatusNone Need Info

    Back to the top

    Powered by Savane 3.13-f8d8.
    Corresponding source code