help-octave
[Top][All Lists]
Advanced

[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
User-agent: Mozilla-Thunderbird 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 Boulogne-Billancourt 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 @@
+2008-12-29  David Bateman  <address@hidden>
+
+       * goemetry/voronoi.m: Speed up and handle dense grids.
+
 2008-12-28  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:end-1)]], c, 
+                           "UniformOutput", false));
 
   ## Identify the unique edges of the Voronoi diagram
   edges = sortrows (sort (edges).').';

reply via email to

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