NAME

       Math::PlanePath::HilbertSpiral -- 2x2 self-similar spiral

SYNOPSIS

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

DESCRIPTION

       This is a Hilbert curve variation which fills the plane by spiralling around into negative
       X,Y on every second replication level.

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

               -2  -1  X=0  1   2   3   4   5

       The curve starts with the same N=0 to N=3 as the "HilbertCurve", then the following 2x2
       blocks N=4 to N=15 go around in negative X,Y.  The top-left corner for this negative
       direction is at Ntopleft=4^level-1 for an odd numbered level.

       The parts of the curve in the X,Y negative parts are the same as the plain "HilbertCurve",
       just mirrored along the anti-diagonal.  For example. N=4 to N=15

           HilbertSpiral             HilbertCurve

                         \        5---6   9--10
                          \       |   |   |   |
                           \      4   7---8  11
                            \                 |
             5-- 4           \           13--12
             |                \           |
             6-- 7             \         14--15
                 |              \
             9-- 8  13--14       \
             |       |   |        \
            10--11--12  15

       This mirroring has the effect of mapping

           HilbertCurve X,Y  ->  -Y,-X for HilbertSpiral

       Notice the coordinate difference (-Y)-(-X) = X-Y so that difference, representing a
       projection onto the X=-Y opposite diagonal, is the same in both paths.

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

           Nstart = 0
           Nlevel = 4^level - 1    (inclusive)

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

           width = height = Xmax - Xmin
                          = Ymax - Ymin
                          = 2^level - 1

       The X,Y range doubles alternately above and below, so the result is a 1 bit going
       alternately to the max or min, starting with the max for level 1.

           level     X,Ymin   binary      X,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 formulas above for Ymin/Ymax have the effect of producing alternating bit
       patterns like this.

       This is the same sort of level range as "BetaOmega" has on its Y coordinate, but on this
       "HilbertSpiral" it applies to both X and Y.

FUNCTIONS

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

       "$path = Math::PlanePath::HilbertSpiral->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)".

OEIS

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

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

           A059285    X-Y coordinate diff

       The difference X-Y is the same as the "HilbertCurve", since the "negative" spiral parts
       are mirrored across the X=-Y anti-diagonal, which means coordinates (-Y,-X) and -Y-(-X) =
       X-Y.

SEE ALSO

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

HOME PAGE

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

LICENSE

       Copyright 2011, 2012, 2013, 2014, 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/>.