Fri 03 Jan 2014 10:01:58 PM UTC, comment #10:
This looks good. Thanks a lot!
|
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.
|
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.
|
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.
|
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)
|
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)
|
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).
|
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.
|
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
|
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.
|
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)
|