[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).').';
- 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 <=