# 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

You are not logged in

## Discussion

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

Anonymous
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>
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]
voronoi(x,y)

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.

Anonymous
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>
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)

Anonymous

## Attached Files

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

Attach Files:

Comment:

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)

## Dependencies

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?
This task has 0 encouragements so far.

Only project members can vote.