[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Voronoi Diagrams

From: Ben Abbott
Subject: Re: Voronoi Diagrams
Date: Mon, 22 Dec 2008 13:25:38 -0500

On Dec 22, 2008, at 10:50 AM, Ryan Matthew Balfanz wrote:

On Mon, Dec 22, 2008 at 9:43 AM, Ben Abbott <address@hidden> 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.


Can you give some more detail?

It is possible to create a simple script to demonstrate the problem?


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

Please contribute if you find this software useful.
For more information, visit

Report bugs to <address@hidden> (but first, please read 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
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, I've cc'd him in the hope he offer a more expert opinion.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]