Space-filling curves for the miscellaneous package

[Javier Enciso]

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   <j4r.e4o@...>
##
## 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   <j4r.e4o@...>
##
## 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
Octave-dev@...
https://lists.sourceforge.net/lists/listinfo/octave-dev

[Søren Hauberg]

søn, 18 10 2009 kl. 00:20 +0200, skrev Javier Enciso:
> 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.

Yay, cool graphics :-)

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

Yeah, the names are probably too general (I believe we have a 'hilbert'
function already that generates a Hilbert matrix). Perhaps
'hilbert_curve' or the long-and-obvious name
'hilbert_space_filling_curve'?

'miscellaneous' seems like a fine place. We used to have a 'plot'
package, that could also be a suitable package, but I think we killed
that one.

Søren


------------------------------------------------------------------------------
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
Octave-dev@...
https://lists.sourceforge.net/lists/listinfo/octave-dev

[Daniel J Sebald]

Søren Hauberg wrote:
> søn, 18 10 2009 kl. 00:20 +0200, skrev Javier Enciso:
>
>>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.

Looks like a simple binary pattern creating a series of blocks that start a new "layer" with each change on binary order.

>>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.
>
>
> Yeah, the names are probably too general (I believe we have a 'hilbert'
> function already that generates a Hilbert matrix). Perhaps
> 'hilbert_curve' or the long-and-obvious name
> 'hilbert_space_filling_curve'?

Long names aren't good.  Go for short condensations.  Aim for no underscores if possible.  For example, hilfil.m gets the point across and has an aliteration memory aid.


> 'miscellaneous' seems like a fine place. We used to have a 'plot'
> package, that could also be a suitable package, but I think we killed
> that one.

Combinatorics might work, oweing to the geometric pattern.  But a fractals package would be good too.  (Why is there none?  Fractal patterns were all the rage a decade ago.)

Dan

------------------------------------------------------------------------------
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
Octave-dev@...
https://lists.sourceforge.net/lists/listinfo/octave-dev

[Pete Gonzalez]

Daniel J Sebald wrote:
> Søren Hauberg wrote:
>> Yeah, the names are probably too general (I believe we have a 'hilbert'
>> function already that generates a Hilbert matrix). Perhaps
>> 'hilbert_curve' or the long-and-obvious name
>> 'hilbert_space_filling_curve'?
>
> Long names aren't good.  Go for short condensations.  Aim for no
 > underscores if possible.  For example, hilfil.m gets the point
 > across and has an aliteration memory aid.

MATLAB was designed in an era when there were only a few hundred
identifiers to distinguish.  Memorizing that "hilfil" means "hilbert
space filling curve" was a small price to pay for saving some keystrokes
on that clunky terminal with no cut+paste.

By contrast, modern namespaces contain hundreds of thousands of names.
People today spend a lot more time reading code than typing it.  Most
programs are too big for any one person to have read every source file.

We can't change the standard function names established by MATLAB, but
if we define new functions, I don't see what's wrong with intuitive names.

Cheers,
-Pete

------------------------------------------------------------------------------
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
Octave-dev@...
https://lists.sourceforge.net/lists/listinfo/octave-dev

[Daniel J Sebald]

Pete Gonzalez wrote:

>
> Daniel J Sebald wrote:
>
>> Søren Hauberg wrote:
>>
>>> Yeah, the names are probably too general (I believe we have a 'hilbert'
>>> function already that generates a Hilbert matrix). Perhaps
>>> 'hilbert_curve' or the long-and-obvious name
>>> 'hilbert_space_filling_curve'?
>>
>>
>> Long names aren't good.  Go for short condensations.  Aim for no
>
>  > underscores if possible.  For example, hilfil.m gets the point
>  > across and has an aliteration memory aid.
>
> MATLAB was designed in an era when there were only a few hundred
> identifiers to distinguish.  Memorizing that "hilfil" means "hilbert
> space filling curve" was a small price to pay for saving some keystrokes
> on that clunky terminal with no cut+paste.

I say that still holds today.  I much prefer things like "cd" as opposed to "change_directory".


> By contrast, modern namespaces contain hundreds of thousands of names.
> People today spend a lot more time reading code than typing it.

I spend a lot of time typing code.  cut+paste are great, for big hunks of code.  But composing code still requires efficiency in keystrokes.  As far as reading code, long function names can send things off the viewing window.

But there is a difference in the setting.  If it is production code unique to some device or program, then long descriptive names are good because it informs the reader about what this function (one they've never seen) does.  Furthermore, and importantly, there is no help feature to explain what the function is.

In the case of the hypothetical "hilfil", I discover that by looking at the package list "fractals" ("miscellaneous" isn't descriptive about category) and next to the function name is a description of what it is.  If one comes across an unknown function name in some code, he uses the help feature.

There is a place for long function names, but once a function reaches package-status, or operating-system-status, or programming-language-status, brevity is good.  I'm not strongly against "hilbert_space_filling_curve", but lean in the direction of shorter is better.


>  Most
> programs are too big for any one person to have read every source file.
>
> We can't change the standard function names established by MATLAB, but
> if we define new functions, I don't see what's wrong with intuitive names.

"hilfil" isn't non-intuitive, it's cryptic.  But once one knows it (similar to commands like "freqz") it's easily remembered.  The saving grace for remembering something like "hilbert_space_filling_curve" is tab completion.

Dan

------------------------------------------------------------------------------
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
Octave-dev@...
https://lists.sourceforge.net/lists/listinfo/octave-dev

[Javier Enciso]

Daniel J Sebald wrote:

> Pete Gonzalez wrote:
>> Daniel J Sebald wrote:
>>
>>> Søren Hauberg wrote:
>>>
>>>> Yeah, the names are probably too general (I believe we have a 'hilbert'
>>>> function already that generates a Hilbert matrix). Perhaps
>>>> 'hilbert_curve' or the long-and-obvious name
>>>> 'hilbert_space_filling_curve'?
>>>
>>> Long names aren't good.  Go for short condensations.  Aim for no
>>  > underscores if possible.  For example, hilfil.m gets the point
>>  > across and has an aliteration memory aid.
>>
>> MATLAB was designed in an era when there were only a few hundred
>> identifiers to distinguish.  Memorizing that "hilfil" means "hilbert
>> space filling curve" was a small price to pay for saving some keystrokes
>> on that clunky terminal with no cut+paste.
>

Thanks all for your superb feedback.

I think the middle point between the over explicit
'hilbert_space_filling_curve' and the cryptic 'hilfil' is
'hilbert_curve'. If there is no any other concern, I'm going to use
'hilbert_curve' and 'peano_curve'.

Best,
Javier

------------------------------------------------------------------------------
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
Octave-dev@...
https://lists.sourceforge.net/lists/listinfo/octave-dev