Hi All,
Looking at the cover of Science magazine for 9 Oct. 2009
<http://www.sciencemag.org/content/vol326/issue5950/cover.dtl>, I found
some sort of motivation to write two simple functions to draw such
Space-filling curves. It will be nice if they can be included in the
miscellaneous package, however, I'm not quite sure regarding the
convenience of the function names (they seem to be so general); if so,
please feel free to propose suitable new names.
FYI, the space-filling curves have interesting data locality properties
that have been exploited in parallel solvers for hierarchical domain
decomposition. Just to mention one.
Best,
Javier Enciso
## Copyright (C) 2009 Javier Enciso <[email protected]>
##
## This program is free software; you can redistribute it and/or modify
## it under the terms of the GNU General Public License as published by
## the Free Software Foundation; either version 3 of the License, or
## (at your option) any later version.
##
## This program is distributed in the hope that it will be useful,
## but WITHOUT ANY WARRANTY; without even the implied warranty of
## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
## GNU General Public License for more details.
##
## You should have received a copy of the GNU General Public License
## along with this program; if not, see
## <http://www.gnu.org/licenses/>.
## -*- texinfo -*-
## @deftypefn {Function file} {...@var{x}, @var{y}} hilbert (@var{n})
## Creates an iteration of the Hilbert space-filling curve with @var{n} points.
## The argument @var{n} must be of the form @code{2^M}, where @var{m} is an
## integer greater than 0.
##
## @example
## n = 8
## [x ,y] = hilbert (n);
## line (x, y, "linewidth", 4, "color", "blue");
## @end example
##
## @end deftypefn
function [x, y] = hilbert (n)
if (nargin != 1)
print_usage ();
endif
check_power_of_two (n);
if (n == 2)
x = [0, 0, 1, 1];
y = [0, 1, 1, 0];
else
[x1, y1] = hilbert (n/2);
x = [y1, x1, n/2 + x1, n - 1 - y1];
y = [x1, n/2 + y1, n/2 + y1, n/2 - 1 - x1];
endif
endfunction
function check_power_of_two (n)
if (frac_part (log (n) / log (2)) != 0)
error ("hilbert: input argument must be a power of 2.")
endif
endfunction
function d = frac_part (f)
d = f - floor (f);
endfunction
%!test
%! n = 2;
%! expect = [0, 0, 1, 1; 0, 1, 1, 0];
%! [get(1,:), get(2,:)] = hilbert (n);
%! if (any(size (expect) != size (get)))
%! error ("wrong size: expected %d,%d but got %d,%d", size (expect), size
(get));
%! elseif (any (any (expect!=get)))
%! error ("didn't get what was expected.");
%! endif
%!test
%! n = 5;
%!error hilbert (n);
%!demo
%! clg
%! n = 4;
%! [x, y] = hilbert (n);
%! line (x, y, "linewidth", 4, "color", "blue");
%! % -----------------------------------------------------------------------
%! % the figure window shows an iteration of the Hilbert space-fillig curve
%! % with 4 points on each axis.
%!demo
%! clg
%! n = 64;
%! [x, y] = hilbert (n);
%! line (x, y, "linewidth", 2, "color", "blue");
%! % ----------------------------------------------------------------------
%! % the figure window shows an iteration of the Hilbert space-fillig curve
%! % with 64 points on each axis.## Copyright (C) 2009 Javier Enciso <[email protected]>
##
## This program is free software; you can redistribute it and/or modify
## it under the terms of the GNU General Public License as published by
## the Free Software Foundation; either version 3 of the License, or
## (at your option) any later version.
##
## This program is distributed in the hope that it will be useful,
## but WITHOUT ANY WARRANTY; without even the implied warranty of
## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
## GNU General Public License for more details.
##
## You should have received a copy of the GNU General Public License
## along with this program; if not, see
## <http://www.gnu.org/licenses/>.
## -*- texinfo -*-
## @deftypefn {Function file} {...@var{x}, @var{y}} peano (@var{n})
## Creates an iteration of the Peano space-filling curve with @var{n} points.
## The argument @var{n} must be of the form @code{3^M}, where @var{m} is an
## integer greater than 0.
##
## @example
## n = 9;
## [x, y] = peano (n);
## line (x, y, "linewidth", 4, "color", "red");
## @end example
##
## @end deftypefn
function [x, y] = peano (n)
if (nargin != 1)
print_usage ();
endif
check_power_of_three (n);
if (n == 3)
x = [0, 0, 0, 1, 1, 1, 2, 2, 2];
y = [0, 1, 2, 2, 1, 0, 0, 1, 2];
else
[x1, y1] = peano (n/3);
x2 = n/3 - 1 - x1;
x3 = n/3 + x1;
x4 = n - n/3 - 1 - x1;
x5 = n - n/3 + x1;
x6 = n - 1 - x1;
y2 = n/3 + y1;
y3 = n - n/3 + y1;
y4 = n - 1 - y1;
y5 = n - n/3 - 1 - y1;
y6 = n/3 - 1 - y1;
x = [x1, x2, x1, x3, x4, x3, x5, x6, x5];
y = [y1, y2, y3, y4, y5, y6, y1, y2, y3];
endif
endfunction
function check_power_of_three (n)
if (frac_part (log (n) / log (3)) != 0)
error ("peano: input argument must be a power of 3.")
endif
endfunction
function d = frac_part (f)
d = f - floor (f);
endfunction
%!test
%! n = 3;
%! expect(1,:) = [0, 0, 0, 1, 1, 1, 2, 2, 2];
%! expect(2,:) = [0, 1, 2, 2, 1, 0, 0, 1, 2];
%! [get(1,:), get(2,:)] = peano (n);
%! if (any(size (expect) != size (get)))
%! error ("wrong size: expected %d,%d but got %d,%d", size (expect), size
(get));
%! elseif (any (any (expect!=get)))
%! error ("didn't get what was expected.");
%! endif
%!test
%! n = 5;
%!error peano (n);
%!demo
%! clg
%! n = 9;
%! [x, y] = peano (n);
%! line (x, y, "linewidth", 4, "color", "red");
%! % --------------------------------------------------------------------
%! % the figure window shows an iteration of the Peano space-fillig curve
%! % with 9 points on each axis.
%!demo
%! clg
%! n = 81;
%! [x, y] = peano (n);
%! line (x, y, "linewidth", 2, "color", "red");
%! % --------------------------------------------------------------------
%! % the figure window shows an iteration of the Peano space-fillig curve
%! % with 81 points on each axis.------------------------------------------------------------------------------
Come build with us! The BlackBerry(R) Developer Conference in SF, CA
is the only developer event you need to attend this year. Jumpstart your
developing skills, take BlackBerry mobile applications to market and stay
ahead of the curve. Join us from November 9 - 12, 2009. Register now!
http://p.sf.net/sfu/devconference
_______________________________________________
Octave-dev mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/octave-dev
