The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Math-PlanePath-53
River stage one • 3 direct dependents • 4 total dependents
2 ++
/ Math::PlanePath::BetaOmega

NAME

Math::PlanePath::BetaOmega -- 2x2 half-plane traversal

SYNOPSIS

 use Math::PlanePath::BetaOmega;
 my $path = Math::PlanePath::BetaOmega->new;
 my ($x, $y) = $path->n_to_xy (123);

DESCRIPTION

This is an integer version of the Beta-Omega curve by Jens-Michael Wierum. It makes a 2x2 self-similar traversal of a half plane (X>=0),

      5   25--26  29--30  33--34  37--38
           |   |   |   |   |   |   |   |
      4   24  27--28  31--32  35--36  39
           |                           |
      3   23  20--19--18  45--44--43  40
           |   |       |   |       |   |
      2   22--21  16--17  46--47  42--41
                   |           |        
      1    1-- 2  15--14  49--48  53--54
           |   |       |   |       |   |
    Y=0->  0   3  12--13  50--51--52  55
               |   |                   |
     -1    5-- 4  11--10  61--60--59  56
           |           |   |       |   |
     -2    6-- 7-- 8-- 9  62--63  58--57
                               |        
     -3                       ...

         X=0   1   2   3   4   5   6   7

Each level extends in (2^level)x(2^level) blocks alternately above or below. The initial N=0 to N=3 extends up from Y=0 and exits the block downwards as N=4 and extends downwards through to exit upwards at N=15. Then N=16 extends upwards through to N=63 which exits downwards, etc.

The curve is named for the two base shapes

         Beta                     Omega

           *---*                  *---*
           |   |                  |   |
         --*   *                --*   *--
               |

The beta comprises three betas and an omega, the omega comprises four betas, in each case suitably rotated, transposed or reversed, so expanding to.

      *---*---*---*            *---*---*---*
      |           |            |           |
      *---*   *---*            *---*   *---*
          |   |                    |   |    
    --*   *   *---*          --*   *   *   *--
      |   |       |            |   |   |   |
      *---*   *---*            *---*   *---*
              |

The curve is expressed in terms of repeated ever-smaller substitutions, which has the effect of making the start a beta going alternately up or down. For this integer version of the path the start direction is fixed as a beta going upwards and the higher levels alternately up and down from that orientation.

FUNCTIONS

See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path classes.

$path = Math::PlanePath::BetaOmega->new ()

Create and return a new path object.

($x,$y) = $path->n_to_xy ($n)

Return the X,Y coordinates of point number $n on the path. Points begin at 0 and if $n < 0 then the return is an empty list.

SEE ALSO

Math::PlanePath, Math::PlanePath::HilbertCurve

Jens-Michael Wierum "Definition of a New Circular Space-Filling Curve: Beta-Omega-Indexing", Technical Report TR-001-02, Paderborn Center for Parallel Computing, March 2002.

Jens-Michael Wierum, "Logarithmic Path-Length in Space-Filling Curves", 14th Canadian Conference on Computational Geometry (CCCG'02), 2002.

    http://www.cccg.ca/proceedings/2002/
    http://www.cccg.ca/proceedings/2002/27.ps     [shorter]
    http://www.cccg.ca/proceedings/2002/27l.ps    [longer]

HOME PAGE

http://user42.tuxfamily.org/math-planepath/index.html

LICENSE

Copyright 2011 Kevin Ryde

This file is part of Math-PlanePath.

Math-PlanePath 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, or (at your option) any later version.

Math-PlanePath 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 Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.