Voronoi Diagrams

[Ben Abbott]

On Dec 22, 2008, at 10:50 AM, Ryan Matthew Balfanz wrote:
>
> On Mon, Dec 22, 2008 at 9:43 AM, Ben Abbott <bpabbott at mac.com> wrote:
>>
>> On Dec 22, 2008, at 10:11 AM, Ryan Matthew Balfanz wrote:
>>
>>> Hi all,
>>> I've been having trouble getting octave to play nice making voronoi
>>> diagrams with large data sets (~5000).
>>>
>>> Does anyone else notice this? I don't want to file a big report  
>>> unless
>>> I know it is universal.
>>>
>>> Thanks,
>>> Ryan
>>
>> Can you give some more detail?
>>
>> It is possible to create a simple script to demonstrate the problem?
>>
>> Ben
>
> Hi Ben,
> Thanks for the reply. He is some more information, hope it helps.
>
> I've not included my own script / data file for this more general
> example taken from
> http://www.obihiro.ac.jp/~suzukim/masuda/octave/html3/octave_152.html
> .
> I've only upped the number of random points from 10 to 1000.
>
> === test_voronoi.m  ===
> x = rand (1000, 1);
> y = rand (size (x));
> h = convhull (x, y);
> [vx, vy] = voronoi (x, y);
> plot (vx, vy, "-b", x, y, "o", x(h), y(h), "-g")
> legend ("", "points", "hull");
>
> === Output ===
> client138-50:Desktop ryan$ octave test_voronoi.m
> GNU Octave, version 3.0.3
> Copyright (C) 2008 John W. Eaton and others.
> This is free software; see the source code for copying conditions.
> There is ABSOLUTELY NO WARRANTY; not even for MERCHANTIBILITY or
> FITNESS FOR A PARTICULAR PURPOSE.  For details, type `warranty'.
>
> Octave was configured for "i386-apple-darwin9.5.0".
>
> Additional information about Octave is available at http://www.octave.org 
> .
>
> Please contribute if you find this software useful.
> For more information, visit http://www.octave.org/help-wanted.html
>
> Report bugs to <bug at octave.org> (but first, please read
> http://www.octave.org/bugs.html to learn how to write a helpful  
> report).
>
> For information about changes from previous versions, type `news'.
>
>
> Output completed.  Verifying that all points are below 2.6e-15 of
> all facets.  Will make 17000 distance computations.
> error: invalid vector index = 963
> error: evaluating argument list element number 1
> error: evaluating assignment expression near line 133, column 7
> error: evaluating for command near line 132, column 3
> error: called from `voronoi' in file
> `/opt/local/share/octave/3.0.3/m/geometry/voronoi.m'
> error: near line 4 of file `test_voronoi.m'

My fist comment is that I'm out of my area of expertise .... looking  
at voronoi.m I've isoloated the origin of the error to the three lines  
below (lines 125-129 in voronoi.m)

	[p, c, infi] = __voronoi__ ([x(:), y(:)], opts{:});
	idx = find (!infi);
	ll = length (idx);

The problem is that "c" may be returned with a shorted length than  
"idx". After many test runs I've concluded there is some statistical  
possibility that even relatively short input vectors can produce the  
error, but those longer than 209 do so very reliably. However, once  
you chose a length of 1000, failure is essentially guaranteed.

I do not know if it is proper to do so, but the error may be avoided  
by determining "ll" by

	ll = min (length (idx), length (c));

While this does permit a diagram to be produced and the rendered  
convex hull does appear to be correct, it is clear that someone who  
understands how __voronoi__ is intended to work should look at this.

As Kai Habel was the originator of the __voronoi__.cc, I've cc'd him  
in the hope he offer a more expert opinion.

Ben