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

NAME

       Math::PlanePath::HilbertSides -- sides of Hilbert curve squares

SYNOPSIS

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

DESCRIPTION

       This path is segments along the sides of the Hilbert curve squares as per

           F. M. Dekking, "Recurrent Sets", Advances in Mathematics, volume 44, 1982, pages
           79-104, section 4.8 "Hilbert Curve"

       The base pattern is N=0 to N=4.  That pattern repeats transposed as points N=0,4,8,12,16,
       etc.

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

       If each point of the "HilbertCurve" path is taken to be a unit square the effect here is
       to go along the sides of those squares.  The square for a segment is on the left or right,

            -------3.       .
               v   |
                   |>
                   |
                   2        .
                   |
                   |>
               ^   |
           0-------1        .

       Some points are visited twice.  The first is at X=2,Y=3 which is N=7 and N=9 where the two
       segments N=7to8 and N=8to9 overlap.  These are consecutive segments, and non-consecutive
       segments can overlap too, as for example N=27to28 and N=36to37.  Double-visited points
       occur also as corners touching, for example at X=4,Y=3 the two N=11 N=31 touch without
       overlapping segments.

       The HilbertCurve squares fall within 2^k x 2^k blocks and so likewise the segments here.
       The right side 1 to 2 and 2 to 3 don't touch the 2^k side.  This is so of the base figure
       N=0 to N=4 which doesn't touch X=2 and higher levels are unrotated replications so for
       example in the N=0 to N=64 shown above X=8 is not touched.  This creates rectangular
       columns up from the X axis.  Likewise rectangular rows across from the Y axis, and both
       columns and rows inside.

       The sides which are N=0 to N=1 and N=3 to N=4 of the base pattern variously touch in
       higher levels giving interesting patterns of squares, shapes, notches, etc.

FUNCTIONS

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

       "$path = Math::PlanePath::HilbertSides->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 = $path->xy_to_n ($x,$y)"
           Return the point number for coordinates "$x,$y".  If there's nothing at "$x,$y" then
           return "undef".

           The curve visits an "$x,$y" twice for various points.  The smaller of the two N values
           is returned.

       "@n_list = $path->xy_to_n_list ($x,$y)"
           Return a list of N point numbers for coordinates "$x,$y".  Points may have up to two
           Ns for a given "$x,$y".

FORMULAS

   Coordinates
       Difference X-Y is the same here as in the "HilbertCurve".  The base pattern here has N=3
       at 1,2 whereas the HilbertCurve is 0,1 so X-Y is the same.  The two then have the same
       pattern of rotate 180 and/or transpose in subsequent replications.

                             3
                             |
           HilbertSides      2         3----2    HilbertCurve
                             |              |
                        0----1         0----1

   Abs dX,dY
       abs(dY) is 1 for a vertical segment and 0 for a horizontal segment.  For the curve here it
       is

           abs(dY) = count 1-bits of N, mod 2 = Thue-Morse binary parity
           abs(dX) = 1 - abs(dY)              = opposite

       This is so for the base pattern N=0,1,2, and also at N=3 turning towards N=4.  Replication
       parts 1 and 2 are transposes where there is a single extra 1-bit in N and dX,dY are
       swapped.  Replication part 3 is a 180 degree rotation where there are two extra 1-bits in
       N and dX,dY are negated so abs(dX),abs(dY) unchanged.

   Turn
       The path can turn left or right or go straight forward or 180 degree reverse.
       Straight,reverse vs left,right is given by

           N num trailing 0 bits               turn
           ---------------------      -----------------------
                 odd                  straight or 180 reverse     (A096268)
                 even                 left or right               (A035263)

       The path goes straight ahead at 2 and reverses 180 at 8 and all subsequent 2*4^k.

   Segments on Axes
       The number of line segments on the X and Y axes 0 to 2^k, which is N=0 to 4^k, is

           Xsegs[k] = 1/3*2^k + 1/2 + 1/6*(-1)^k
                    = 1, 1, 2, 3, 6, 11, 22, 43, 86             (A005578)
                    = Ysegs[k] + 1

           Ysegs[k] = 1/3*2^k - 1/2 + 1/6*(-1)^k
                    = 0, 0, 1, 2, 5, 10, 21, 42, 85,...         (A000975)
                    = binary 101010...   k-1 many bits alternating

       These counts can be calculated from the curve sub-parts

             k odd              k even

           +---+   .          .   .   .
             R |>T              T   T
           .   .   .          +---+---+
               |>T            |>    R<|
           o---+   .          o   .   +

       The block at the origin is X and Y segments of the k-1 level.  For k odd, the X axis then
       has a transposed block which means the Y segments of k-1.  The Y axis has a 180 degree
       rotated block R.  The curve is symmetric in mirror image across its start to end so the
       count of segments it puts on the Y axis is the same as Y of level k-1.

           Xsegs[k] = Xsegs[k-1] +   Ysegs[k-1]       for k odd
           Ysegs[k] =              2*Ysegs[k-1]

       Then similarly for k even, but the other way around the 2*Y.

           Xsegs[k] = 2*Xsegs[k-1]                    for k even
           Ysegs[k] =   Xsegs[k-1] + Ysegs[k-1]

OEIS

       Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include

           <http://oeis.org/A059285> (etc)

           A059285    X-Y
           A010059    abs(dX), 1 - Thue-Morse binary parity
           A010060    abs(dY), Thue-Morse binary parity

           A096268    turn 1=straight or reverse, 0=left or right
           A035263    turn 0=straight or reverse, 1=left or right

           A062880    N values on diagonal X=Y (digits 0,2 in base 4)

           A005578    count segments on X axis, level k
           A000975    count segments on Y axis, level k

SEE ALSO

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

HOME PAGE

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

LICENSE

       Copyright 2015, 2016, 2017, 2018, 2019, 2020 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/>.