bugGNU Octave - Bugs: bug #40996, voronoi doesn't return bisection...


bug #40996: voronoi doesn't return bisection line for input of two points

Submitted by:  None
Submitted on:  Tue 24 Dec 2013 10:08:28 AM UTC  
Category:  Octave Function Severity:  3 - Normal
Priority:  3 - Low Item Group:  Incorrect Result
Status:  Fixed Assigned to:  None
Originator Name:  hekawi Originator Email:  -email is unavailable-
Open/Closed:  Closed Release:  3.6.4
Operating System:  GNU/Linux

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)

Fri 03 Jan 2014 10:01:58 PM UTC, comment #10: 

This looks good. Thanks a lot!

hekawi <hekawi>
Fri 03 Jan 2014 06:54:48 PM UTC, comment #9: 

I pushed a changeset that fixes the issue here (http://hg.savannah.gnu.org/hgweb/octave/rev/5646f999245d).  This is on the development brach so you will need to get the file voronoi.m from Mercurial to see the change, or wait until the 4.2 release which will be a ways off.

Rik <rik5>
Project Administrator
Fri 03 Jan 2014 08:47:42 AM UTC, comment #8: 

The voronoi() function calls qhull with the given number of points
plus the four points of the binding box. Thus, it'll always have
a sufficient number of points for qhull.
But, in the current version it strips too many or too few points
from the result for two points. That's what caused the erroneous
output in that case. I corrected the reduction of the output.

hekawi <hekawi>
Fri 03 Jan 2014 06:09:37 AM UTC, comment #7: 

I see now that this is just an optical illusion.  The slope of the bisecting line is so large that it looks like it is vertical rather than bisecting the space between the two points. 

Rik <rik5>
Project Administrator
Fri 03 Jan 2014 01:07:59 AM UTC, comment #6: 

I wonder if you need to calculate the bisector directly (easy with 2 points) rather than using the output from QHull which we know is broken when the number of points is only 2.  I used one of the examples posted earlier.

voronoi([106, 323],[154, 151])

but the bisection line is not perpendicular to the line between the two points as I would expect.  See the attached image non_perpendicular_bisect.png.

Rik <rik5>
Project Administrator
Thu 02 Jan 2014 10:50:18 PM UTC, comment #5: 

I upload the voronoi() function that extracts the bisector,
if only two point were given as input.

please find the diff to your voronoi.m for release 4.2 and
the voronoibisector.m file that includes the bisector computation.

the solution for the bisector also fixes the regression bug #41068

let me know, if this is ok.

(file #30151, file #30152)

hekawi <hekawi>
Thu 02 Jan 2014 07:11:36 PM UTC, comment #4: 

Octave, like Matlab, relies internally on QHull for geometry like convex hulls and voronoi diagrams.  If you take a look at the Matlab documentation for voronoin (N-dimensional voronoi) (http://www.mathworks.com/help/matlab/ref/voronoin.html) they state that the minimum number of points is N+1.  So, for a 2-D diagram 3 points are required.  I added an input validation test to Octave in this changeset (http://hg.savannah.gnu.org/hgweb/octave/rev/31d8e19a745d).  The change is on the development branch which will eventually become release 4.2, but you can just grab the file voronoi.m from Mercurial and place it in your scripts/geometry directory to see the change.

If you want to write a patch to calculate the bisection line when the number of points is 2 I can review it and commit it if it looks good.

As for the problem with too many line segments, this is a regression from versions 3.2.4 and 3.4.3 of Octave where this worked correctly.  I filed a different bug report to track that here (bug #41068).

Rik <rik5>
Project Administrator
Thu 02 Jan 2014 02:53:20 PM UTC, comment #3: 

I ran the voronoi() calls on Matlab R2012:

In Matlab the voronoi diagram seems to be implemented using the
delaunay triangulation. Therefore, it complains about too few
points. Here's an example:

Matlab>> [vx,vy]=voronoi([106, 323],[154, 151])
Error using delaunay
Error computing the Delaunay triangulation. Not enough unique points

Error in voronoi (line 67)
        tri = delaunay(x,y);

It would be nice, if octave provided the bisector between the
two points.

hekawi <hekawi>
Fri 27 Dec 2013 05:35:54 PM UTC, comment #2: 

Currently, I don't have acces to matlab, but it surely should
return the bisector, or document that type of unusual behavior.

In addition, I found a related bug:
For certain point sets the octave voronoi function returns
too many line segments.
Here is a set of two points that yields five line segments
instead of just the bisector:

>>> [vx,vy]=voronoi([278, 155],[90, 195])

vx =

   216.500   535.451   216.500   344.080    88.920
    88.920   344.080   344.080    88.920  -102.451

vy =

  -231.1286   142.5000   516.1286   291.9514    -6.9514
    -6.9514   291.9514   291.9514    -6.9514   142.5000

hekawi <hekawi>
Fri 27 Dec 2013 04:14:42 PM UTC, comment #1: 

In terms of compatibility, do you have access to Matlab?  I would like to know how they handle this corner case.

Rik <rik5>
Project Administrator
Tue 24 Dec 2013 10:08:28 AM UTC, original submission:  

Instead of returning the bisector line between the given two points an empty result is returned.
Two examples:

>>> [vx,vy]=voronoi([106, 323],[154, 151])

vx = [](2x0)
vy = [](2x0)

>>> [vx,vy]=voronoi([92, 273],[228, 163])

vx = [](2x0)
vy = [](2x0)



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

Attach Files:

Attached Files
file #30151:  voronoibisector.m added by hekawi (7KiB - text/x-objcsrc - the voronoi.m file including the bisector and the diff to the voronoi.m file in release 4.2)
file #30152:  voronoi.diff added by hekawi (3KiB - text/x-patch - the voronoi.m file including the bisector and the diff to the voronoi.m file in release 4.2)


Depends on the following items: None found

Items that depend on this one: None found


Carbon-Copy List
  • -email is unavailable- added by hekawi (Posted a comment)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by hekawi

    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 9 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2014-01-03 rik5 StatusNeed Info => Fixed
        Open/ClosedOpen => Closed
    2014-01-03 rik5 Attached File- => Added non_perpendicular_bisect.png, #30156
    2014-01-02 hekawi Attached File- => Added voronoibisector.m, #30151
        Attached File- => Added voronoi.diff, #30152
    2014-01-02 rik5 Priority5 - Normal => 3 - Low
        Summaryvoronoi diagram has no result for two points => voronoi doesn't return bisection line for input of two points
    2013-12-27 rik5 StatusNone => Need Info
    2013-12-24 hekawi Carbon-Copy- => Added hekawi

    Back to the top

    Powered by Savane 3.5