[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Voronoi Diagrams
From: 
David Bateman 
Subject: 
Re: Voronoi Diagrams 
Date: 
Mon, 29 Dec 2008 23:44:16 +0100 
Useragent: 
MozillaThunderbird 2.0.0.17 (X11/20081018) 
David Bateman wrote:
Ryan Matthew Balfanz wrote:
Hi All,
I've changed the the lines starting from line number 127 to the
following:

#idx = find (!infi); # Original
idx = find ( ! resize (infi, size(c))); # Modified
ll = length (idx); # Original
#ll = min (length (idx), length (c)); # Modified

and get strange output.
My input file can be found at
http://www.phy.ilstu.edu/~rbalfanz/voronoi/inp.dat
The output can be found at
http://www.phy.ilstu.edu/~rbalfanz/voronoi/voronoi.pdf
To get my results do the following in octave:

load inp.dat
voronoi(inp(:,2), inp(:,3))

For the curious, columns 2 and 3 of inp.dat are positional data of
galaxies. I'm having no trouble in MatLab working with this data even
though individual points can be extremely close to one another.
That is a surprising result... It appears that Qhull's Voronoi
algorithm has some sort of threshold of whether the distance between a
point is considered significant or not that is relative to the
distance between two points and the maximum distance between any
point. Unfortunately the external box I added to get the matlab
compatibiliy works well for convhull and needs to be extremely large
in that case to approximate a box at infinite. However, it causes
issues for voronoi. For now set scale to something smaller then 1e4
(say scale = 1e2) and it should work.. I'll look at a better fix soon.
Ok it appears that yes the box is needed, but scale can be as small as
2... In any case working on this I found the attached speedup to this
function that should double its speed... The plotting with gnuplot is
still really sssslllloooowwwww though.
D.

David Bateman address@hidden
35 rue Gambetta +33 1 46 04 02 18 (Home)
92100 BoulogneBillancourt FRANCE +33 6 72 01 06 33 (Mob)
# HG changeset patch
# User David Bateman <address@hidden>
# Date 1230590478 3600
# Node ID 9a85ba74f26b2da0e23a8fe165eaa9cbdaa33cb7
# Parent 96b15e87cae2d3a662ac4775207f9f935802b94c
Fix for dense grids and speed up for voronoi function
diff git a/scripts/ChangeLog b/scripts/ChangeLog
 a/scripts/ChangeLog
+++ b/scripts/ChangeLog
@@ 1,3 +1,7 @@
+20081229 David Bateman <address@hidden>
+
+ * goemetry/voronoi.m: Speed up and handle dense grids.
+
20081228 Jaroslav Hajek <address@hidden>
* miscellaneous/delete.m: Allow filename globs. Display warnings if
diff git a/scripts/geometry/voronoi.m b/scripts/geometry/voronoi.m
 a/scripts/geometry/voronoi.m
+++ b/scripts/geometry/voronoi.m
@@ 106,44 +106,31 @@
error ("voronoi: arguments must be vectors of same length");
endif
 ## Add big box to approximate rays to infinity
+ ## Add box to approximate rays to infinity. For Voronoi diagrams the
+ ## box can (and should) be close to the points themselves. To make the
+ ## job of finding the exterior edges it should be at least two times the
+ ## delta below however
xmax = max (x(:));
xmin = min (x(:));
ymax = max (y(:));
ymin = min (y(:));
xdelta = xmax  xmin;
ydelta = ymax  ymin;
 scale = 10e4;
+ scale = 2;
xbox = [xmin  scale * xdelta; xmin  scale * xdelta; ...
xmax + scale * xdelta; xmax + scale * xdelta];
ybox = [xmin  scale * xdelta; xmax + scale * xdelta; ...
xmax + scale * xdelta; xmin  scale * xdelta];
 x = [x(:) ; xbox(:)];
 y = [y(:) ; ybox(:)];
 [p, c, infi] = __voronoi__ ([x(:), y(:)], opts{:});
+ [p, c, infi] = __voronoi__ ([[x(:) ; xbox(:)], [y(:); ybox(:)]], opts{:});
idx = find (!infi);

ll = length (idx);
 k = 0;r = 1;

 for i = 1 : ll
 k += length (c{idx(i)});
 endfor

 edges = zeros (2, k);

 for i = 1 : ll
 fac = c{idx(i)};
 lf = length (fac);
 fac = [fac, fac(1)];
 fst = fac (1 : length(fac)  1);
 sec = fac(2 : length(fac));
 edges (:, r : r + lf  1) = [fst; sec];
 r += lf;
 endfor
+ c = c(idx).';
+ k = sum (cellfun ('length', c));
+ edges = cell2mat(cellfun (@(x) [x ; [x(end), x(1:end1)]], c,
+ "UniformOutput", false));
## Identify the unique edges of the Voronoi diagram
edges = sortrows (sort (edges).').';
 Voronoi Diagrams, Ryan Matthew Balfanz, 2008/12/22
 Re: Voronoi Diagrams, Ben Abbott, 2008/12/22
 Re: Voronoi Diagrams, Ryan Matthew Balfanz, 2008/12/22
 Re: Voronoi Diagrams, Ben Abbott, 2008/12/22
 Re: Voronoi Diagrams, SÃ¸ren Hauberg, 2008/12/22
 Re: Voronoi Diagrams, Ben Abbott, 2008/12/22
 Re: Voronoi Diagrams, David Bateman, 2008/12/22
 Re: Voronoi Diagrams, Ryan Matthew Balfanz, 2008/12/29
 Re: Voronoi Diagrams, David Bateman, 2008/12/29
 Re: Voronoi Diagrams,
David Bateman <=