bugGNU Octave - Bugs: bug #54896, voronoi produces no edges for...


bug #54896: voronoi produces no edges for provided data

Submitted by:  None
Submitted on:  Thu 25 Oct 2018 03:05:12 PM UTC  
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  Confirmed Assigned to:  None
Originator Name:  Pavel Remygailo Originator Email:  -email is unavailable-
Open/Closed:  Open Release:  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)

Thu 29 Nov 2018 05:44:33 PM UTC, comment #7: 

I can confirm that it is Octave post-processing of the edges that is the problem.  Unfortunately, I'm not sure I have a solution--computational geometry is not my area of expertise so I don't understand particularly how to replace the algorithm we have with a better one.

This could go on to the Bugs or Projects List and maybe we could enlist some outside help.  You might also put in a request on the Octave-Maintainer's list to see if there is someone with the requisite knowledge to look at this report.

Rik <rik5>
Project Administrator
Wed 31 Oct 2018 04:42:59 AM UTC, comment #6: 

As I understand it, Matlab still uses QHull.  It just doesn't expose the API to programmers anymore.  With Matlab, you are stuck using whatever options they think are appropriate.

But, I don't think this is a problem with the QHull library.  The voronoi function in voronoi.m does post-processing on the edges found.  I think there may be an issue there.  The code is

  if (numel (x) > 2)
    ## Eliminate the edges of the diagram representing the box.
    ## Exclude points outside a certain radius from the center of distribution.
    ## FIXME: Factor should be at least 1.0.  Octave uses 1.1 for margin.
    ## There is no theoretical justification for this choice.
    ctr = [(xmax + xmin)/2 , (ymax + ymin)/2];
    radius = 1.1 * sumsq ([xmin, ymin] - ctr);
    dist = sumsq (p - ctr, 2);

    p_inside = (1:rows (p))(dist < radius);
    edge_inside = any (ismember (edges, p_inside));
    edges = edges(:, edge_inside);

If I change the factor from 1.1 to 100.1 then I get a figure equivalent to Matlab.  If I comment out the code completely I get an en equivalent figure as well.

Rik <rik5>
Project Administrator
Fri 26 Oct 2018 05:27:11 PM UTC, comment #5: 

Retagging as incorrect result.

We can continue to use QHull unless there is something better available now.

If it is important to you, open a separate bug report about the changes in Matlab's voronoi interface.

John W. Eaton <jwe>
Project Administrator
Fri 26 Oct 2018 02:17:53 PM UTC, comment #4: 

Looks like R2018b doesn't use QHull because it doesn't support QHull-specific options anymore https://www.mathworks.com/help/matlab/ref/voronoi.html

Fri 26 Oct 2018 06:58:01 AM UTC, comment #3: 

If you think it is important to handle this corner case, could you play with QHull options (see "help voronoi" and references there in) and try to see if you can get Octave to match Matlabs behavior (IIRC ML also uses QHull). Maybe we are not passing the right options.

Pantxo Diribarne <pantxo>
Project Member
Thu 25 Oct 2018 04:54:57 PM UTC, comment #2: 

Actually, this was part of the larger dataset

x =[1, 1, 2, 2, 2, 4, 4, 8, 8, 16, 32, 64]
y = [1.0, 2.0, 4.0, 8.0, 15.25, 16.0, 30.5, 32.0, 61.0, 122.0, 244.0, 488.0]

with which you get some edges, but last three points are hanging in the air, instead I would expect to have parallel edges separating them.

Tried my first example in Matlab Live editor and it failed saying that points are collinear, but this second one works fine showing parallel lines for last four points, while in Octave they are absent.

Thu 25 Oct 2018 03:57:08 PM UTC, comment #1: 

I think this is an invalid input (what kind of voronoi cell would you expect from collinear points?) and voronoin fails as I would expect:

>> x = [8, 16, 32, 64]
>> y = [61.0, 122.0, 244.0, 488.0]
>> voronoin([x' y'])

QH6239 Qhull precision error: Initial simplex is cocircular or cospherical.  Use option 'Qz' for the Delaunay triangulation or Voronoi diagram of cocircular/cospherical points.  Option 'Qz' adds a point "at infinity".    Use option 'Qs' to search all points for the initial simplex.

While executing:  | qhull v Qbb
Options selected for Qhull 2015.2 2016/01/18:
  run-id 824596463  voronoi  Qbbound-last  _pre-merge  _zero-centrum  Pgood
  _max-width 4.3e+02  Error-roundoff 6.8e-13  _one-merge 4.7e-12
  _near-inside 2.4e-11  Visible-distance 1.4e-12  U-coplanar-distance 1.4e-12
  Width-outside 2.7e-12  _wide-facet 8.1e-12
error: voronoin: qhull failed
error: called from
    voronoin at line 73 column 12

Probably the only bug here is that voronoi fails silently instead of firing an explicit error.

Pantxo Diribarne <pantxo>
Project Member
Thu 25 Oct 2018 03:05:12 PM UTC, original submission:  

x = [8, 16, 32, 64]
y = [61.0, 122.0, 244.0, 488.0]
voronoi(x, y)



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

Attach Files:

Attached Files
file #45293:  matlab_voronoi.png added by None (26KiB - image/png)
file #45294:  octave_voronoi.png added by None (25KiB - image/png)
file #45292:  Screenshot (1).png added by None (10KiB - image/png)


Depends on the following items: None found

Items that depend on this one: None found


Carbon-Copy List
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by jwe (Posted a comment)
  • -email is unavailable- added by pantxo (Posted a comment)
  • -email is unavailable- added by None (Submitted the item)

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

    Only project members can vote.




    Follow 8 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2018-10-31 rik5 CategoryLibraries => Octave Function
        Release4.2.1 => dev
    2018-10-26 jwe Item GroupMatlab Compatibility => Incorrect Result
    2018-10-26 pantxo Item GroupIncorrect Result => Matlab Compatibility
        StatusNone => Confirmed
    2018-10-25 None Attached File- => Added matlab_voronoi.png, #45293
        Attached File- => Added octave_voronoi.png, #45294
    2018-10-25 None Attached File- => Added Screenshot (1).png, #45292

    Back to the top

    Powered by Savane 3.5