Provided by: libmath-planepath-perl_125-1_all bug

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

           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.

       The curve form here makes a 2x2 self-similar traversal of the 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 square parts 2^level x 2^level alternately up or down.  The initial N=0
       to N=3 extends upwards from Y=0 and exits the block downwards at N=3.  N=4 extends
       downwards and goes around back upwards to exit N=15.  N=16 then extends upwards through to
       N=63 which exits downwards, etc.

       The curve is named for the two base shapes

                Beta                     Omega

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

       The beta is made from three betas and an omega sub-parts.  The omega is made from four
       betas.  In each case the sub-parts are suitably rotated, transposed or reversed, so
       expanding to

           Beta = 3*Beta+Omega      Omega = 4*Beta

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

       The sub-parts represent successive ever-smaller substitutions.  They have the effect of
       making the start a beta going alternately up or down.  For this integer version the start
       direction is kept fixed as a beta going upwards and the higher levels then alternate up
       and down from there.

   Level Ranges
       Reckoning the initial N=0 to N=3 as level 1, a replication level extends to

           Nlevel = 4^level - 1
           Xmin = 0
           Xmax = 2^level - 1

           Ymin = - (4^floor(level/2) - 1) * 2 / 3
                = binary 1010...10
           Ymax = (4^ceil(level/2) - 1) / 3
                = binary 10101...01

           height = Ymax - Ymin = 2^level - 1

       The Y range increases alternately above and below by a power of 2, so the result for Ymin
       and Ymax is a 1 bit going alternately to Ymax and Ymin, starting with Ymax for level 1.

           level     Ymin    binary       Ymax   binary
           -----     --------------       -------------
             0         0                    0
             1         0          0         1 =       1
             2        -2 =      -10         1 =      01
             3        -2 =     -010         5 =     101
             4       -10 =    -1010         5 =    0101
             5       -10 =   -01010        21 =   10101
             6       -42 =  -101010        21 =  010101
             7       -42 = -0101010        85 = 1010101

       The power of 4 divided by 3 formulas above for Ymin/Ymax have the effect of producing
       alternating bit patterns like this.

       For odd levels -Ymin/height approaches 1/3 and Ymax/height approaches 2/3, ie. the start
       point is about 1/3 up the total extent.  For even levels it's the other way around, with
       -Ymin/height approaching 2/3 and Ymax/height approaching 1/3.

   Closed Curve
       Wierum's idea for the curve is a closed square made from four betas,

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

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

       And at the next expansion level

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

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

       The code here could be used for that by choosing a level and applying four copies of the
       path suitably mirrored and offset in X and Y.

       For an odd level, the path N=0 to N=4^level-1 here is the top-right quarter, entering on
       the left and exiting downwards.  For an even level it's the bottom-right shape instead,
       exiting upwards.  The difference arises because when taking successively greater detail
       sub-parts the initial direction alternates up or down, but in the code here it's kept
       fixed (as noted above).

       The start point here is also fixed at Y=0, so an offset Ymin must be applied if say the
       centre of the sections is to be Y=0 instead of the side entry point.

FUNCTIONS

       See "FUNCTIONS" in Math::PlanePath for 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.

       "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
           The returned range is exact, meaning $n_lo and $n_hi are the smallest and biggest in
           the rectangle.

   Level Methods
       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
           Return "(0, 4**$level - 1)".

FORMULAS

   N to X,Y
       Each 2 bits of N become a bit each for X and Y in a "U" arrangement, but which way around
       is determined by sub-part orientation and beta/omega type per above,

           beta rotation     4 of
                transpose    2 of
                reverse      2 of
           omega rotation    4 of
                 transpose   2 of
                           ----
           total states     24   = 4*2*2 + 4*2

       The omega pattern is symmetric so its reverse is the same, hence only rotate and transpose
       forms for it.  Omitting omega reverse reduces the states from 32 to 24, saving a little
       space in a table driven approach.  But if using separate variables for rotate, transpose
       and reverse then the reverse can be kept for both beta and omega without worrying that it
       makes no difference in the omega.

       Adding bits to Y produces a positive value measured up from Ymin(level), where level is
       the number of base 4 digits in N.  That Ymin can be incorporated by adding -(2^level) for
       each even level.  A table driven calculation can work that in as for example

           digit = N base 4 digits from high to low

           xbit = digit_to_x[state,digit]
           ybit = digit_to_y[state,digit]
           state = next_state[state,digit]

           X += 2^level * xbit
           Y += 2^level * (ybit - !(level&1))

       The (ybit-!(level&1)) means either 0,1 or -1,0.  Another possibility there would be to
       have -!(level&1) in the digit_to_y[] table, doubling the states so as to track the
       odd/even level within the state and having the digit_to_y[] as -1,0 in the even and 0,1 in
       the odd.

   N to X,Y Fraction
       If N includes a fractional part, it can be put on a line towards the next integer point by
       taking the direction as at the least significant non-3 digit.

       If the least significant base 4 digit is 3 then the direction along the curve is
       determined by the curve part above.  For example at N=7 (13 base 4) it's rightwards as per
       the inverted beta which is the N=4 towards N=8 part of the surrounding pattern.  Or
       likewise N=11 (23 base 4) in the N=8 to N=12 direction.

               |                 0    12--
           5---4                 |     |
           |                     |     |
           6---7-- ...           4-----8

       If all digits are 3 base 4, which is N=3, N=15, N=63, etc, then the direction is down for
       an odd number of digits, up for an even number.  So N=3 downwards, N=15 upwards, N=63
       downwards, etc.

       This curve direction calculation might be of interest in its own right, not merely to
       apply a fractional N as done in the code here.  There's nothing offered for that in the
       "PlanePath" modules as such.  For it the X,Y values can be ignored just follow the state
       or orientations changes using the base 4 digits of N.

SEE ALSO

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

           <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.3487> (cached copy)

       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, 2012, 2013, 2014, 2015, 2016, 2017 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/>.