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 FunctionSeverity: 3 - Normal
Priority: 3 - LowItem Group: Incorrect Result
Status: FixedAssigned to: None
Originator Name: hekawiOriginator Email: -unavailable-
Open/Closed: ClosedRelease: 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 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.

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.

(file #30156)

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

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)

Anonymous

 

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

Attach File(s):
   
   
Comment:
   

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
  • -unavailable- added by hekawi (Posted a comment)
  • -unavailable- added by rik5 (Posted a comment)
  • -unavailable- added by hekawi
  •  

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

    Date Changed By Updated Field Previous Value => Replaced By
    Fri 03 Jan 2014 06:54:48 PM UTCrik5StatusNeed Info=>Fixed
      Open/ClosedOpen=>Closed
    Fri 03 Jan 2014 01:07:59 AM UTCrik5Attached File-=>Added non_perpendicular_bisect.png, #30156
    Thu 02 Jan 2014 10:50:18 PM UTChekawiAttached File-=>Added voronoibisector.m, #30151
      Attached File-=>Added voronoi.diff, #30152
    Thu 02 Jan 2014 07:11:36 PM UTCrik5Priority5 - Normal=>3 - Low
      Summaryvoronoi diagram has no result for two points=>voronoi doesn't return bisection line for input of two points
    Fri 27 Dec 2013 04:14:42 PM UTCrik5StatusNone=>Need Info
    Tue 24 Dec 2013 10:30:35 AM UTChekawiCarbon-Copy-=>Added hekawi

    Back to the top


    Powered by Savane 3.1-cleanup1